Donald Knuth

Donald Ervin Knuth (), né le  à 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  (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

Enfance et études 
Né à Milwaukee, dans le Wisconsin, Knuth reçoit son bachelor's degree summa cum laude 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.

Carrière universitaire 
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 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é 

Knuth est une figure de l'informatique connue pour son humour geek : il offre par exemple une prime de  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 ). 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 . 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é. »

Knuth a cessé d'utiliser le courrier électronique, disant qu'il s'en était servi entre 1975 et le , 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 ».

Vie personnelle, autres signes d'humour 
Knuth apprécie la musique et aime en particulier jouer de l'orgue. Il en a fait construire un dans sa propre maison. Knuth fait allusion à son orgue dans l'index du  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, qui a publié un livre sur la liturgie et réalisé les illustrations du livre sur les nombres surréels. 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.

Knuth a publié son premier article (qui était à forte teneur humoristique) dans le numéro de juin 1957 du magazine américain Mad.

À 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 ».

Travaux 
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 
 Notation des puissances itérées de Knuth ;
 Travaux sur les tableaux de Young.

Contributions à l’algorithmique 
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.

Les logiciels TeX et Metafont 

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.
Fourni avec ses sources, TeX est l'un des premiers logiciels libres, ou presque. En effet, la seule restriction que Knuth impose à toute modification est qu'elle ne prenne pas le nom de TeX. Aujourd'hui, il existe plusieurs extensions de TeX, les plus répandues étant pdfTeX, XeTeX et LuaTeX.

Metafont est un langage utilisé pour composer des polices matricielles. Développé en même temps que TeX, il a été utilisé par Knuth pour créer la police Computer Modern. Le langage Metafont a aussi donné naissance à MetaPost, qui permet de produire des figures PostScript à partir d'une description géométrique.

Autres idées notables 
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

The Art of Computer Programming 
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 , 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 
Il s'agit de l'ensemble constitué par :
 The TeXbook (Reading, Massachusetts: Addison-Wesley, 1984), 
 TeX: The Program (Reading, Massachusetts: Addison-Wesley, 1986), 
 The METAFONTbook (Reading, Massachusetts: Addison-Wesley, 1986), 
 METAFONT: The Program (Reading, Massachusetts: Addison-Wesley, 1986), 
 Computer Modern Typefaces (Reading, Massachusetts: Addison-Wesley, 1986),

Nombres surréels 
Un texte présentant de manière ludique les nombres surréels de Conway :
  ;
 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 
Knuth est également l'auteur de 3:16 Bible Texts Illuminated (1991) , dans lequel il tente d'examiner la Bible par une analyse du ,  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 

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, 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 
Donald Knuth a reçu plus d'une centaine de prix et d'honneurs dans le monde :

Prix

Sociétés savantes 
 1973 : Membre de l'Académie américaine des arts et des sciences dans la section Science physique et mathématique
 1975 : Membre de l'Académie nationale des sciences (Etats-Unis)
 1980 : Membre distingué de la British Computer Society
 1981 : Membre de l'Académie nationale d'ingénierie des États-Unis
 1982 : Membre de l'Association for Computing Machinery
 1982 : Membre d'honneur de l'Institute of Electrical and Electronics Engineers
 1992 : Associé étranger de l'Académie des sciences (France), élu le  dans la section Sciences mécaniques et informatiques
 1998 : Membre d'honneur du Musée de l'histoire de l'ordinateur
 1998 : Membre de l'Académie bavaroise des sciences
 2003 : Membre étranger de la Royal Scoiety
 2008 : Membre de l'Académie des sciences de Russie
 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
 Membre de l'American Mathematical Society
 Membre de l'Académie norvégienne des sciences et des lettres

Honneurs 
 1978 : Conférence Gibbs
 1993 : Professeur Emeritus de l'université Stanford
 2001 : L’astéroïde (21656) Knuth est nommé en son honneur
 2011 : 
 2016 : Conférence von Neumann
 
Il a reçu une multitude de Doctorat honoris causa :

Notes et références 

Certains renseignements viennent de son CV

Annexes

Articles connexes 
 Algorithme de Knuth-Morris-Pratt
 
 Algorithme de Knuth-Bendix
 Grammaire attribuée
 Metafont
 Notation des puissances itérées de Knuth
 Prix Donald E. Knuth
 TeX

Liens externes 

 
 
  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.
  Longue biographie de Knuth
  Conférences en ligne
  Knuth, entretiens en ligne
  Vidéos de présentations avec Donald Knuth
  La première analyse d'algorithme de Knuth

Boursier Guggenheim
Conférencier von Neumann
Docteur honoris causa de l'université Harvard
Docteur honoris causa de l'université Paris-Est-Marne-la-Vallée
Docteur honoris causa de l'université d'Oslo
Docteur honoris causa de l'université de Glasgow
Docteur honoris causa de l'université d'État de Saint-Pétersbourg
Docteur honoris causa de l'Université Concordia
Docteur honoris causa de l'École polytechnique fédérale de Zurich
Docteur honoris causa de l'université de Bordeaux
Hacker
Récipiendaire de la National Medal of Science
Lauréat de la médaille Franklin
Lauréat du prix de Kyoto
Lauréat du prix Harvey (Technion)
Lauréat du prix Turing
Lauréat du prix Leroy P. Steele
Mathématicien américain du XXIe siècle
Mathématicien américain du XXe siècle
Membre de l'Académie bavaroise des sciences
Membre de l'Académie des sciences (France)
Membre de l'Académie norvégienne des sciences et des lettres
Membre de l'American Mathematical Society
Membre de l'Académie nationale des sciences
Membre de la Société américaine de philosophie
Membre étranger de l'Académie des sciences de Russie
Membre étranger de la Royal Society
Naissance en janvier 1938
Naissance à Milwaukee
Personnalité américaine de l'informatique
Personnalité en informatique théorique
Personnalité en langages de programmation
Personnalité en méthodes formelles
Personnalité liée au logiciel libre
Professeur à l'université Stanford
Étudiant de l'université Case Western Reserve
Étudiant du California Institute of Technology