Tri de crêpes
Problème lié |
---|
Le tri de crêpes (de l'anglais pancake sorting) est un problème mathématique. 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. On peut considérer d'une part le problème algorithmique, où le but est d'arriver à la configuration finale, comme pour un algorithme de tri, et d'autre part des questions mathématiques. Une question classique est d'évaluer le nombre minimum de mouvements nécessaires, pour toute pile d'une certaine taille.
Contexte
[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. Un seul type d'opération est autorisé 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.
Problèmes mathématiques
[modifier | modifier le code]La question est : pour N crêpes, quel est le nombre minimum de manipulations (P) qui sont nécessaires pour mettre toute pile dans l'ordre décroissant ?
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 déjà dans l'ordre désiré, aucune manipulation n'est nécessaire. Donc pour N=2, P est au maximum de 1.
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. D'autre part, dès que N>4, il existe des piles où aucune crêpe ne touche une crêpe qui sera sa voisine dans le tri final (paire adjacente de crêpes). Comme chaque inversion crée au plus une adjacence de ce type, le tri prend nécessairement au moins N inversions - mais peut devoir en prendre plus[1]. De même, le nombre maximal est toujours inférieur à 2N-3 (on peut trier la pile séquentiellement, en commençant par la plus grande, avec deux inversions par crêpes, et le tri des deux dernières prend au plus un coup)[1]. Mais cette manière de faire n'est pas nécessairement optimale. Si une pile de trois crêpes peut demander jusqu'à trois inversions, une pile de quatre peut toujours être triée en quatre inversions (économisant un coup) et une pile de cinq en cinq inversions (économisant deux coups).
P en fonction de N
[modifier | modifier le code]Le problème qui se pose est de trouver la loi mathématique qui donne P pour tout N, quand le tri est conduit de manière optimale. Ce problème est NP-difficile[2],[3] et 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 à [2]. Cette valeur a été révélée en 2008 par une équipe de l'Université de Dallas (Texas). Cette valeur affine un majorant de obtenu en 1979[1].
Nombre de problèmes
[modifier | modifier le code]Le nombre C de configurations qu’une pile de crêpes possède au début du problème dépend du nombre N de crêpes dans cette pile. Il s’agit du nombre de façons différentes de permuter les N crêpes, soit une simple factorielle : C = N !. Pour chaque configuration de départ, il faut un nombre minimum P de manipulations au minimum afin de trier la pile. Bien qu’encore impossible de déterminer P pour tout N, on connaît toutefois le nombre de problèmes nécessitant P manipulations, pour un nombre de crêpes N fixé.
- Pour une pile d’une crêpe (N=1), il n’y a qu’une seule configuration possible (C=1). On peut considérer que la « pile » est déjà triée.
- Pour une pile de deux crêpes (N=2), il y a deux configurations possibles (C=2) :
- la crêpe du dessus est plus petite que celle du dessous : la pile est déjà triée et ne nécessite donc aucune manipulation (P=0)
- le diamètre de la crêpe du dessus est plus large que celle du dessous : il faut retourner toute la pile en une manipulation (P=1)
- Pour une pile de trois crêpes (N=3), il y a six configurations possibles (C=6) :
- une configuration pour laquelle la pile est déjà triée, ne nécessitant aucune manipulation (P=0). On peut noter cette pile de la façon suivante : {1 ; 2 ; 3}.
- deux configurations pour lesquelles il faut une seule manipulation (P=1). Il s’agit de la pile {2 ; 1 ; 3} où il faut retourner les deux premières crêpes et de la pile {3 ; 2 ; 1} où il faut retourner la pile complète.
- deux configurations pour lesquelles il faut deux manipulations (P=2). Il s’agit des piles {2 ; 3 ; 1} et {3 ; 1 ; 2}.
- une configuration nécessitant trois manipulations (P=3). Il s’agit de la pile {1 ; 3 ; 2}.
Le tableau suivant donne le nombre de problèmes nécessitant P manipulations, pour un nombre de crêpes N donné.
Nombre P de manipulations nécessaires | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | ||
Nombre N de crêpes |
1 | 1 | ||||||||||||||
2 | 1 | 1 | ||||||||||||||
3 | 1 | 2 | 2 | 1 | ||||||||||||
4 | 1 | 3 | 6 | 11 | 3 | |||||||||||
5 | 1 | 4 | 12 | 35 | 48 | 20 | ||||||||||
6 | 1 | 5 | 20 | 79 | 199 | 281 | 133 | 2 | ||||||||
7 | 1 | 6 | 30 | 149 | 543 | 1 357 | 1 903 | 1 016 | 35 | |||||||
8 | 1 | 7 | 42 | 251 | 1 191 | 4 281 | 10 561 | 15 011 | 8 520 | 455 | ||||||
9 | 1 | 8 | 56 | 391 | 2 278 | 10 666 | 38 015 | 93 585 | 132 697 | 79 379 | 5 804 | |||||
10 | 1 | 9 | 72 | 575 | 3 963 | 22 825 | 106 461 | 377 863 | 919 365 | 1 309 756 | 814 678 | 73 232 | ||||
11 | 1 | 10 | 90 | 809 | 6 429 | 43 891 | 252 737 | 1 174 766 | 4 126 515 | 9 981 073 | 14 250 471 | 9 123 648 | 956 354 | 6 | ||
12 | 1 | 11 | 110 | 1 099 | 9 883 | 77 937 | 533 397 | 3 064 788 | 14 141 929 | 49 337 252 | 118 420 043 | 169 332 213 | 111 050 066 | 13 032 704 | 167 |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/59/Tri_de_6_cr%C3%AApes.gif/220px-Tri_de_6_cr%C3%AApes.gif)
Ce tableau, lu ligne par ligne, constitue la suite A092113 de l'OEIS.
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.
Ce tri a intéressé Bill Gates (l'un des fondateurs de Microsoft), David X. Cohen (l'un des créateurs de la série Futurama), et l'informaticien Christos Papadimitriou[2].
Sources
[modifier | modifier le code]Références
[modifier | modifier le code]- Gates et Papadimitriou 1979
- Jérôme Cottanceau, Le choix du meilleur urinoir : Et 19 autres problèmes amusants qui prouvent que les maths servent à quelque chose !, Paris, Belin, coll. « Science à plumes », , 216 p. (ISBN 978-2-7011-9766-1), chap. 19 (« À quoi servent les maths... À trier ses crêpes comme Bill Gates ? »).
- (en) Laurent Bulteau, Guillaume Fertin et Irena Rusu, « Pancake Flipping is hard », Journal of Computer and System Sciences, vol. 81, no 8, (lire en ligne).
Bibliographie
[modifier | modifier le code]Articles scientifiques
[modifier | modifier le code]- (en) William H. Gates et Christos Papadimitriou, « Bounds for Sorting by Prefix Reversal », Discrete Mathematics, no 27, , p. 47-57 (DOI 10.1016/0012-365X(79)90068-2) ;
- (en) David S. Cohen et Manuel Blum, « On the problem of sorting burnt pancakes », Discrete Applied Mathematics, vol. 61, no 2, , p. 105-120 (DOI 10.1016/0166-218X(94)00009-3) ;
Vulgarisation
[modifier | modifier le code]- Jérôme Cottanceau, Le choix du meilleur urinoir : Et 19 autres problèmes amusants qui prouvent que les maths servent à quelque chose !, Paris, Belin, coll. « Science à plumes », , 216 p. (ISBN 978-2-7011-9766-1), chap. 19 (« À quoi servent les maths... À trier ses crêpes comme Bill Gates ? »).
Liens
[modifier | modifier le code]Articles connexes
[modifier | modifier le code]Liens externes
[modifier | modifier le code]- (en) Flipping pancakes puzzle, une applet java et une discussion sur le tri de crêpes, sur cut-the-knot
- (en) The Pancake Problems par Douglas B. West
- (en) Eric W. Weisstein, « Pancake sorting », sur MathWorld