Conférence jubilaire de Donald Knuth "À l'arbre de Noël"

Pendant un quart de siècle, le grand professeur émérite de Stanford organise une conférence spéciale en décembre, «À l'arbre de Noël». À l'approche de ses 82 ans, Donald Knut a de nouveau tenu la conférence du 25e anniversaire le 5 décembre. Il a rappelé au public qu'il travaillait toujours avec diligence sur le livre qu'il écrivait depuis 57 ans.

Le livre "The Art of Programming" parmi les programmeurs est considéré comme l'une des recherches les plus complètes sur les algorithmes. Selon le site Web de l'Université de Stanford , ce livre est l'un des meilleurs travaux scientifiques du siècle. «En raison de mon horaire d'écriture chargé, je dois mener une vie d'ermite», écrit Knut sur son site Web personnel .

Par conséquent, il est doublement inhabituel de voir ce grand homme vivre.

Notre site a sa propre tradition de Noël : nous publions des critiques et des captures d'écran des récentes conférences de Knuth. En 2017, je l'ai décrit comme «rencontrer mon parent bien-aimé pour les vacances» et «une chance de voir un grand esprit vivre».

La conférence de cette année n'a pas fait exception.

Tout comme pi

La conférence de Knut a eu lieu le 5 décembre, mais n'a été publiée que le samedi 21 décembre. (Lundi, elle avait déjà obtenu plus de 2 000 vues.)


Knuth avait une autre raison d'être fier: il a terminé la conférence, tenant dans ses mains une copie du supplément qui vient d'être publié sur «l'Art de la programmation» . Il a dit que dans ce livre "beaucoup de choses intéressantes, et entre autres, cela vous permet d'apprendre plusieurs algorithmes."


La cinquième édition du quatrième volume est sortie le mois dernier.

Knut a également beaucoup aimé la conférence. "Merci à tous d'être venus", a déclaré Knut au public. "Il semble que vous ne soyez pas encore fatigué de moi", a-t-il plaisanté, ajoutant, "nous verrons si quelqu'un viendra l'année prochaine ..."

Mais Knut a préparé quelque chose de spécial pour la conférence de cette année. Il a montré au public comment, pendant un demi-siècle, a étrangement intégré les chiffres pi dans différents exercices de son livre, encore et encore et encore. Knut a déclaré à ses auditeurs qu'il avait recherché l'intégralité du texte de son livre «The Art of Programming» à l'aide de l'outil Linux egrep , et trouvé jusqu'à 1700 occurrences du mot «pi», c'est-à-dire tant qu'il apparaît environ deux fois pour toutes les cinq pages du livre. Il pense que l'utilisation de pi dans les exemples permet aux lecteurs de s'assurer que les algorithmes fonctionnent vraiment même pour un ensemble de chiffres choisi arbitrairement.

Bientôt, son discours s'est transformé en une sorte d'attraction intellectuelle - il a partagé d'autres faits liés au pi, qui ont souvent surpris et parfois stupéfaits.

Il a commencé par montrer la couverture de The Numerology of Dr. Mathématicien Matrix Martin Gardner, et a montré sa table des 32 premiers chiffres décimaux pi. Knut a rappelé comment il l'avait inclus dans l'un des premiers volumes de «The Art of Programming» et a cité la déclaration de Gardner selon laquelle l'interprétation correcte des chiffres pi transmet toute l'histoire de l'humanité. "Dans un sens, on peut dire que le but principal de ma vie est d'interpréter correctement les signes pi", a déclaré Knut au public. "Que pourrait-on faire de plus important dans votre vie?"

Cependant, la description de la vidéo indique que "la conférence parle des nombreuses interprétations de ces signes, à la fois bonnes et mauvaises".

Knut a ensuite partagé une règle mnémonique pour se souvenir des premiers chiffres de pi. Vous pouvez obtenir chacun de ses premiers chiffres - 3.14159265358979 - en comptant le nombre de lettres dans chaque mot de la phrase:

"Comment j'ai besoin d'un verre - alcoolisé, bien sûr - après les conférences intenses impliquant la mécanique quantique." [env. trans.: analogique en russe - "Comment je veux et veux me foutre de moi après ces rapports stupides menant à une grave dépression".]

Il a ensuite présenté un livre qu'il a qualifié de "l'une des plus grandes réalisations de la littérature ULIPO " - un type de littérature dans laquelle les écrivains suivent des restrictions strictes (et parfois mathématiques). Comment ça s'appelle?

Not A Wake: A Dream Incarning (Pi )'s Digits Fully For 10000 Decimals


Le nombre de lettres dans chaque mot de ce nom correspond également exactement à la séquence de chiffres pi. Knut a cité la couverture arrière: «C'est une pièce de théâtre, une histoire, des fantasmes en vers modernes et d'autres écrits, qui suivent sans exception les motifs mathématiques des manuels scolaires.» Cette phrase est également constituée de mots dont la longueur correspond aux chiffres de pi. «L'auteur du livre», ajoute Knut, «atteint jusqu'à 10 000 chiffres.» Puis il a lu la première page poétique du livre:

"Maintenant je tombe, une banlieue fatiguée dans un liquide sous les arbres
À la dérive le long de forêts mijotant de rouge au crépuscule sur l'Europe ... "


