Tri de crepes
- Tri de crepes
-
Tri de crêpes
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.
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.
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).
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.
Liens externes
Portail de l’informatique
Catégorie : Algorithme de tri
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Tri de crepes de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Tri de crêpes — 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… … Wikipédia en Français
Liste Des Algorithmes — Sommaire 1 Liste par catégories 1.1 Compression de données 1.2 Tri 1.2.1 Algorithmes en temps quadratique … Wikipédia en Français
Liste des algorithmes — Sommaire 1 Liste par catégories 1.1 Compression de données 1.2 Tri 1.2.1 Algorithmes en temps quadratique … Wikipédia en Français
Single-Handed Trans-Atlantic Race — The Single handed Trans Atlantic Race, or STAR, is an east to west yacht race across the North Atlantic. When inaugurated in 1960, it was the first single handed ocean yacht race; it is run from Plymouth to the USA, and is held every four years.… … Wikipedia
Yolato — Infobox Company company name = Yolato company company type = Private company slogan = Yolato Healthy Gelato foundation = Edgewater, NJ location = Edgewater, NJ, USA Manhattan, NY, USA key people = Reggie Bear Kim, Mascot industry = Restaurants… … Wikipedia
Brittany — Infobox Settlement name =Brittany official name = other name = native name = Breizh nickname = settlement type = total type = motto = imagesize = image caption = imagesize = image caption = flag size = image seal size = image shield = COA fr… … Wikipedia
La Route du Rhum — Route du Rhum Plaque, à la pointe du Grouin, commémorant la création de la Route du Rhum par Michel Etevenon … Wikipédia en Français
Route du Rhum — Port de départ et port de destination Type : En solitaire, sans escale e … Wikipédia en Français
Route du rhum — Plaque, à la pointe du Grouin, commémorant la création de la Route du Rhum par Michel Etevenon … Wikipédia en Français
Top Chef (season 3) — Top Chef: Miami Judges Ted Allen and Gail Simmons (center left), hosts Padma Lakshmi and Tom Colicchio (center right), along with the chefs participating in Top Chef s third season Winner Hung Huynh Original run June 13, 2007 … Wikipedia
