Bill Gates a travaillé à trier les crêpes

Proposé par
le

Bill Gates a trouvé une solution au problème d'optimisation mathématique pancake sorting, ou triage de crêpe en français. Le problème consiste à trier des crêpes de la plus petite à la plus grande avec pour seule opération possible celle d'insérer une spatule dans la pile et la retourner. Sa solution fut tellement efficace qu'elle n'a été améliorée que 30 ans plus tard.


Tous les commentaires (37)

Un pancake n'est pas une crêpe. Il n'y a pas vraiment de traductions en français donc il faudrait aussi appeller ça un pancake.

Ca n'a aucune importance dans ce cas vu que c'est une métaphore mais je tenais a le préciser.

Posté le

android

(6)

Répondre

a écrit : Ah, bonne référence, le voyageur de commerce ! J'en profite d'ailleurs pour rebondir sur les exploitations de la chose. C'est en fait (de ce que j'ai pu en lire là : fr.wikipedia.org/wiki/Probl%C3%A8me_du_voyageur_de_commerce) un modèle d'algorithme décisionnel "simple".

Dans le lien, ils donnent l'exemple d'une fraiseuse automatique qui optimise le perçage de plusieurs trous dans une pièce (donc gain de temps de cycle, donc plus de pièces produites pour pas un rond d'investissement, c'est un peu le Graal). Il semblerait par ailleurs que ça soit utilisé en génétique, aussi improbable que ça puisse paraître...

Je trouve que ça illustre le fait que la réponse universelle à "Ca sert vraiment à rien" doit se rapprocher de "Tu manques d'imagination".

(Edit à la relecture : Je dis pas ça pour toi xiele, hein !!!)
Afficher tout
Ca manque pas d'imagination, mais de connaissances c'est clair.
Il est difficile pour le commun des mortels (comme moi) de comprendre à quoi peut servir un algorithme d'empilage de crêpes dans notre monde actuel, faut pas nous en vouloir, on fait ce qu'on peux pour comprendre mais dès fois ça nous dépasse tellement que ça nous parait absurde.

Quand à dire que "ça sert à rien" comme tu le souligne très justement et où je ne peux qu'approuver ton commentaire: aucune connaissance est inutile, et ceux qui disent le contraire sont certainement les mêmes qui se disent: "Ma voiture démarre parce que j'ai tourné la clé dans le contact" sans chercher plus loin. ;)

a écrit : Un pancake n'est pas une crêpe. Il n'y a pas vraiment de traductions en français donc il faudrait aussi appeller ça un pancake.

Ca n'a aucune importance dans ce cas vu que c'est une métaphore mais je tenais a le préciser.
Désolé, mais un pancake, c'est une crêpe. Épaisse, mais c'est une crêpe quand même. La recette est exactement la même, seule l'épaisseur change.
Oui, c'est totalement HS, mais ce qui est dit au dessus c'est comme dire que du pain de mie n'est pas du pain, et donc je proteste énergiquement ^^

a écrit : Désolé, mais un pancake, c'est une crêpe. Épaisse, mais c'est une crêpe quand même. La recette est exactement la même, seule l'épaisseur change.
Oui, c'est totalement HS, mais ce qui est dit au dessus c'est comme dire que du pain de mie n'est pas du pain, et donc je proteste énergiquement ^^
Un autocar ca à des roues, un moteur, un volant. C'est comme une voiture, mais en plus grand... mais c'est un autocar!
Pareil pour les crêpes ;)

Ces conneries ça m'a donné envie. Alors des oeufs, farine, lait.... ET NUTELLA. Et on les mangera dans le désordre. Trop compliqué ces maths et algorithmes. J'arrive à peine à faire du traitement de texte sans planter mon ordi, alors la taille des crêpes....

a écrit : L'explication n'est pas très claire, il s'agit en fait d'un problème assez simple et ludique:
www-irem.ujf-grenoble.fr/spip/IMG/pdf/fiche_prof_crepier_psychorigide.pdf
Je ne pense pas que ce tri soit vraiment utilisé en pratique sauf exception, néanmoins c'est un bon moyen de
présenter l'algorithmique aux plus jeunes!
Bill Gates est un homme d'affaires brillant, mais en tant qu' informaticien il s'agit de sa seule publication (je n'ai pas de source) d'ailleurs co-signée par d'autres grands noms (cf source Wikipedia).
Afficher tout
Je n'ai pas de certitudes, mais je pense que si, c'est utilisé.