Le chiffre 0 est indiqué par des mots de dix lettres et 11 peut être représenté par des mots de onze lettres. "L'auteur a appelé cette langue Pi-lish " , a déclaré Knuth en riant. Qu'en est-il de la célèbre séquence de six neuf de suite? Le poète a écrit:

"Sans reproche, sans effusion de sang, sans culpabilité, sans cesse, sans limite, sans limites."

Le public a applaudi et Knut a continué à lire le livre. Il contient des essais, des poèmes courts, des épigrammes et même un script avec des dialogues pour un film épique de science-fiction appelé Zompyr Chronicle . Chaque mot a une longueur exactement égale au signe pi correspondant.

"Cependant, le puzzle de mots croisés est devenu une véritable voltige."

Attends une minute, quoi? Oui, en respectant strictement la longueur des mots donnés par chaque pi, l'une des pages du livre se transforme soudain en un indice pour un jeu de mots croisés. Ceci est suivi par le puzzle de mots croisés lui-même, où vous devez entrer les réponses. Son nom indique clairement que les mots de réponse sont les noms de livres avec les premières lettres des mots réarrangés. En effet, les indices et les réponses sont cryptés avec le livre classique de Walt Whitman "Greaves of Lass" et le roman révolutionnaire de James Joyce, "Winnegan's Fake".

Et vers la fin du livre, il y a même le parfait sonnet shakespearien ...

Knuth a ensuite admis que dans l'index du volume 4A de son propre livre, il y avait une référence particulièrement délicate au nombre pi: «vous devez comprendre à quoi ressemble la page 382 à pi» ...

Bonne réponse: +00 ++ - +++ - 000-

C'est pi dans «l'un des systèmes de nombres les plus étonnants» - un système de nombres ternaire équilibré, dans lequel les caractères 0, + et - sont utilisés pour représenter les nombres dans un système de base 3.

Énigmes avec pi

Knuth s'est ensuite tourné vers les galères préliminaires de la cinquième édition du quatrième volume qui vient d'être publiée. Il a dit que sur n'importe quelle page, vous trouverez probablement un puzzle, car "il s'est avéré que les types d'algorithmes décrits ici sont mieux illustrés par leur relation avec les puzzles". Et l'accent dans le livre n'est pas sur la façon de résoudre des énigmes, mais sur la façon de les créer . À titre d'exemple, il a montré au public son puzzle Sudoku, dans lequel les nombres finis étaient 3, 1, 4, 1, 5, 9 ...

"J'ai réussi à adapter les 32 premiers caractères pi ici."


Est-il possible de créer plus de sudoku qu'un ches avec des nombres de 32 pi? Non, et il y a une raison simple - le 33ème symbole pi est zéro, le seul chiffre non utilisé dans le sudoku.

Ensuite, Donald a montré la couverture d' Exotische Sudoku , où non seulement les décharges pi étaient utilisées pour le sudoku, mais elles étaient également disposées en cercle . Ce livre est entièrement composé d'énigmes sudoku, où les signes pi sont utilisés comme indices, sous réserve d'une condition supplémentaire - deux lignes diagonales de neuf carrés dans la solution doivent également contenir chaque chiffre une fois.


Knut a également montré des exemples de deux puzzles impliquant des pièces d'échecs. Dans la solution Knight Sudoko, chaque ligne, colonne et carré contient exactement trois chevaliers d'échecs. Les indices ne montrent que certains des chevaux avec un nombre indiquant combien d'autres chevaux ils peuvent attaquer. Bien sûr, Knut a créé un puzzle dans lequel ces nombres sont 3, 1, 4, 1, 5 ...

Il existe également un casse-tête similaire utilisant des éléphants , bien sûr, les indices qu'il contient constituent également le nombre pi.

Knut s'est ensuite tourné vers les puzzles KenKen, dans lesquels les nombres de chaque ensemble de carrés connectés sont combinés, donnant la solution souhaitée (en utilisant un opérateur mathématique donné). Dans la version Knuth, les indices sont 3, 14, 15, 9, 2 et 6 ... Il y a aussi le puzzle Kakuro - une sorte de puzzle de mots croisés avec des nombres; Knut a suggéré que les lecteurs créent une tâche où les réponses seraient 31, 41, 59, 26, 53, 58, 97. Dans le puzzle Hidato, les nombres consécutifs sont situés sur la grille, mais uniquement dans les carrés adjacents (horizontal, vertical ou diagonal). Knut a suggéré que les lecteurs créent exactement le même puzzle avec des chiffres de pi.

C'est un excellent moyen de démontrer que les algorithmes fonctionneront réellement avec n'importe quel ensemble de nombres, même 3.141592. En guise de conclusion grandiose, Knut a probablement parlé du puzzle le plus intéressant de tous - le «mur chinois» (slitherlink). Les solveurs doivent tracer une ligne continue reliant les points de la grille, touchant le nombre de côtés du "carré" de points spécifié par le nombre carré. Le livre de Knut pose une question aux lecteurs - quelle est la surprise d'une solution spécifique au «mur chinois»?

Lorsque Knut a parlé de la solution étonnante au puzzle, il a mérité beaucoup d'applaudissements.


«Merci beaucoup», a-t-il déclaré solennellement au public, «et joyeux Noël».