Tri de crêpes
Un article de Wikipédia, l'encyclopédie libre.
Le tri de crêpes (de l'anglais pancake sorting) ou encore tri à la mode bretonne 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.
Sommaire |
[modifier] Principe
Le problème consiste à trier une pile de crêpes suivant l'ordre de taille. Pour cela une seule opération est autorisée, qui consiste à retourner un sommet de la pile, cette opération prend un seul paramètre, à savoir la taille du sommet que l'on souhaite retourner. Ce paramètre varie entre deux et la taille de la pile (retourner la crêpe du haut ne change pas la pile).
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.
[modifier] Intérêts
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.
L'autre intérêt de ce tri, ce sont les personnes s'y étant intéressées : Bill Gates (Microsoft) ou encore David X. Cohen (un des créateurs de la série Futurama).
[modifier] Références
- Gates, W. et Papadimitriou, C. “Bounds for Sorting by Prefix Reversal”, Discrete Mathematics, n° 27, pages 47-57, 1979 lire en ligne.
- Cohen D.S. et Blum, M. “On the problem of sorting burnt pancakes”, Discrete Applied Mathematics, n° 61, pages 105-120, 1995.
[modifier] Liens externes
- (en) Cut-the-Knot: Flipping pancakes puzzle, un applet Java et une discussion sur le tri de crêpes.
- (en) Douglas B. West's “The Pancake Problems”
- (en) Pancake sorting, sur le site Mathworld
