Donald Knuth
Donald Ervin Knuth ([kə.ˈnuːθ]), né le 10 janvier 1938 à Milwaukee dans le Wisconsin, est un informaticien et mathématicien américain de renom, professeur émérite en informatique à l'université Stanford (en tant que « professeur émérite de l'art de programmer »). Il est un des pionniers de l'algorithmique et a fait de nombreuses contributions dans plusieurs branches de l'informatique théorique. Knuth est l'auteur d'une centaine d'articles et d'une dizaine de livres sur l'algorithmique et les mathématiques discrètes ; les trois premiers volumes, avec les parties déjà publiées du volume 4 (4A et 4B) de The Art of Computer Programming (TAOCP), demeurent des ouvrages de référence. Afin d'avoir une bonne qualité de mise en page pour la deuxième édition de son TAOCP, Knuth crée deux logiciels libres, par la suite largement utilisés en typographie professionnelle et en mathématiques, TeX et Metafont. Son intérêt pour la typographie le pousse également à créer la police Computer Modern, police par défaut de TeX.
Pour les articles homonymes, voir Knuth.
.jpg)
| Professeur |
|---|
| Naissance | |
|---|---|
| Nom dans la langue maternelle |
Donald Ervin Knuth |
| Nationalité | |
| Formation |
Milwaukee Lutheran High School (en) (jusqu'en 1956) Université Case Western Reserve (master of science et baccalauréat ès sciences) (jusqu'en 1960) California Institute of Technology (docteur en philosophie) (septembre 1960 - juin 1963) |
| Activités |
Donald Ervin Knuth ([kə.ˈnuːθ][1]), né le 10 janvier 1938 à Milwaukee dans le Wisconsin, est un informaticien et mathématicien américain de renom, professeur émérite en informatique à l'université Stanford[2] (en tant que « professeur émérite de l'art de programmer »). Il est un des pionniers de l'algorithmique et a fait de nombreuses contributions dans plusieurs branches de l'informatique théorique.
Knuth est l'auteur d'une centaine d'articles et d'une dizaine de livres sur l'algorithmique et les mathématiques discrètes ; les trois premiers volumes, avec les parties déjà publiées du volume 4 (4A et 4B) de The Art of Computer Programming (TAOCP), demeurent des ouvrages de référence.
Afin d'avoir une bonne qualité de mise en page pour la deuxième édition de son TAOCP, Knuth crée deux logiciels libres, par la suite largement utilisés en typographie professionnelle et en mathématiques, TeX et Metafont. Son intérêt pour la typographie le pousse également à créer la police Computer Modern, police par défaut de TeX.
Biographie
[modifier | modifier le code]Enfance et études
[modifier | modifier le code]Né à Milwaukee, dans le Wisconsin, Knuth reçoit son bachelor's degree summa cum laude[3] et son master's degree (les deux simultanément, le jury considérant son travail de B.Sc. comme valant un M.Sc.) en mathématiques du Case Institute of Technology (devenu depuis l'université Case Western Reserve) en 1960.
Sa première analyse d'algorithme remonte à l'été 1962. Il est alors impressionné par un ouvrage de l'informaticien soviétique Andreï Ershov.
Knuth découvre à cette occasion un lien entre l'efficacité d'un algorithme de hachage et des mathématiques remontant à Ramanujan.
En 1963, il soutient avec succès son Ph. D. (doctorat) en mathématiques au California Institute of Technology[4],[5].
Il est invité d'honneur de l’Oulipo en 1996[6].
Carrière universitaire
[modifier | modifier le code]En 1968, il devient membre de la faculté de l'université Stanford, où il recevra finalement un titre académique créé à son intention : Professor Emeritus of the Art of Computer Programming. En 1971, Knuth est le premier à recevoir le prix Grace Murray Hopper de l'Association for Computing Machinery (ACM). Il reçoit de nombreuses autres distinctions honorifiques, entre autres le prix Turing, la National Medal of Science (États-Unis), la médaille John von Neumann[7] de l'IEEE, ainsi que le prix de Kyoto et la médaille Franklin. Il est élu membre associé de l'Académie des sciences française en 1992 et membre de la Royal Society en 2003.
Personnalité
[modifier | modifier le code]
Knuth est une figure de l'informatique connue pour son humour geek : il offre par exemple une prime de 2,56 dollars pour chaque faute typographique ou erreur découverte dans ses livres, expliquant que « 256 cents font un dollar hexadécimal » (pour les erreurs de son ouvrage 3:16 Bible Texts Illuminated, la prime est cependant de 3,16 dollars). Les numéros de version de TeX convergent vers pi, c’est-à-dire que les versions se suivent de la sorte : « 3 », « 3,1 », « 3,14 », etc., les numéros de version de Metafont convergent, eux, vers le nombre e. Il a également mis en garde ainsi les utilisateurs d'un de ses logiciels : « Faites attention aux bogues dans ce code ; je n'ai fait que démontrer qu'il était correct, je ne l'ai pas essayé[8]. »
Knuth a cessé d'utiliser le courrier électronique, disant qu'il s'en était servi entre 1975 et le 1er janvier 1990, et que cela suffisait pour toute une vie. Il trouve plus efficace de tenir une correspondance en « mode batch », et y consacrer une journée tous les six mois, en répondant par courrier « classique[9] ».
Vie personnelle, autres signes d'humour
[modifier | modifier le code]Knuth apprécie la musique et aime en particulier jouer de l'orgue. Il en a fait construire un dans sa propre maison[10]. Knuth fait allusion à son orgue dans l'index du volume 3 de The Art of Computer Programming : l'entrée Royalties, use of renvoie vers le graphique « organ-pipe arrangement ».
Il est marié à Nancy Jill Carter[11], qui a publié un livre sur la liturgie et réalisé les illustrations du livre sur les nombres surréels[12]. Ils ont deux enfants. Avec elle, il collectionne les photographies de panneaux de signalisation routière (signalisation de danger de forme losangée) américains, s'intéressant aux plus surprenants[13].
Knuth a publié son premier article (qui était à forte teneur humoristique) dans le numéro de juin 1957 du magazine américain Mad[14].
À la suite d'un défaut de typographie sur le delta minuscule (δ), Knuth lance un appel pour corriger le problème et demande de mettre à jour la police de caractères Computer Modern, disant qu'il « ne pouvait supporter d'écrire des documents utilisant ce symbole, maintenant il ne supporte pas de lire les documents qui l'utilisent toujours[15] ».
Travaux
[modifier | modifier le code]Les travaux de Donald Knuth concernent particulièrement l'algorithmique et les mathématiques discrètes, mais il a aussi créé des logiciels très utilisés encore aujourd'hui, TeX et Metafont.
Contributions aux mathématiques
[modifier | modifier le code]- Notation des puissances itérées de Knuth ;
- Travaux sur les tableaux de Young.
Contributions à l’algorithmique
[modifier | modifier le code]Don Knuth est le créateur de plusieurs algorithmes qui portent son nom, parmi lesquels :
- l'algorithme de Knuth-Morris-Pratt, algorithme de recherche de sous-chaîne ;
- l'algorithme X de Knuth, algorithme récursif non déterministe de parcours en profondeur et à retour sur trace ;
- l'algorithme RSK ;
- la complétion de Knuth-Bendix.
Contributions à la typographie: les logiciels TeX et Metafont
[modifier | modifier le code]
Knuth est le créateur du système de composition de documents TeX et du système de création de polices Metafont.
Mécontent de la façon dont étaient imprimés ses livres, il consacre plusieurs années de sa vie, à partir de 1977, à écrire un logiciel lui permettant d'obtenir un rendu correct des formules mathématiques pour la typographie professionnelle. Il s'agit d'un langage à balises tel que le SGML, qui permet de se concentrer sur la structure du document, laissant au compilateur le travail de mise en page. Le but de Knuth quand il a créé TeX était d'avoir un langage de description de contenu permettant d'obtenir un rendu de grande qualité avec un minimum d'efforts et qui serait indépendant de l'architecture matérielle. TeX se distingue par la précision de son algorithme de césure et d’espacement des lignes, garantissant une disposition esthétique des textes, mais ce projet est aussi novateur sur le plan des logiciels libres. En effet, Knuth a publié TeX avec ses sources, permettant à d’autres de l’utiliser et de le modifier, à la seule condition que les versions modifiées ne prennent pas le nom de TeX[16]. Ce choix a contribué à la pérennité du logiciel. Ainsi, TeX constitue l’un des premiers exemples de logiciel libre, avant même que le concept ne soit formalisé.
TeX a connu par la suite de nombreuses extensions et améliorations. Les plus courantes aujourd’hui sont pdfTeX, qui permet la génération directe de fichiers PDF, XeTeX, qui améliore la gestion des polices et des systèmes d’écriture multilingues, et LuaTeX, qui offre plus de flexibilité pour la personnalisation et la programmation en intégrant le langage de script Lua.
En parallèle, Knuth développe Metafont, un langage utilisé pour composer des polices matricielles. Grâce à ce langage, Knuth crée la police Computer Modern, qui reste encore aujourd’hui la police par défaut des documents TeX. Mais l’influence de Metafont va au delà de la simple typographie, puisqu’il a aussi donné naissance à MetaPost, un langage qui permet de générer des illustrations vectorielles au format PostScript à partir de descriptions géométriques.
Contributions à la théorie des langages informatiques
[modifier | modifier le code]Knuth est à l'origine de nombreux concepts de programmation. On peut citer :
- les analyseurs de grammaires formelles LR(k) ;
- la méthode des attributs sémantiques en compilation ;
- le concept de programmation lettrée (literate programming).
Ouvrages
[modifier | modifier le code]The Art of Computer Programming
[modifier | modifier le code]Knuth est surtout connu comme l'auteur de l'ouvrage The Art of Computer Programming (TAOCP), une des références dans le domaine de l'informatique. Ce livre a établi un domaine : l'analyse d'algorithmes, qui consiste à se servir des mathématiques pour étudier les performances (en temps, mémoire…) d'un algorithme sur l'ensemble de ses exécutions possibles.
Au début du XXIe siècle, Knuth consacre désormais presque toute son énergie à achever les sept volumes de TAOCP (la première édition du premier volume remonte à 1968 et seulement les trois premiers volumes ont paru, ainsi que trois fascicules du quatrième volume).
Computers & Typesetting
[modifier | modifier le code]Il s'agit de l'ensemble constitué par :
- The TeXbook (Reading, Massachusetts: Addison-Wesley, 1984), (ISBN 0-201-13447-0)
- TeX: The Program (Reading, Massachusetts: Addison-Wesley, 1986), (ISBN 0-201-13437-3)
- The METAFONTbook (Reading, Massachusetts: Addison-Wesley, 1986), (ISBN 0-201-13445-4)
- METAFONT: The Program (Reading, Massachusetts: Addison-Wesley, 1986), (ISBN 0-201-13438-1)
- Computer Modern Typefaces (Reading, Massachusetts: Addison-Wesley, 1986), (ISBN 0-201-13446-2)
Nombres surréels
[modifier | modifier le code]Un texte présentant de manière ludique les nombres surréels de Conway :
- (en) Donald Ervin Knuth, Surreal Numbers : How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness : A Mathematical Novelette, Addison-Wesley Professional, 1974, 119 p. (ISBN 0-201-03812-9) ;
- Traduction française de Daniel E. Loeb et Hélène Loeb, Les nombres surréels, ou comment deux anciens étudiants découvrirent les mathématiques pures et vécurent heureux. Une romance mathématique de D. E. Knuth
Autres livres
[modifier | modifier le code]Knuth est également l'auteur de 3:16 Bible Texts Illuminated (1991) (ISBN 0-89579-252-4), dans lequel il tente d'examiner la Bible par une analyse du chapitre 3, verset 16 de chaque livre. Chaque verset est accompagné d'une calligraphie produite par un groupe de calligraphes dirigés par Hermann Zapf. La traduction française est parue en 2017 sous le titre 3.16, Bible en lumière (ISBN 978-2-227-49168-7)
Il a également écrit un ouvrage sur les « mariages stables » et des algorithmes apparentés. Il s'agit d'un problème d'optimisation combinatoire, comme ceux qui surviennent lorsqu'on cherche à apparier deux types d'acteurs ou d'objets avec des listes de préférences : étudiants et stages… Cet ouvrage a d'abord été publié en français en 1976[17], après une conférence donnée à l'Université de Montréal, puis traduit en anglais vingt ans plus tard.
Le livre Éléments pour une histoire de l'informatique, édité par CLSI Publications (Stanford) et la Société mathématique de France (2011), regroupe divers articles de Donald Knuth sur l'histoire de l'informatique, choisis et traduits par Patrick Cégielski, et en partie réécrits à cette occasion.
En collaboration avec Ronald Graham et Oren Patashnik, il a développé les sections mathématiques de TAOCP sous forme d'un manuel de cours de combinatoire, intitulé Concrete Mathematics.
Distinctions
[modifier | modifier le code]Donald Knuth a reçu plus d'une centaine de prix et d'honneurs dans le monde[18],[19] :
Prix
[modifier | modifier le code]- 1971 : Prix Grace Murray Hopper de l'Association for Computing Machinery
- 1972 : Bourse Guggenheim
- 1974 : Prix Turing pour The Art of Computer Programming[18]
- 1975 : Prix Halmos-Ford
- 1979 : Médaille nationale de la science, remis par le Président des États-Unis Jimmy Carter le 14 janvier 1980[20]
- 1980 : W. Wallace McDowell Award (en)
- 1986 : Prix ACM Software System pour le projet TeX[21]
- 1986 : Prix Leroy P. Steele[22]
- 1988 : Médaille Franklin de l'Institut Franklin[23]
- 1993 : Prix Halmos-Ford
- 1994 : Médaille Adelskold de l'Académie royale des sciences de Suède[19]
- 1995 : Médaille John von Neumann de l'Institute of Electrical and Electronics Engineers[24]
- 1995 : Prix Harvey de l'Institut israélien de technologie[25]
- 1996 : Prix Kyoto dans la catégorie Science de l'information
- 2006 : Médaille d'or de l'université d'État d'ingénierie d'Arménie[19]
- 2006 : Médaille d'or de l'université d'État d'Erevan[19]
- 2010 : Prix Katayanagi[26]
- 2010 : BBVA Foundation Frontiers of Knowledge Award [27]
- 2011 : Médaille Faraday de l'Institution of Engineering and Technology (en)[28]
- 2011 : Stanford University School of Engineering (en) Hero Award[29]
- 2018 : Prix Trotter (en)
Sociétés savantes
[modifier | modifier le code]- 1973 : Membre de l'Académie américaine des arts et des sciences dans la section Science physique et mathématique[30]
- 1975 : Membre de l'Académie nationale des sciences (Etats-Unis)[31]
- 1980 : Membre distingué de la British Computer Society[32]
- 1981 : Membre de l'Académie nationale d'ingénierie des États-Unis[33]
- 1982 : Membre de l'Association for Computing Machinery[18]
- 1982 : Membre d'honneur de l'Institute of Electrical and Electronics Engineers[34]
- 1992 : Associé étranger de l'Académie des sciences (France), élu le 30 mars 1992 dans la section Sciences mécaniques et informatiques[35]
- 1998 : Membre d'honneur du Musée de l'histoire de l'ordinateur[36]
- 1998 : Membre de l'Académie bavaroise des sciences[37]
- 2003 : Membre étranger de la Royal Society[38]
- 2008 : Membre de l'Académie des sciences de Russie[39]
- 2009 : Membre de la Society for Industrial and Applied Mathematics
- 2012 : Membre de la Société américaine de philosophie
- 2015 : Membre d'honneur de la London Mathematical Society[19]
- Membre de l'American Mathematical Society
- Membre de l'Académie norvégienne des sciences et des lettres[40]
Honneurs
[modifier | modifier le code]- 1978 : Conférence Gibbs
- 1993 : Professeur Emeritus de l'université Stanford[18]
- 2001 : L’astéroïde (21656) Knuth est nommé en son honneur[19]
- 2011 : Leçon Turing (en)
- 2016 : Conférence von Neumann
Il a reçu une multitude de Doctorat honoris causa :
- 1986 : Université Paris-Sud (Orsay)
- 1991 : Université Concordia[41]
- 1993 : Université de Marne-la-Vallée[42]
- 1996 : Université Masaryk[43]
- 2000 : Université de Waterloo[19]
- 2001 : Université Eberhard Karl de Tübingen[19]
- 2002 : Université d'Oslo[32],[44]
- 2003 : Université Harvard[45]
- 2003 : Université d'Anvers[46]
- 2003 : Université de Macédoine[19]
- 2004 : Faculté des arts et des sciences de l’université de Montréal[19]
- 2005 : École polytechnique fédérale de Zurich[47]
- 2006 : Université du Wisconsin[19]
- 2007 : Université Bordeaux-I[48]
- 2011 : Université de Glasgow[32]
- Université d'État de Saint-Pétersbourg[32]
- Université d'État de New York à Stony Brook[41]
Notes et références
[modifier | modifier le code]- ↑ (en) « Frequently Asked Questions » sur la page personnelle de Knuth. La prononciation proposée est Ka-NOUSS.
- ↑ (en) http://www-cs-faculty.stanford.edu/~knuth/.
- ↑ Summa cum laude, littéralement : « Avec les éloges les plus grands » : « Avec les félicitations du jury ».
- ↑ (en) « Donald Ervin Knuth | American mathematician and computer scientist », sur Encyclopedia Britannica (consulté le 10 janvier 2020)
- ↑ (en-US) « Donald E. Knuth | Encyclopedia.com », sur www.encyclopedia.com (consulté le 10 janvier 2020)
- ↑ « Invités d'honneur de l'Oulipo », sur oulipo.net (consulté le 11 janvier 2025)
- ↑ Liste des lauréats de la médaille John von Neumann.
- ↑ FAQ sur le site personnel de Donald Knuth.
- ↑ (en) http://www-cs-faculty.stanford.edu/~knuth/email.html.
- ↑ Page de son site consacrée à cet orgue.
- ↑ Information de son CV.
- ↑ Donald Ervin Knuth, Surreal Numbers : How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness : A Mathematical Novelette, Addison-Wesley Professional (1974) - (ISBN 0-201-03812-9).
- ↑ site des panneaux.
- ↑ The Potrzebie (en) System of weights and measures : « ma première publication », dit Knuth dans une entrevue.
- ↑ (en) Message important pour tous les utilisateurs de TeX.
- ↑ « The lingua franca of LaTeX – Increment: Open Source », sur localhost (consulté le 4 novembre 2024)
- ↑ Donald E. Knuth, Mariages stables et leurs relations avec d'autres problèmes combinatoires., Montréal, Presses de l'université de Montréal, 1976 (ISBN 2-7606-0529-9, lire en ligne).
- (en) « DONALD ("DON") ERVIN KNUTH », sur Association for Computing Machinery (consulté le 27 mai 2019).
- (en) « Donald Ervin Knuth », sur Université de St Andrews (consulté le 28 mai 2019).
- ↑ (en) « The President's National Medal of Science: Recipient Details », sur national Science Foundation (consulté le 27 mai 2019).
- ↑ (en) « ACM Software System Award », sur Association for Computing Machinery (consulté le 27 mai 2019).
- ↑ (en) « Prizes and Awards », sur American Mathematical Society (consulté le 27 mai 2019).
- ↑ (en) « DONALD ERVIN KNUTH », sur Institut Franklin (consulté le 27 mai 2019).
- ↑ (en) « IEEE John Von Neumann Medal Recipients », sur Institute of Electrical and Electronics Engineers (consulté le 27 mai 2019).
- ↑ (en) « Harvey Prize », sur Institut israélien de technologie (consulté le 27 mai 2019).
- ↑ « Katayanagi », CMU.
- ↑ (es) « Fronteras », FBBVA, 2010.
- ↑ (en) « The Faraday Medallists », sur Institution of Engineering and Technology (consulté le 27 mai 2019).
- ↑ Andrew Myers, « Stanford's Don Knuth, a pioneering hero of computer programming », Stanford Report, 1er juin 2001 (lire en ligne, consulté le 27 juin 2011).
- ↑ (en) « Donald Ervin Knuth », sur Académie américaine des arts et des sciences (consulté le 27 mai 2019).
- ↑ (en) « Donald E. Knuth », sur Académie nationale des sciences (consulté le 27 mai 2019).
- (en) « Honorary Degree for Stanford Computer Scientist », sur Université de Glasgow (consulté le 27 mai 2019).
- ↑ (en) « Dr. Donald Knuth », sur Académie nationale d'ingénierie des États-Unis (consulté le 27 mai 2019).
- ↑ (en) « IEEE Honorary Membership », sur Institute of Electrical and Electronics Engineers (consulté le 27 mai 2019).
- ↑ « Donald Knuth », sur Académie des sciences (consulté le 27 mai 2019).
- ↑ (en) « Donald Knuth », sur Musée de l'histoire de l'ordinateur (consulté le 27 mai 2019).
- ↑ (en) « Prof. Dr. Donald E. Knuth », sur Académie bavaroise des sciences (consulté le 27 mai 2019).
- ↑ (en) « Donald Knuth », sur Royal Society (consulté le 27 mai 2019).
- ↑ (ru) « Кнут Дональд Эрвин », sur Académie des sciences de Russie (consulté le 27 mai 2019).
- ↑ (no) « Gruppe 1: Matematiske fag », sur Académie norvégienne des sciences et des lettres (consulté le 27 mai 2019).
- (en) « Honorary Degree Citation - Donald Ervin Knuth », sur Université Concordia (consulté le 28 mai 2019).
- ↑ Docteurs honoris causa de l'UMLV.
- ↑ (pl) « Donald E. Knuth », sur Université Masaryk (consulté le 28 mai 2019).
- ↑ (en) « Honors and Awards », sur Université Stanford (consulté le 28 mai 2019).
- ↑ (en) « Honorary Degrees », sur Université Harvard (consulté le 27 mai 2019).
- ↑ (en) « Honorary Doctorates », sur Université d'Anvers (consulté le 28 mai 2019).
- ↑ (en) « Honorary Doctors », sur École polytechnique fédérale de Zurich (consulté le 27 mai 2019).
- ↑ Journées en l'honneur de Donald E. Knuth.
Certains renseignements viennent de son CV [PDF]
Annexes
[modifier | modifier le code]Articles connexes
[modifier | modifier le code]- Algorithme de Knuth-Morris-Pratt
- Algorithme de Trabb Pardo-Knuth (en)
- Algorithme de Knuth-Bendix
- Grammaire attribuée
- Metafont
- Notation des puissances itérées de Knuth
- Prix Donald E. Knuth
- TeX
Liens externes
[modifier | modifier le code]
- (en) Site officiel
- Archives conservées par : musée de l'histoire de l'ordinateur (102658053)
- Ressources relatives à la recherche :
- Ressource relative à la musique :
- Notices dans des dictionnaires ou encyclopédies généralistes :
- (en) Page professionnelle sur le site de l'université Stanford — Le site comprend, outre une FAQ, une liste des questions posées rarement, où Knuth laisse entrevoir ses opinions politiques.
- (en) Longue biographie de Knuth
- (en) Conférences en ligne
- (en) Knuth, entretiens en ligne
- (en) Vidéos de présentations avec Donald Knuth
- (en) La première analyse d'algorithme de Knuth
