Siloda Valley Yoda

Donald Knuth, un maître des algorithmes, réfléchit à plus de 50 ans de travail sur sa création principale, le livre «L'art de la programmation», qu'il continue de compléter

Donald Knut à son domicile de Stanford, en Californie. Un perfectionniste effrayant, a nommé une récompense pour avoir trouvé des erreurs dans ses livres.

Depuis un demi-siècle, l'informaticien de Stanford, Donald Knuth, qui rappelle un peu Yoda - bien qu'il mesure 193 cm et porte des lunettes - a occupé une position dominante en tant que professeur spirituel dans le domaine des algorithmes.

Il est l'auteur de L'Art de la programmation, une monographie qu'il continue d'écrire à ce jour, en 4 volumes, et qui est l'œuvre de sa vie. Le premier volume a été publié en 1968, et tous les volumes ensemble (vendus dans un ensemble de 250 $ [ou 12 500 ₽ / environ. Trad.]) En 2013 ont été inclus dans la liste des livres qui ont formé le siècle dernier de la science, compilée par American Scientist. Il comprend également l'édition spéciale de l'Autobiographie de Charles Darwin, le livre de Tom Wolf « Guys What You Need! », Le livre de Rachel Carson « Silent Spring » et les monographies d'Albert Einstein, John von Neumann et Richard Feynman.

L '«Art de la programmation», imprimé à plus d'un million d'exemplaires, est une bible dans son domaine. «Cela ressemble à une vraie Bible - elle est très longue et complète; il n'y a pas d'autres livres aussi complets », explique Peter Norvig, directeur de la recherche chez Google. Après 652 pages, le volume se termine par une citation au dos d'un livre de Bill Gates: "Si vous pouvez lire le livre en entier, envoyez-moi votre CV."

Il s'ouvre sur un passage de la collection de recettes McCall:

Voici un livre que vous avez demandé de publier en milliers de vos lettres. Il nous a fallu des années pour tester et revérifier d'innombrables recettes afin de vous proposer uniquement le meilleur, intéressant et idéal.

Le livre répertorie les algorithmes, les recettes qui alimentent l'ère numérique - bien que, comme le Dr Knut aime le souligner, des algorithmes puissent également être trouvés sur des tablettes babyloniennes de 3800 ans. C'est un algorithmiste profondément respecté; certains des motifs les plus importants portent son nom, par exemple, l'algorithme Knut - Morris - Pratt pour trouver une sous-chaîne dans une chaîne. Il a été inventé en 1970 et trouve toutes les occurrences d'une séquence de lettres donnée dans le texte - par exemple, lorsque vous appuyez sur Ctrl-F pour rechercher un mot dans un document.

Le Dr Knut a maintenant 80 ans et il s'habille généralement comme il était quand il était un jeune geek quand il commençait à peine cette odyssée: un T-shirt à manches longues crochets sous un T-shirt à manches courtes et un jean - au moins à cette période de l'année. À cette époque, il écrivait des programmes en code machine, jouait avec des zéros et des uns.

"Knut a clairement indiqué que le système peut être compris jusqu'au niveau des codes machine", a déclaré le Dr Norvig. Aujourd'hui, lorsque les algorithmes contrôlent (et interfèrent) avec nos vies, le programmeur moyen n'a pas le temps de creuser dans le désordre binaire; il travaille avec des hiérarchies d'abstraction, avec des couches de code - et souvent avec des chaînes de code empruntées aux bibliothèques. Mais l'élite des programmeurs tombe parfois aux niveaux les plus bas.

"Chez Google, nous collectons parfois simplement le code de ce que nous avons", a déclaré Norvig lors d'une réunion de l'équipe Google Trips à Mountain View. «Et parfois, lorsque vous devez servir des milliards d'utilisateurs, vous devez le faire efficacement. Une amélioration de 10% de l'efficacité peut se transformer en milliards de dollars, et pour atteindre ce dernier niveau d'efficacité, vous devez comprendre ce qui arrive à ses fondements mêmes. »


Le Dr Knut à California Tech, où il a obtenu son doctorat en 1963.

