Concours Informatique du LIPN

Ce concours est ouvert à tous les étudiants inscrits à l'institut Galilée ou à l'IUT de Villetaneuse (Licence, Master, IUT, Sup-Galilée).

Ce concours est une introduction à la recherche en informatique. Les participants doivent constituer un dossier de recherche sur le problème ci-dessous. Ce dossier pourra contenir des preuves, des programmes, des références bibliographiques,...

Le nombre maximum d'étudiants sur un même projet est fixé à 3.

La date limite pour la soumission est fixée au vendredi 16 mai.

Le jury donnera le résultat du concours le vendredi 20 juin. Une remise des prix est prévue avec un stand de crêpes !

Le problème sélectionné pour l'année 2014 est le suivant :

Un cuisinier fait des crêpes et les empile les unes sur les autres. Toutes les crêpes (supposées parfaitement circulaires) ont des diamètres différents. Le problème consiste à ordonner les crêpes par ordre décroissant de taille (diamètre), c'est à dire la plus petite en haut de la pile.

Pour cela, une seule opération est autorisée pour manipuler la pile : insérer une spatule à un endroit de la pile et retourner toutes les crêpes qui se trouvent au-dessus de la spatule (comme l'on retournerait des crêpes).

Le problème est de déterminer pour une pile de n crêpes, quel est le nombre maximum de manipulations m(n) nécessaires pour réordonner la pile. Mais, on peut explorer toutes les questions annexes possibles : le nombre moyen de manipulations, la pile la plus dure à réorganiser, l'algorithme le plus efficace, des bornes supérieures pour m(n), des codes optimisés pour trouver les valeurs m(n),... ?

Bon courage !

Les étudiants désirant participer peuvent envoyer un mail à olivier.bodini@lipn.univ-paris13.fr