Donald Ervin Knuth (né le 10 janvier 1938) est un informaticien et mathématicien américain. Il est professeur émérite à l'Université Stanford et lauréat du prix Turing de l'ACM en 1974, considéré de manière informelle comme le prix Nobel de l'informatique. Knuth a été qualifié de « père de l'analyse des algorithmes » et est l'auteur de l'ouvrage en plusieurs volumes The Art of Computer Programming.
Knuth a contribué au développement de l'analyse rigoureuse de la complexité computationnelle et a systématisé les techniques mathématiques formelles qui s'y rapportent, popularisant la notation asymptotique. Il est également le créateur du système de composition typographique TeX, du langage de définition de polices METAFONT et des polices Computer Modern. En tant qu'écrivain et chercheur, il a créé les systèmes de programmation WEB et CWEB pour la programmation lettrée et a conçu les architectures de jeux d'instructions MIX et MMIX. Il s'oppose fermement aux brevets logiciels et a exprimé ses opinions auprès de l'Office des brevets et des marques des États-Unis et de l'Organisation européenne des brevets.
Jeunesse et formation
Knuth est né à Milwaukee, dans le Wisconsin, de Ervin Henry Knuth et Louise Marie Bohning. Il décrit son héritage comme « germano-luthérien du Midwest ». Son père possédait une petite imprimerie et enseignait la tenue de livres. Au lycée luthérien de Milwaukee, Knuth a fait preuve d'une ingéniosité précoce pour résoudre des problèmes. En huitième année, il a participé à un concours visant à trouver le nombre de mots pouvant être formés à partir des lettres de « Ziegler's Giant Bar ». Les juges avaient identifié 2 500 mots ; Knuth, utilisant un dictionnaire non abrégé pendant une journée de maladie fictive, en a trouvé plus de 4 500 et a remporté le concours. L'école a reçu un téléviseur et des barres chocolatées pour tous les élèves.
Knuth a reçu une bourse en physique à l'Institut de technologie Case (aujourd'hui partie de l'Université Case Western Reserve) en 1956. Il a rejoint le chapitre Beta Nu de la fraternité Theta Chi. Introduit à l'IBM 650, un ordinateur commercial précoce, il a lu son manuel et a décidé de réécrire le code d'assemblage et de compilation de la machine, pensant pouvoir faire mieux. En 1958, il a créé un programme pour aider l'équipe de basket-ball à gagner en attribuant des « valeurs » aux joueurs pour estimer la probabilité de marquer - une approche novatrice rapportée par Newsweek et CBS Evening News.
Knuth a été rédacteur fondateur de la Engineering and Science Review, qui a remporté un prix national en 1959. Il est passé de la physique aux mathématiques et a obtenu à la fois un baccalauréat ès sciences et une maîtrise en 1960, cette dernière grâce à une distinction spéciale du corps professoral. À la fin de sa dernière année, il a proposé à la société Burroughs d'écrire un compilateur ALGOL pour le B205 pour 5 000 dollars ; la proposition a été acceptée, et il y a travaillé entre Case et Caltech. En 1963, il a obtenu un doctorat en mathématiques de l'Institut de technologie de Californie, avec Marshall Hall comme directeur de thèse, sur la thèse Finite Semifields and Projective Planes.
Début de carrière et The Art of Computer Programming
Après avoir obtenu son doctorat, Knuth a rejoint la faculté de Caltech en tant que professeur assistant en 1963. Il est également devenu consultant pour Burroughs Corporation, travaillant sur le compilateur ALGOL pour le B220. Il a refusé un contrat de 100 000 dollars de Green Tree Corporation pour rester à Caltech et Burroughs. Il a décliné des bourses de la National Science Foundation et de la Fondation Woodrow Wilson parce qu'elles auraient empêché son travail de consultant. À l'été 1962, il a écrit un compilateur FORTRAN pour Univac, déclarant plus tard avoir « vendu son âme au diable ».
Chez Burroughs, Knuth a suggéré une extension de la table des symboles permettant à un symbole de représenter une chaîne de symboles, ce qui est devenu la base de la fonctionnalité DEFINE dans l'ALGOL de Burroughs. Edsger Dijkstra n'a pas apprécié l'idée au départ. Knuth a également travaillé sur les langages de simulation, produisant SOL avec J. McNeeley, et a influencé Burroughs pour adopter Simula après avoir assisté à une conférence en Norvège en 1967. Sa relation de conseil avec Burroughs a duré de 1960 à 1968.
En 1962, Addison-Wesley a commandé à Knuth un livre sur les compilateurs. En y travaillant, il s'est rendu compte qu'il avait besoin d'une théorie fondamentale de la programmation informatique, ce qui est devenu The Art of Computer Programming. Initialement prévu en un volume, il s'est étendu à six ou sept ; le premier volume a été publié en 1968. Juste avant la publication, Knuth a quitté Caltech pour travailler à la Division de recherche en communications de l'Institute for Defense Analyses à Princeton, menant des recherches mathématiques en cryptographie pour la National Security Agency.
Contributions à l'informatique
Le travail de Knuth sur The Art of Computer Programming a établi l'analyse des algorithmes comme une discipline rigoureuse. Il a introduit et popularisé la notation asymptotique (telle que la notation grand O) pour décrire l'efficacité des algorithmes. Ses livres sont connus pour leur précision, leurs notes historiques et leurs exercices classés par difficulté. La série est considérée comme une référence fondamentale en informatique.
Knuth a également développé le système de composition typographique TeX (publié en 1978) et METAFONT, permettant une composition mathématique de haute qualité. TeX est devenu une norme dans l'édition académique. Il a créé les systèmes WEB et CWEB pour la programmation lettrée, qui combinent code et documentation dans une seule source. Ses langages d'assemblage MIX et MMIX sont utilisés dans ses livres pour illustrer des concepts de programmation de bas niveau.
Carrière ultérieure et reconnaissance
Knuth a rejoint l'Université Stanford en 1969, où il est devenu professeur puis professeur émérite. Il a reçu le prix Turing en 1974 pour ses contributions majeures à l'analyse des algorithmes et à la conception des langages de programmation. Il a également reçu la Médaille nationale des sciences (1979), la Médaille John von Neumann (1995) et le Prix de Kyoto (1996). Knuth est connu pour son souci du détail, offrant des récompenses monétaires pour les erreurs trouvées dans ses livres.
Knuth est un opposant déclaré aux brevets logiciels, déposant des mémoires d'amicus curiae et témoignant devant les offices de brevets. Il s'est retiré de la recherche active dans les années 1990 pour se consacrer à l'achèvement de The Art of Computer Programming, dont les volumes 4A et 4B ont été publiés en 2011 et 2022. Son travail a influencé des générations d'informaticiens, y compris beaucoup au MIT et à l'Université Carnegie Mellon.
Héritage
L'impact de Knuth s'étend aux algorithmes, à la composition typographique et à la méthodologie de programmation. Ses manuels ont été traduits dans de nombreuses langues et restent largement utilisés. Le système TeX et ses dérivés (tels que LaTeX) sont des outils essentiels dans l'édition scientifique. Son concept de programmation lettrée a influencé les pratiques modernes de documentation. L'insistance de Knuth sur la rigueur mathématique dans l'analyse des algorithmes a établi une norme pour le domaine, et ses contributions à l'intelligence artificielle et aux domaines connexes sont reconnues par de nombreux diplômes et prix honorifiques.
Malgré son accent sur l'informatique classique, le travail de Knuth sous-tend de nombreux développements modernes, y compris l'apprentissage automatique et les réseaux de neurones, en fournissant des techniques algorithmiques fondamentales. Son héritage est célébré par le prix Knuth annuel, décerné pour des contributions exceptionnelles aux fondements de l'informatique.