Cette année, 2022 marque le 60e anniversaire de ce jour fatidique de 1962 où Donald Knuth, 24 ans, a commencé à écrire «L’art de la programmation informatique.” Approchant maintenant de son 85e anniversaire, Knuth est devenu presque une légende dans le monde de la programmation informatique – et il écrit toujours des volumes supplémentaires pour son analyse massive des algorithmes.
Mais chaque année, juste au moment de Noël, il y a une autre tradition. Knuth donne une conférence spéciale “à des non-spécialistes” pour un petit public à l’Université de Stanford (où Knuth est professeur émérite) et un public plus large en ligne. À cause de la pandémie, cela fait trois ans que Knuth n’a pas pu honorer cette tradition.
Le public de cette année a donc accueilli Knuth avec un sentiment d’anticipation supplémentaire.
La magie des arbres
Penché sur un bloc-notes (qui était projeté sur un écran derrière lui), Knuth a commencé la 26e conférence annuelle de Noël en soulignant que le sujet de la soirée était caché à la vue de tous depuis deux décennies. Pendant les 20 premières années, ils les avaient appelées les conférences de «l’arbre de Noël», car «les arbres sont l’une des choses les plus importantes pour un informaticien. Et chaque année, j’ai appris au moins deux nouvelles choses intéressantes sur les arbres… »
Il y a environ cinq ans, ils avaient changé le nom en “Conférences de Noël” – mais le problème n’était pas que les arbres avaient cessé d’être intéressants. “J’apprends encore des choses intéressantes sur les arbres chaque année. Mais ils deviennent de plus en plus difficiles à expliquer au grand public !
Ainsi, la conférence triomphale du « retour aux sources » de cette année inclurait en effet des arbres – en particulier un phénomène que Knuth décrit comme des « arbres jumeaux », ainsi que des permutations de Baxter et des plans d’étage. Knuth a noté qu’ils sont tous des sujets abordés dans le dernier volume de L’art de la programmation informatiqueavant de rappeler en plaisantant au public que son livre est un excellent cadeau de Noël.
Il a ajouté en riant que “Du point de vue d’un conférencier, c’est toujours mieux quand vous avez quelque chose dont vous aimez parler.”
Knuth a commencé par présenter au public des arbres binaires – une structure de données de branchement familière où, au fur et à mesure que vous progressez, chaque nœud peut avoir jusqu’à deux nœuds inférieurs (un nœud «enfant» gauche et un nœud droit). Mais ensuite, il a montré au public “l’un de mes algorithmes préférés de tous les temps, depuis plus de 50 ans… l’insertion d’arbre binaire”. C’est là que les données sont insérées dans la fourche gauche si elle est inférieure à la valeur de la clé, et dans la fourche droite si elle est supérieure.
Pour générer une séquence vraiment aléatoire, il laissait les membres du public crier où les chiffres devaient apparaître dans une séquence de huit chiffres, puis convertissait ce fouillis en un arbre binaire bien rangé sur son bloc-notes.
Mais ensuite, en parcourant ces mêmes nombres dans l’ordre inverse, Knuth a produit comme par magie un deuxième arbre binaire complémentaire – un où il n’y a pas de chevauchement lorsque vous écrivez les sous-nœuds de chaque nœud parent, pour les deux arbres, sur un seul graphique.
Knuth l’a démontré en utilisant de l’encre rouge pour écrire les sous-nœuds d’un arbre, puis de l’encre verte pour les sous-nœuds de l’autre :
Rare? À peine. Knuth a partagé le calcul surprenant selon lequel il existe plus de 10 000 arbres jumeaux à huit nœuds. “Cet algorithme d’insertion d’arbres est quelque chose avec lequel j’ai joué depuis le milieu des années 1960”, a déclaré Knuth au public étonné “et je l’ai utilisé dans un zillion de programmes informatiques.
“Mais je n’ai jamais – il a fallu 50 ans avant que je comprenne que cela me donnait aussi des arbres jumeaux en même temps!”
Petits et Grands
La curiosité mathématique suivante était la permutation de Baxter, une sorte de série de nombres pour laquelle Knuth offrait une définition magnifiquement simple. Si les nombres au-dessus des nombres fixes k et M + 1 sont des “grands” et les nombres en dessous sont des “petits”, puis dans les permutations de Baxter, “je ne peux pas avoir un grand suivi d’un petit”. (Et l’inverse est également vrai. Si dans la séquence k est précédé du plus grand k + 1puis “Je ne peux pas avoir un petit suivi d’un gros”.)
Knuth a fourni un exemple – mais a ensuite joué avec les ramifications.
Inverser l’ordre des nombres produit toujours une autre Permutation de Baxter. Et vous pouvez également produire une autre permutation de Baxter simplement en ajoutant une constante à chaque nombre de la séquence. Si cette constante est égale ou supérieure au nombre le plus élevé de votre séquence, vous pouvez alors produire une permutation de Baxter encore plus longue en ajout cette séquence sur votre séquence d’origine. (Ou même par pré– en attendant cette séquence.)
Tous ces scénarios conservent la propriété unique originale de la séquence de Baxter, a réitéré Knuth au public. Peu importe la paire de nombres séparés par un que vous choisissez pour votre test, “Tous les petits gars vont tous venir en premier, et les gros gars plus tard.”
Knuth a présenté le plus petit possible non-Baxter permutations — 3, 1, 4,2. Il l’a appelée « la mutation pi », puisqu’il s’agit d’une approximation arrondie de pi à quatre chiffres.
Au fil des ans, Knuth a découvert que lors du test de conjectures sur les permutations, “si la conjecture est fausse, elle échoue presque toujours à la mutation pi”. L’inverse de la séquence n’est pas non plus une permutation de Baxter – les deux seules séquences défaillantes (sur 24 séquences possibles).
Trois beaux algorithmes
Le dernier sujet de la soirée était les plans d’étage – une répartition (ou «décomposition») d’apparence familière d’un rectangle en sous-rectangles plus petits. (Ou, ceci étant un plan d’étage, en “pièces”.) En aparté, Knuth a souligné que ce type de modélisation devient important lors de la création de puces en silicium – où les “pièces” deviennent des modules ou des portes logiques.
Et puis il a posé une question provocante : qu’est-ce que cela signifie que deux plans d’étage soient identiques ?
Knuth a réorganisé l’ordre de ses noms de coordonnées sur ses axes X et Y, puis a dessiné un autre plan d’étage où les rectangles ont conservé leur même position les uns par rapport aux autres. (“Je ferais aussi bien de tout écrire, parce que ça se passe sur Internet”, a plaisanté Knuth à un moment donné.)
Ce plan d’étage particulier a suivi la condition Tatami – il n’y a pas de point «quatre coins» où quatre rectangles différents se rencontrent en un seul point. Knuth a montré d’autres façons de schématiser le plan d’étage – ce qui l’a amené à sa grande finale. “Qu’est-ce que cela a à voir avec les arbres jumeaux et les permutations de Baxter?”
Étonnamment, lors de l’utilisation de cette dernière méthode de création de diagrammes, tous séquence de nombres qui est une permutation Baxter vous donne un plan d’étage valide. Et parcourir cette même séquence, d’abord en avant puis en arrière, vous donne toujours une paire d’arbres binaires jumeaux qui – vous l’avez deviné – sont à nouveau parfaitement complémentaires. (Il n’y a pas de chevauchement lorsque vous écrivez les sous-nœuds de chaque nœud parent pour les deux arbres sur un seul graphique.)
“Vous me donnez une permutation Baxter, je peux vous dire quel est le plan d’étage. Vous me donnez un plan d’étage, je peux vous dire ce que sont les twintrees, et vous me donnez un twintree, je peux vous dire quelle est la permutation unique de Baxter qui le génère !”
Comme l’a expliqué Knuth sur sa page web“Trois concepts fascinants, qui semblent au premier abord totalement indépendants les uns des autres, sont en fait en correspondance biunivoque, via trois beaux algorithmes.”
Knuth a écrit des programmes qui effectuent toutes les opérations – comme un programme qui convertit les permutations de Baxter en plans d’étage. (“Si vous lui donnez une permutation qui n’est pas une permutation Baxter,” dit Knuth au public, “il se moque de vous et dit ‘Dommage. Vous perdez. Ce n’est pas une permutation Baxter!” ) Il a même utilisé des tubes Unix pour envoyer la sortie d’un programme comme entrée pour le suivant – et “je récupère, bien sûr, celui avec lequel j’ai commencé.”
> baxter-to-floorplan | plan-au-twintree-ttform | twintree à baxter
Après 60 ans d’écriture et une vie d’exploration d’algorithmes mathématiques, Knuth a levé les yeux pour voir qu’il avait parlé 10 minutes après l’heure prévue. Et puis il a plaisanté en disant qu’il était content. “Je m’attendais à avoir 20 minutes de plus.”
“Merci d’avoir écouté, et je suis prêt à répondre à vos questions.”