Le retournement d'une liste est infiniment plus rapide à faire que les successions de lectures-écritures nécessaires pour faire un tri.
Plus grand monde ne sait réellement comment sont codés les algorithmes de tris ultra-optimisés utilisés aujourd'hui, mais ça ne m'étonnerai pas qu'ils reposent sur ce genre de technique.

:)

a écrit : Je suis le seul à n'avoir rien compris?... C'est un triage algorithmique, c'est a dire une manière logique traduisible en langage "ordinateur". Le tri est rapide et efficace, car une seule action et un seul passage sont faits.

Vois ca comme une boule de noeud, qui se demelerait en un seul coup de peigne, avec cette méthode de tri, au lieu de devoir procéder mèche par mèche.

Source : Une informaticien aux cheveux longs. Salut.

Posté le

android

(9)

Répondre

a écrit : Non non t'inquiète, j'ai rien pigé aussi au début^^
Donc le but est de retourner des crêpes avec une spatule pour les ranger par ordre de taille? Encore un truc de matheux, ca me rappelle ce casse tête à la c..:, le hanoi...

Enfin, je suis certain qu'un jour il y aura une application p
ratique à ce... ce quoi? Programme? Afficher tout
C'est une méthode de tri optimisée, c'est déjà bien utilisé dans beaucoup de langages normalement :)

Posté le

android

(3)

Répondre

a écrit : Un autocar ca à des roues, un moteur, un volant. C'est comme une voiture, mais en plus grand... mais c'est un autocar!
Pareil pour les crêpes ;)
un baba au rhum, c'est un gâteau, un quatre quart c'est aussi un gâteau.
Tu voulais dire quoi déjà? Ah oui, que le pancake n'est pas une crêpe alors que les ingrédients sont exactement les mêmes, que ça se cuit de la même façon, sauf que c'est plus épais.
Okay.

a écrit : Ces conneries ça m'a donné envie. Alors des oeufs, farine, lait.... ET NUTELLA. Et on les mangera dans le désordre. Trop compliqué ces maths et algorithmes. J'arrive à peine à faire du traitement de texte sans planter mon ordi, alors la taille des crêpes.... essaie avec un peu de sucre et du jus de citron, ça change de la crêpe au nutella ;)

a écrit : C'est une méthode de tri optimisée, c'est déjà bien utilisé dans beaucoup de langages normalement :) Je veux bien te croire, mais vraiment j'y comprends absolument rien^^

C'est pas grave hein, ça fonctionne, c'est le principal ;)

a écrit : Il ne serait pas plus simple de préparer toutes ses crêpes avec la même poêle ? Toi, tu n'as jamais fait de crêpe !!!

Posté le

android

(1)

Répondre

De toute façon il n'y a que ce genre de mec qui se posent ces questions là et surtout qui finissent par les résoudre qui entrent dans l'Histoire.. Regarde un peu autour de toi tous les mecs chelou, il y a peut être un génie parmi eux.

a écrit : Non non t'inquiète, j'ai rien pigé aussi au début^^
Donc le but est de retourner des crêpes avec une spatule pour les ranger par ordre de taille? Encore un truc de matheux, ca me rappelle ce casse tête à la c..:, le hanoi...

Enfin, je suis certain qu'un jour il y aura une application p
ratique à ce... ce quoi? Programme? Afficher tout
Cela était effectivement un problème théorique au départ, mais qui trouve une application en génétique.

En effet, les gènes évoluent souvent par de minuscules mutations, mais parfois quelque chose de plus radical se produit et des gènes entiers sont inversés : nous parlons ici de la technique de l'inversion des deux plaques, car cela peut se produire n'importe où dans le chromosome.

plus.maths.org/content/pancakes-mice-and-men

« Philanthrope »… le tout est de s’en convaincre.
Si tu donner un milliards aux restos du cœur ou à La Croix Rouge tu es philanthrope car tu ne pourras rien recevoir en retour (sauf un ou deux repas gratos bien sûr)
Quand tu finances l’Oms tu diriges la politique mondiale en matière de santé.
C’est bon là où faut encore développer ?