Ou, comme Andrei Broder, un célèbre scientifique de Google et l'un des anciens étudiants de Knuth, l'a expliqué lors de la réunion: «Nous avons besoin d'une base théorique pour notre travail. Nous n'avons pas besoin d'algorithmes frivoles, maladroits et de second ordre. Nous ne voulons pas que d'autres algorithmistes disent: "Oui, vous êtes des idiots."

Lancée en 2016, l'application Google Trips est un algorithme de voyage pour le divertissement touristique toute la journée. L'équipe a travaillé sur " maximiser la qualité des pires jours " - par exemple, l'algorithme devrait éviter d'avoir à envoyer plusieurs fois l'utilisateur aux mêmes endroits pour explorer des sites différents. Ils ont été inspirés par un algorithme vieux de 300 ans inventé par le mathématicien suisse [ainsi que allemand et russe] Leonhard Euler, qui voulait tracer un chemin à travers la ville prussienne de Königsberg [aujourd'hui Kaliningrad], en traversant tous ses sept ponts une seule fois. Knut aborde le problème classique d'Euler dans le premier volume de son traité. Il a une fois appliqué la méthode Euler pour programmer une machine à coudre contrôlée par ordinateur.


Suivre la doctrine de Knut aide à éviter l'idiotie. Il est connu pour avoir introduit le concept de «programmation littéraire», soulignant l'importance d'écrire du code que non seulement les ordinateurs mais aussi les gens peuvent lire - un concept qui semble aujourd'hui quelque chose de démodé. Knut a même affirmé que certains programmes informatiques peuvent être considérés comme des œuvres littéraires, avec les poèmes d'Elizabeth Bishop et le roman American Pastoral de Philip Roth digne du prix Pulitzer.

Il est également connu pour son perfectionnisme. Randal Munroe, l'auteur des dessins animés xkcd et Thing Explainer, a d'abord entendu parler de Knut par des programmeurs qui ont mentionné le prix qu'il avait promis de payer à toute personne ayant trouvé une erreur dans l'un de ses livres. Comme le rappelle Monroe, "les gens ont parlé de recevoir un tel chèque comme s'il s'agissait d'un Nobel d'informatique".

Les normes exigeantes de Knut, à la fois littéraire et le reste, peuvent expliquer pourquoi l'œuvre de toute sa vie est loin d'être terminée. Il a discuté avec Sergey Brin, co-fondateur de Google et de son ancien étudiant, si Brin terminerait son doctorat avant que Knut ne termine sa monographie.

Algorithme de l'aube

À l'âge de 19 ans, Knut a publié son premier ouvrage technique, «Le système potentiologique des poids et mesures » dans le magazine Mad [C'était un magazine humoristique, et potrebibi est le mot polonais utilisé en anglais pour désigner l'absurdité. Par exemple, dans son travail, Knut a introduit une nouvelle mesure de longueur d'un potrecybi, égale à l'épaisseur du 26ème numéro du journal / env. trad.]. Il est devenu un spécialiste de l'informatique avant même l'avènement de l'informatique, étudiant les mathématiques dans l'établissement d'enseignement, qui s'appelle maintenant l'Université Keyes de la Western Reserve Region. Il a étudié des programmes sélectionnés écrits pour l'ordinateur central de l'école IBM 650, un ordinateur décimal et, rencontrant des inexactitudes, les a réécrits et le manuel utilisé en classe. Comme passe-temps, il a calculé des statistiques pour une équipe de basket-ball et a écrit un programme qui les a aidés à gagner sa ligue, grâce auquel le célèbre journaliste de télévision Walter Cronkite a même tourné un reportage télévisé sur lui appelé "Electronic Trainer".


