Tri de crêpes

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le tri de crêpes (de l'anglais pancake sorting) est une variante du problème du tri. Il s'agit de trier une pile de crêpes afin que les crêpes soient empilées de la plus grande à la plus petite (au sens de leur diamètre). La seule opération autorisée pour arriver à ce résultat est de retourner la partie supérieure de la pile.

Énoncé du problème[modifier | modifier le code]

Un cuisinier fait des crêpes et les pose en pile à côté de la poêle lorsqu'elles sont cuites. Toutes les crêpes sont de taille différente. On dispose donc d'une pile de crêpes, chacune de taille différente et il s'agit d'ordonner les crêpes dans la pile, par ordre décroissant de taille (diamètre) avec donc celle de plus petit diamètre en haut de la pile.

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

La question est : pour une pile de N crêpes, quel est le nombre maximum de manipulations (P) qui sont nécessaires à la mettre dans l'ordre décroissant. Le nombre minimum de manipulations est toujours 0 puisque le cuisinier peut avoir cuit les crêpes dans l'ordre décroissant de taille, auquel cas, il n'y a aucune manipulation à faire.

Un premier exemple peut être avec 2 crêpes (N=2), où l'on a alors seulement deux configurations de pile possibles. Soit il a cuit d'abord la petite puis la plus grande, soit c'est le contraire. Dans le premier cas, la plus petite est en bas et la plus grande en haut : il faut donc retourner toute la pile pour la mettre dans l'ordre voulu en glissant la spatule sous la crêpe du fond de la pile. Une seule manipulation est ainsi nécessaire. Dans le second cas, la pile est dans déjà l'ordre désiré, aucune manipulation n'est nécessaire. Donc pour N=2, P est au maximum de 1.

Le problème qui se pose est de trouver la loi mathématique qui donne P pour tout N. Ce problème n'a toujours pas de solution complète. Les chercheurs qui se penchent depuis plus de 30 ans sur la question ont jusqu'ici réussi à estimer P qui serait toujours inférieur à 18n/11 dès que N>2. Cette valeur a été révélée en 2008 par une équipe de l'Université de Dallas (Texas). Elle affine une estimation de 1997 qui avait établi une borne maximum de 15n/14.

Intérêts[modifier | modifier le code]

Dans un autre formalisme, le problème est équivalent au tri d'un tableau à l'aide d'une seule opération, l'inversion d'un préfixe.

Le tri de crêpes présenté en parallèle du problème classique du tri permet d'insister sur les opérateurs permis pour résoudre un problème d'algorithmique.

Une des particularités de ce tri se trouve dans les personnes s'y étant initialement intéressées : Bill Gates (fondateur de Microsoft, qui avait publié sous son vrai nom William Gates), David X. Cohen (l'un des créateurs de la série Futurama), et aussi Christos Papadimitriou, un informaticien de grand renom.

Références[modifier | modifier le code]

Liens externes[modifier | modifier le code]