La science est ce que nous comprenons assez bien pour l'expliquer à un ordinateur ; l'art est tout le reste.
Donald Ervin Knuth est un informaticien américain, mathématicien et professeur émérite à l'Université Stanford. Il est le lauréat 1974 du prix Turing de l'ACM, considéré officieusement comme le prix Nobel de l'informatique. Knuth a été appelé le « père de l'analyse des algorithmes ».
Il est l'auteur de l'œuvre multi-volume The Art of Computer Programming. Il a contribué au développement de l'analyse rigoureuse de la complexité computationnelle des algorithmes et a systématisé les techniques mathématiques formelles pour celle-ci. Ce faisant, il a également popularisé la notation asymptotique. En plus de contributions fondamentales dans plusieurs branches de l'informatique théorique, Knuth est le créateur du système de composition typographique TeX, du langage de définition de polices METAFONT associé et du système de rendu, ainsi que de la famille de polices Computer Modern.
En tant qu'écrivain et universitaire, Knuth a créé les systèmes de programmation informatique WEB et CWEB conçus pour encourager et faciliter la programmation alphabétisée, et a conçu les architectures d'ensemble d'instructions MIX/MMIX. Knuth s'oppose fortement à l'octroi de brevets logiciels, ayant exprimé son opinion auprès de l'Office des brevets et marques des États-Unis et de l'Office européen des brevets.
Biographie
Début de la vie
Knuth est né à Milwaukee, Wisconsin, de parents germano-américains Ervin Henry Knuth et Louise Marie Bohning. Son père possédait une petite imprimerie et enseignait la comptabilité. Donald, étudiant à la Milwaukee Lutheran High School, a trouvé des façons ingénieuses de résoudre les problèmes. Par exemple, en huitième année, il a participé à un concours pour trouver le nombre de mots que les lettres de « Ziegler's Giant Bar » pouvaient être réarrangées pour créer ; les juges avaient identifié 2 500 tels mots. Avec le temps gagné en s'absentant de l'école en raison d'une douleur à l'estomac feinte, et en travaillant le problème à l'envers, Knuth a utilisé un dictionnaire complet et a déterminé si chaque entrée du dictionnaire pouvait être formée en utilisant les lettres de la phrase. En utilisant cet algorithme, il a identifié plus de 4 500 mots, remportant le concours. En tant que prix, l'école a reçu une nouvelle télévision et assez de barres chocolatées pour que tous ses camarades de classe puissent en manger.
Éducation
Knuth a reçu une bourse en physique au Case Institute of Technology, maintenant partie de Case Western Reserve University à Cleveland, Ohio, s'inscrivant en 1956. Il a également rejoint la Beta Nu Chapter de la fraternité Theta Chi. Tout en étudiant la physique à Case, Knuth a été introduit à l'IBM 650, un ordinateur commercial précoce. Après avoir lu le manuel de l'ordinateur, Knuth a décidé de réécrire le code assembly et compilateur de la machine utilisée dans son école, car il croyait qu'il pouvait le faire mieux.
En 1958, Knuth a créé un programme pour aider l'équipe de basket-ball de son école à remporter leurs matchs. Il a attribué des « valeurs » aux joueurs afin d'évaluer leur probabilité de marquer des points, une approche novatrice que Newsweek et CBS Evening News ont rapportée par la suite.
Knuth était l'un des rédacteurs fondateurs de l'Engineering and Science Review du Case Institute, qui a remporté un prix national en tant que meilleur magazine technique en 1959. Il est ensuite passé de la physique aux mathématiques, et a reçu deux diplômes du Case en 1960 : son baccalauréat ès sciences et simultanément une maîtrise ès sciences par un prix spécial de la faculté, qui considéraient son travail exceptionnellement remarquable.
En 1963, avec le mathématicien Marshall Hall comme conseiller, il a obtenu un doctorat en mathématiques du California Institute of Technology.
Premiers travaux
Après avoir obtenu son doctorat, Knuth a rejoint la faculté de Caltech en tant que professeur assistant.
Il a accepté une commission pour écrire un livre sur les compilateurs de langage de programmation informatique. En travaillant sur ce projet, Knuth a décidé qu'il ne pouvait pas traiter adéquatement le sujet sans d'abord développer une théorie fondamentale de la programmation informatique, qui devint The Art of Computer Programming. Il avait initialement prévu de publier ceci en tant que livre unique. Alors que Knuth développait son plan pour le livre, il a conclu qu'il avait besoin de six volumes, puis sept, pour couvrir complètement le sujet. Il a publié le premier volume en 1968.
Juste avant de publier le premier volume de The Art of Computer Programming, Knuth a quitté Caltech pour accepter un emploi à la Communications Research Division de l'Institute for Defense Analyses, à l'époque située sur le campus de l'Université de Princeton, qui menait des recherches mathématiques en cryptographie pour soutenir l'Agence de sécurité nationale.
En 1967, Knuth a assisté à la conférence de la Society for Industrial and Applied Mathematics et quelqu'un a demandé ce qu'il faisait. À l'époque, l'informatique était divisée en analyse numérique, intelligence artificielle et langages de programmation. Basé sur son étude et le livre The Art of Computer Programming, Knuth a décidé que la prochaine fois que quelqu'un lui poserait la question, il dirait « Analyse des algorithmes ».
Knuth a ensuite quitté ce poste pour rejoindre la faculté de l'Université Stanford en 1969, où il est maintenant professeur Fletcher Jones d'informatique, émérite.
Écrits
Knuth est un écrivain, ainsi qu'un informaticien.
The Art of Computer Programming TAOCP
Dans les années 1970, Knuth a décrit l'informatique comme « un domaine tout à fait nouveau sans véritable identité. Et le standard des publications disponibles n'était pas si élevé. Beaucoup des articles qui sortaient étaient tout simplement faux. ... Donc l'une de mes motivations était de redresser une histoire qui avait été très mal racontée. » En 2011, les trois premiers volumes et la première partie du quatrième volume de sa série avaient été publiés. Concrete Mathematics: A Foundation for Computer Science 2ème édition, qui provient d'une expansion de la section des préliminaires mathématiques du Volume 1 de TAOCP, a également été publiée. En avril 2020, Knuth a dit qu'il travaille dur sur la partie B du volume 4, et il anticipe que le livre aura au moins les parties A à F.
Autres œuvres
Knuth est également l'auteur de Surreal Numbers, une novella mathématique sur la construction de la théorie des ensembles de John Conway d'un système alternatif de nombres. Au lieu de simplement expliquer le sujet, le livre cherche à montrer le développement des mathématiques. Knuth voulait que le livre prépare les étudiants à faire de la recherche originale et créative.
En 1995, Knuth a écrit la préface du livre A=B de Marko Petkovšek, Herbert Wilf et Doron Zeilberger. Knuth est également un contributeur occasionnel de puzzles linguistiques à Word Ways: The Journal of Recreational Linguistics.
Knuth s'est également plongé dans les mathématiques récréatives. Il a contribué des articles au Journal of Recreational Mathematics à partir des années 1960, et a été reconnu comme un contributeur majeur dans Mathematics on Vacation de Joseph Madachy.
Knuth a également participé à un certain nombre de vidéos Numberphile et Computerphile sur YouTube où il a discuté de sujets allant de l'écriture de Surreal Numbers à la raison pour laquelle il n'utilise pas le courrier électronique.
Œuvres concernant les croyances religieuses de Knuth
En plus de ses écrits sur l'informatique, Knuth, un luthérien, est également l'auteur de 3:16 Bible Texts Illuminated, dans lequel il examine la Bible par un processus d'échantillonnage systématique, à savoir une analyse du chapitre 3, verset 16 de chaque livre. Chaque verset est accompagné d'un rendu en art calligraphique, contribué par un groupe de calligraphes sous la direction de Hermann Zapf. Par la suite, il a été invité à donner une série de conférences au MIT sur ses opinions sur la religion et l'informatique derrière son projet 3:16, ce qui a abouti à un autre livre, Things a Computer Scientist Rarely Talks About, où il a publié les conférences « God and Computer Science ».
Opinion sur les brevets logiciels
En tant que membre de la communauté universitaire et scientifique, Knuth s'oppose fortement à la politique d'octroi de brevets logiciels pour des solutions triviales qui devraient être évidentes, mais a exprimé des opinions plus nuancées pour des solutions non triviales telles que la méthode des points intérieurs de la programmation linéaire. Il a exprimé son désaccord directement à la fois à l'Office des brevets et marques des États-Unis et à l'Office européen des brevets.
Computer Musings
Knuth donne des conférences informelles quelques fois par an à l'Université Stanford, qu'il a intitulées « Computer Musings ». Il a été professeur invité au Département d'informatique de l'Université Oxford au Royaume-Uni jusqu'en 2017 et Fellow honoraire du Magdalen College.
Programmation
Composition typographique numérique
Dans les années 1970, les éditeurs de TAOCP ont abandonné Monotype en faveur de la photocomposition. Knuth est devenu si frustré par l'incapacité de ce dernier système à se rapprocher de la qualité des volumes précédents, qui avaient été composés à l'aide du système plus ancien, qu'il a pris du temps pour travailler sur la composition typographique numérique et a créé TeX et Metafont.
Programmation alphabétisée
Tout en développant TeX, Knuth a créé une nouvelle méthodologie de programmation, qu'il a appelée programmation alphabétisée, car il croyait que les programmeurs devraient penser aux programmes comme à des œuvres de littérature. « Au lieu d'imaginer que notre tâche principale est d'instruire un ordinateur sur ce qu'il faut faire, concentrons-nous plutôt sur l'explication aux êtres humains de ce que nous voulons qu'un ordinateur fasse. »
Knuth a incarné l'idée de programmation alphabétisée dans le système WEB. La même source WEB est utilisée pour tisser un fichier TeX, et pour enchevêtrer un fichier source Pascal. Ceux-ci produisent à leur tour une description lisible du programme et un binaire exécutable respectivement. Une itération ultérieure du système, CWEB, remplace Pascal par C.
Knuth a utilisé WEB pour programmer TeX et METAFONT, et a publié les deux programmes sous forme de livres : The TeXbook, initialement publié en 1984, et The METAFONTbook, initialement publié en 1986. À peu près à la même époque, LaTeX, le forfait macro maintenant largement adopté basé sur TeX, a été développé pour la première fois par Leslie Lamport, qui a ensuite publié son premier manuel d'utilisateur en 1986.
Musique
Knuth est un organiste et un compositeur. En 2016, il a achevé une pièce musicale pour orgue intitulée Fantasia Apocalyptica, qu'il décrit comme « traduction du texte grec de la Révélation de Saint Jean le Divin en musique ». Elle a été créée en Suède le 10 janvier 2018.
Vie personnelle
Donald Knuth a épousé Nancy Jill Carter le 24 juin 1961, alors qu'il était étudiant diplômé au California Institute of Technology. Ils ont deux enfants : John Martin Knuth et Jennifer Sierra Knuth.
Nom chinois
Le nom chinois de Knuth est Gao Dena. En 1977, il lui a été donné ce nom par Frances Yao, peu de temps avant de faire un voyage de 3 semaines en Chine. Dans son volume 1980 de The Art of Computer Programming, Knuth explique qu'il a adopté son nom chinois parce qu'il voulait être connu par le nombre croissant de programmeurs informatiques en Chine à l'époque. En 1989, son nom chinois a été placé en haut de l'en-tête du Journal of Computer Science and Technology, ce que Knuth dit « me fait sentir proche de tous les Chinois bien que je ne puisse pas parler votre langue ».
Problèmes de santé
En 2006, Knuth a été diagnostiqué avec un cancer de la prostate. Il a subi une intervention chirurgicale en décembre cette année-là et a déclaré : « un peu de radiothérapie ... par mesure de précaution mais le pronostic semble plutôt bon », comme il l'a rapporté dans son autobiographie vidéo.
Humour
Knuth avait l'habitude de payer une prime de découverte de 2,56 $ pour toute erreur typographique ou toute erreur découverte dans ses livres, car « 256 cents est un dollar hexadécimal », et 0,32 $ pour les « suggestions précieuses ». Selon un article de Technology Review du Massachusetts Institute of Technology, ces chèques de récompense Knuth sont « parmi les trophées les plus prisés de l'informatique ». Knuth a dû arrêter d'envoyer de vrais chèques en 2008 en raison de la fraude bancaire, et à la place donne maintenant à chaque découvreur d'erreur un « certificat de dépôt » d'un solde publiquement répertorié dans sa fictive « Bank of San Serriffe ».
Il a un jour averti un correspondant : « Méfiez-vous des bogues dans le code ci-dessus ; je l'ai seulement prouvé correct, pas essayé. »
Knuth a publié son premier article « scientifique » dans un magazine scolaire en 1957 sous le titre « The Potrzebie System of Weights and Measures ». Il y définissait l'unité fondamentale de longueur comme l'épaisseur de Mad No. 26, et nommait l'unité fondamentale de force « whatmeworry ». Mad a publié l'article dans le numéro 33 de juin 1957.
Pour démontrer le concept de récursion, Knuth a intentionnellement renvoyé « Circular definition » et « Definition, circular » l'un à l'autre dans l'index de The Art of Computer Programming, Volume 1.
La préface de Concrete Mathematics contient le paragraphe suivant :
Quand DEK a enseigné Concrete Mathematics à Stanford pour la première fois, il a expliqué le titre quelque peu étrange en disant que c'était sa tentative d'enseigner un cours de mathématiques qui était dur au lieu de doux. Il a annoncé que, contrairement aux attentes de ses collègues, il n'allait pas enseigner la Théorie des Agrégats, ni le Théorème de Plongement de Stone, ni même la compactification Stone–Čech. (Plusieurs étudiants du département d'ingénierie civile se sont levés et ont quitté tranquillement la salle.)
À la Conférence TUG 2010, Knuth a annoncé un successeur satirique basé sur XML à TeX, intitulé « iTeX » prononcé, exécuté avec une cloche qui sonne, qui soutiendrait des fonctionnalités telles que les unités irrationnelles arbitrairement mises à l'échelle, l'impression 3D, l'entrée de seis