Pendant les vacances d'été, Knut a gagné plus d'argent que ses professeurs dans l'année en créant des compilateurs. Le compilateur est comme un traducteur, il transforme un langage de programmation de haut niveau (qui rappelle l'algèbre) en un langage de bas niveau (parfois c'est un code binaire mystérieux), et, idéalement, améliore le programme dans le processus. En informatique, l'optimisation est un art, qui se reflète dans un autre énoncé de Knuth: "L'optimisation prématurée est la racine de tous les maux."

En conséquence, Knut lui-même est devenu un compilateur, découvrant accidentellement un nouveau domaine, qu'il a appelé plus tard «analyse des algorithmes». L'éditeur l'a engagé pour écrire un livre sur les compilateurs, mais le projet s'est transformé en un livre qui recueille tout ce qu'il savait sur la façon d'écrire des programmes pour les ordinateurs - en un livre sur les algorithmes.


Knut, en 1981, étudiait le numéro de 1957 de Mad Magazine, qui publiait son premier article technique.


L'art de la programmation, volumes 1-4.

«Au début de la Renaissance, il y avait déjà des doutes sur l'origine de ce mot», commence le livre. "Les premiers linguistes ont essayé de comprendre son origine en créant des combinaisons telles que algiros [morbide] + arithmos [nombre]." En fait, poursuit Knut, ce nom est apparu en l'honneur de l'auteur persan du manuel du 9ème siècle, Abu Abdullah Muhammad ibn Musa al-Khwarizmi, dont le nom dans le disque latin a commencé à ressembler à "Algorithm". Knut, qui ne s'est jamais contenté de demi-mesures, s'est rendu en pèlerinage en 1979 dans la patrie d'al-Khwarizmi, en Ouzbékistan [ plus précisément, il a participé à une conférence à Urgench / env. perev. ].

Dès le début, Knut a voulu écrire un livre. Bientôt, le Big Bang s'est produit en informatique, alors il a révisé son projet, le divisant en sept volumes. Maintenant, il publie des sous-volumes ou des numéros. Le prochain «Volume 4, numéro 5», qui, entre autres, décrit des choses comme le «retour en arrière» et les «liens de danse», devait être publié en 2018. Cependant, il a été retardé jusqu'en avril, car l'auteur trouve constamment de plus en plus de nouvelles tâches qu'il veut certainement présenter.

Pour optimiser les chances d'arriver à la fin du travail, Knut surveille depuis longtemps son temps. Il a pris sa retraite à 55 ans, a limité la prise de parole en public et a refusé le courrier électronique (au moins officiellement). Andrei Broder rappelle que la gestion du temps était une caractéristique déterminante de son professeur dans les années 1980.

Knut rencontrait généralement les étudiants le vendredi matin jusqu'à ce qu'il commence à passer les soirées dans le laboratoire de John McCarthy, l'un des pionniers de l'intelligence artificielle, à accéder aux ordinateurs lorsqu'ils étaient libres. Effrayé par la façon dont le livre qui lui tient à cœur a commencé à s'intéresser à l'avènement des systèmes d'édition numérique, Knut s'est fixé pour objectif de développer un système informatique pour l'ensemble typographique TeX, qui reste l'étalon-or pour toutes les formes de communications et de publications scientifiques. Certains le considèrent comme la plus grande contribution de Knut et la plus grande contribution à l'imprimerie depuis l'époque de Gutenberg.

Ce retard de dix ans s'est produit à un moment où différentes personnes utilisaient des ordinateurs et où elles travaillaient plus vite la nuit, lorsque la plupart des gens dormaient. Par conséquent, Knut est passé à un mode de vie nocturne, a décalé l'horaire de 12 heures et a changé l'heure des réunions avec les étudiants de 8 à 12 heures du soir vendredi. Broder se souvient: "Quand j'ai dit à ma petite amie que nous ne pouvions rien faire vendredi soir, parce que j'avais rendez-vous avec mon superviseur à 22 heures, elle a pensé:" Cela semble si stupide que cela semble être vrai " ".

Cependant, lorsque Knut décide de se rendre quelque part en personne, il consacre toute son attention à cet événement. «Être avec lui est un plaisir», a déclaré Jennifer Chase, directrice générale de Microsoft Research. «Il est au maximum dans la communauté. Si vous aviez une fonction d'optimisation qui représentait la chaleur et la profondeur, alors ce serait Don. »


Knut discute des polices avec Hermann Zapf, un développeur de polices.

Dimanche avec un algorithme

Knut vit à Stanford et rencontre des gens le dimanche. Ce qu'il a mis de côté pour toute la journée était exceptionnel - il n'est généralement pas disponible pendant son sommeil diurne, qui est un rituel sacré qui dure de 13 à 16 heures. Il a commencé sa journée tôt, dans la première église luthérienne de Palo Alto, où il a donné une leçon pour l'école du dimanche devant une foule de gens réunis dans une pièce sans chaises. Sur le chemin du retour, il commence à philosopher sur les mathématiques.

«Je ne saurai jamais tout», a-t-il déclaré. "Ma vie serait bien pire s'il n'y avait pas de questions pour lesquelles je connais les réponses, et s'il n'y avait pas de questions pour lesquelles je ne connais pas les réponses." Il a ensuite offert une visite de la maison «Californie moderne» que lui et sa femme ont construite en 1970. Son bureau est rempli de piles de lecteurs flash et décoré avec des objets d'artisanat par Jill, un graphiste, le jour de la Saint-Valentin. Le plus impressionnant est la salle de musique, construite autour d'un orgue sur mesure avec 812 tuyaux. La journée s'est terminée lors d'une fête avec bière et devinettes.

Des énigmes, des jeux, l'écriture d'un roman sur les nombres surréalistes , la composition d'une composition musicale multimédia de 90 minutes Fantasia Apocalyptica - de telles choses commencent . Une section de son livre s'intitule Énigmes contre le monde réel. Il a envoyé un extrait du livre à une équipe de père et fils, Martin Demein, un artiste, et Eric Demein, un spécialiste en informatique qui travaille au MIT, car Knut a inclus leurs « polices de puzzle algorithmique » dans le livre.

«J'ai été agréablement surpris», a déclaré Eric Demain. "Entrer dans ce livre est un honneur." Il a mentionné une autre citation de Knut, une conférence biennale inspirante de divertissement avec algorithmes : «L'objectif principal était probablement toujours le plaisir.»

Et puis, a déclaré Demane, ce domaine est devenu un domaine pratique. Ingénieurs, scientifiques, artistes - ils se réunissent tous pour résoudre de vrais problèmes, tels que le pliage des protéines, la robotique, les airbags, en utilisant les méthodes origami développées par les deux Demane, le pliage du papier et son reliure sous diverses formes.

Bien sûr, tout ce désordre algorithmique pose de vrais problèmes. Les algorithmes écrits par des personnes - abordant des tâches de plus en plus complexes et émettant du code rempli d'erreurs et de biais - sont déjà assez désagréables. Mais, pire encore, ce sont des algorithmes écrits non pas par des personnes, mais par des machines.

Les programmeurs continuent de former des machines et de leur fournir des données. Les données sont un nouveau domaine d'erreurs et de biais, et elles sont plus difficiles à détecter et à corriger. Cependant, comme l'a déclaré Kevin Slavin, professeur agrégé au MIT Media Lab, «Nous écrivons maintenant des algorithmes qui ne sont pas capables de lire. Cela marque un moment historique unique où nous travaillons avec des idées, des actions et des tentatives, provoquées par la physique, provenant de personnes, mais non comprises par des personnes. » Slavin remarque souvent: "Vous avez un brillant avenir, si vous êtes un algorithme."


Knut à son bureau à la maison, 1999.


Remarques

Et ce sera d'autant plus merveilleux si vous êtes un algorithme bien versé dans Knut. "Aujourd'hui, les programmeurs utilisent ce que Knut et d'autres ont utilisé comme composants de leurs algorithmes et les combinent avec toutes sortes d'autres choses dont ils ont besoin", a déclaré le Dr Norvig de Google.

«Avec l'IA, nous faisons la même chose. C'est juste que l'étape de combinaison est automatique, basée sur les données, et non basée sur le travail du programmeur. Nous avons besoin de l'IA pour pouvoir combiner les composants afin d'obtenir la bonne réponse sur la base des données. Cependant, vous devez décider quels sont ces composants. Il peut arriver que chacun des composants soit une page ou un chapitre de Whip, car ce sera le meilleur moyen de terminer une tâche.

Nous avons donc de la chance que Knut continue de le faire. Il pense qu'il faudrait encore 25 ans pour achever «l'art de la programmation», bien que cette évaluation n'ait pas changé depuis les années 1980. Les algorithmes qui écrivent d'autres algorithmes obtiendront-ils leur chapitre dans le livre ou la page dans l'épilogue? "Certainement pas", a déclaré Knut.

"Je suis préoccupé par l'effet que les algorithmes ont sur le monde", a-t-il ajouté. - Tout a commencé avec le fait que les informaticiens étaient inquiets parce que personne ne les écoutait. Maintenant, je crains que trop de gens nous écoutent. "

☃