Nous sommes à un jour seulement de la Chandeleur. Alors que les Bretons s’agitent et que les Français les imitent pour confectionner les meilleures crêpes, il y a un problème auquel nous sommes tous confrontés : obtenir des crêpes de taille identique. À défaut d’atteindre cet objectif, nous nous attelons pour des raisons esthétiques à trier notre tas de crêpes de façon à les ranger en taille décroissante, de la plus large en bas de la pile à la plus petite au-dessus. Un problème simple, pensez-vous ? Eh bien pas tout à fait. Certes vous arriverez sans grande difficulté à résoudre ce problème, mais la vraie question est en combien de déplacements de crêpes ? Voilà qui fait partie des grandes énigmes algorithmiques à résoudre encore aujourd’hui, le fameux « pancake sorting » ou triage de crêpes en français. Quand l’algorithmique s’invite à la Chandeleur, ce sont les mathématiques qui trinquent !
Beaucoup d’algorithmes possèdent des composantes de tri, que ce soit dans la finance pour le choix d’actions boursières au sein d’un portefeuille d’investissement, ou encore dans la biologie pour le tri des cellules afin d’en classifier la source. De nombreux algorithmes ont été développés pour minimiser le nombre d’opérations à réaliser au cours du tri. Écrits autrement, ces algorithmes sont dimensionnés pour aller vite ! Mais il y a un problème pour lequel aucun algorithme optimal n’a encore été trouvé, c’est notre fameux problème de triage de crêpes. Le problème est le suivant : vous avez devant vous une pile de crêpes de tailles différentes. Vous devez ranger ces crêpes de la plus grande à la plus petite (située en haut de la pile) en ne réalisant qu’un seul type de mouvement (alias l’opération algorithmique) : glisser la spatule entre deux crêpes, et retourner en une fois l’ensemble des crêpes situées au-dessus de la spatule.
Casse-tête chinois
Les scientifiques cherchent ici à décrire la complexité temporelle de l’algorithme, qui traduit l’évolution du nombre d’opérations algorithmiques qu’on nomme P, en fonction du nombre de crêpes initialement dans la pile qu’on nomme N. Ils analysent donc la relation mathématique P(N). Par exemple, pour deux crêpes (N = 2), le nombre de déplacements est au mieux P = 0 (si les deux crêpes sont déjà rangées) et P = 1 le cas contraire. Pour une grande quantité de crêpes, la théorisation du nombre de déplacements optimal devient plus complexe. Depuis trois décennies, les scientifiques se cassent les dents sur un tel mystère. En 1997, puis en 2008, des chercheurs ont tout de même réussi à démontrer que ce nombre mystère était compris entre 1,07 × N et 1,64 × N. Même Bill Gates en 1979, alors étudiant à Harvard et déjà créateur de Microsoft, démontre dans un article publié dans la revue Discrete Mathematics avec Christos Papadimitriou de l’université de Berkeley en Californie, que pour N crêpes disposées aléatoirement au sein d’une pile il faut au maximum (5 × N + 5)/3 déplacements.
Un casse-tête chinois qui ne fera pas peur aux Bigoudènes. Alors que vous trierez vos crêpes ce week-end, pensez à ce problème mathématique qui n’a toujours pas trouvé son algorithme optimal. Un bol de cidre breton vous aidera peut-être à trouver la solution !