Donald Knuth

Donald Ervin Knuth
Donald Knuth lors d'une réception pour le Open Content Alliance, le 25 Octobre, 2005
Né	(10/01/1938) Janvier 10, 1938 Milwaukee, Wisconsin, États-Unis
Résidence	États-Unis
Nationalité	Américain
Les champs	Mathématiques Informatique
Institutions	Université de Stanford
Alma mater	Case Institute of Technology California Institute of Technology
Conseiller de doctorat	Marshall Hall, Jr.
Doctorants	Leonidas J. Guibas Michael Fredman Scott Kim Vaughan Pratt Robert Sedgewick Jeffrey Vitter Andrei Broder
Connu pour	The Art of Computer Programming TeX , METAFONT Algorithme Knuth-Morris-Pratt Algorithme de Knuth-Bendix MMIX
Prix remarquables	Prix Turing (1974) John von Neumann Médaille (1995) Prix Harvey (1995) Prix de Kyoto (1996)
Site Web
Donald E. Knuth

Donald Ervin Knuth (pron .: / k ə n U θ / Nooth kə-; né le 10 Janvier, 1938) est un informaticien et Professeur émérite à L'Université de Stanford.

Il est l'auteur de l'œuvre multi-volume séminal L'Art de la programmation informatique. Knuth a été appelé le "père" de la analyse d'algorithmes. Il a contribué au développement de l'analyse rigoureuse de la complexité de calcul des algorithmes et des techniques mathématiques formelles systématisées pour elle. Dans le processus, il a également popularisé le notation asymptotique.

En plus des contributions fondamentales dans plusieurs branches de informatique théorique, Knuth est le créateur de la TeX système informatique de composition, le connexes METAFONT langage de définition de police et le système de rendu et le Computer famille moderne de caractères.

Comme un écrivain et érudit, Knuth a créé le WEB / CWEB systèmes de programmation informatique conçu pour encourager et faciliter programmation littéraire, et conçu le MIX / MMIX jeu d'instructions architectures.

Jeunesse

Knuth est né en Milwaukee, Wisconsin, où son père possédait une petite entreprise d'impression et a enseigné la comptabilité au Milwaukee luthérienne High School, où il se est inscrit, gagner des prix d'excellence. Il a appliqué son intelligence de façon non conventionnelle, remportant un concours quand il était en huitième année en trouvant plus de 4500 mots qui pourraient être formés à partir des lettres de "Giant Bar de Ziegler"; les juges avaient seulement environ 2 500 mots sur leur liste de maître. Cela lui a gagné un poste de télévision pour son école et un bar de bonbons pour tout le monde dans sa classe.

Éducation

Knuth a eu un moment difficile de choisir la physique plus la musique comme son majeur à Case Institute of Technology (maintenant partie de Case Western Reserve University). Il a également rejoint Beta Nu chapitre de la Fraternité Theta Chi. Pendant ses études de physique à l'Case Institute of Technology, Knuth a été présenté au IBM 650, l'un des premiers mainframes. Après avoir lu le manuel de l'ordinateur, Knuth a décidé de réécrire l'assemblage et le code du compilateur pour la machine utilisée dans son école, parce qu'il croyait qu'il pouvait faire mieux. En 1958, Knuth construit un programme basé sur la valeur de chaque joueur qui pourrait aider son équipe de basket-ball de l'école remporter le championnat. Ce était si nouveau une proposition au moment où il se est repris et publié par Newsweek et également couverts par Walter Cronkite sur le CBS Evening Nouvelles. Knuth a été l'un des rédacteurs en chef fondateurs de la revue ingénierie et des sciences, qui a remporté un prix national comme meilleur magazine technique en 1959. Il a ensuite mis de la physique aux mathématiques, et en 1960, il a reçu son baccalauréat ès sciences, recevoir simultanément son maître ès sciences par un prix spécial de la faculté qui considérait son travail remarquable.

En 1963, il a obtenu un doctorat en mathématiques (conseiller: Marshall Hall) de la California Institute of Technology, et a commencé à y travailler en tant que professeur associé et a commencé à travailler sur L'Art de la programmation informatique. Il avait d'abord accepté une commission d'écrire un livre sur les compilateurs qui deviendra plus tard le multi-volumes The Art of Computer Programming. Ce travail a été prévu à l'origine pour être un seul livre, puis conçu comme un six, puis la série en sept volumes. En 1968, juste avant, il a publié le premier volume, Knuth a accepté un poste de travail sur les problèmes de la National Security Agency ( NSA) à travers leur FFRDC l'Institut for Defense Analyses ( IDA) Division de la recherche Communications situé à l'époque sur le campus de Princeton dans le bâtiment Von Neumann comme indiqué dans son cumulae vitae. Il semble probable Knuth a quitté son poste et a rejoint la faculté de Université de Stanford en raison de ses convictions politiques et le climat politique volatile sur le campus à l'époque.

Écrits

The Art of Computer Programming (TAOCP)

Informatique prenait alors ses premiers pas hésitants. "Ce était un domaine totalement nouveau," rappelle Knuth, "sans véritable identité. Et le niveau de publications disponibles ne était pas très élevé. Un grand nombre de documents qui sortaient étaient tout simplement faux. (...) Donc, une de mes motivations était de mettre directement une histoire qui avait été très mal dit ».

Après avoir produit le troisième volume de sa série en 1976, il a exprimé cette frustration à l'état naissant des outils d'édition électronique alors nouvellement développés (en particulier ceux qui ont contribué à photocomposeuses) qu'il a pris le temps de travailler sur la composition et a créé la TeX et Outils METAFONT.

À partir de 2012, les trois premiers volumes et la première partie du volume quatre de ses séries ont été publiées.

Autres œuvres

Il est également l'auteur de Numéros Surréaliste, un Novelette mathématique sur John Conway théorie des ensembles la construction d'un autre système de numéros. Au lieu d'expliquer simplement le sujet, le livre vise à montrer le développement des mathématiques. Knuth voulait que le livre pour préparer les étudiants à faire, la recherche créative originale.

En 1995 , Knuth a écrit la préface du livre A = B par Marko Petkovsek, Herbert Wilf et Doron Zeilberger.

Croyances religieuses et le travail

En plus de ses écrits sur la science informatique, Knuth, luthérien, est également l'auteur de 03h16 Bible Illuminated Textes, dans lequel il examine la Bible par un processus de échantillonnage systématique, à savoir une analyse du chapitre 3, verset 16 de chaque livre. Chaque verset est accompagné d'un rendu dans l'art calligraphique, contribué par un groupe de calligraphes sous la direction de Hermann Zapf.

Soucis de santé

En 2006, Knuth a été diagnostiqué avec cancer de la prostate. Il a été opéré en Décembre de cette année et a commencé à "un peu de la radiothérapie ... par mesure de précaution mais le pronostic semble assez bon", comme il l'a indiqué dans son autobiographie vidéo.

Rêveries informatiques

Knuth donne des conférences informelles quelques fois par année au Université de Stanford, où il a appelé Computer Rêveries. Il a également été professeur invité à la Oxford University Computing Laboratory dans le Royaume-Uni et d'un membre honoraire de Magdalen College.

Humour

Knuth est connu pour son "humour professionnel».

Un des Les chèques de fidélité de Knuth

"Niché parens »- Donald Knuth et Jacob Appelbaum

• Il avait l'habitude de payer les honoraires d'intermédiation de 2,56 $ pour des erreurs ou des erreurs découvertes dans ses livres typographiques, parce que "256 pennies est une hexadécimale dollar », et de 0,32 $ pour des« suggestions précieuses ". Selon un article paru dans le Massachusetts Institute of Technology Review de la technologie, ces Chèques de fidélité Knuth sont "parmi les trophées les plus prisés de computerdom". Knuth a dû arrêter d'envoyer des chèques réels en 2008 en raison de la fraude bancaire, et au lieu donne maintenant chaque viseur d'erreur un «certificat de dépôt» d'un équilibre cotée en bourse dans son fictive "Banque du San Serriffe ".
• Il a averti une fois un correspondant, "Méfiez-vous des bugs dans le code ci-dessus, je ne ai prouvé correct, pas essayé."
• La préface de Mathématiques Béton comprend l'anecdote suivante: «Quand Knuth enseigné Mathématiques concrètes à Stanford pour la première fois, il a expliqué le titre un peu étrange en disant que ce était sa tentative de donner un cours de mathématiques qui était difficile à la place du soft. Il a annoncé que, contrairement aux attentes de certains de ses collègues, il ne allait pas à enseigner la théorie de Agrégats, ni Embedding théorème de Pierre, ni même le Pierre-Čech compactification théorème. (Plusieurs étudiants de l' ingénierie civile département se sont levés et ont quitté la salle en silence.) "

• Knuth a publié son premier article «scientifique» dans un magazine de l'école en 1957 sous le titre " Système Potrzebie des poids et mesures. "Dans ce document, il a défini la unité fondamentale de la longueur que l'épaisseur de Mad # 26, et nommé l'unité fondamentale de la force "de whatmeworry." Mad publié l'article dans le numéro 33 (Juin 1957).
• L'article de Knuth de la complexité de calcul de chansons, " La complexité des Cantiques ", a été réimprimé deux fois dans des revues d'informatique.
• Pour démontrer le concept, Knuth intentionnellement visé "définition circulaire» et «Définition, circulaire" à l'autre de l'indice des The Art of Computer Programming, Volume 1.
• Au TUG Conférence 2010, Knuth a annoncé une XML-basée successeur de TeX, intitulé "Itex" (prononcé [Iː˨˩˦tɛks˧˥], avec une sonnerie de cloche), qui charge des fonctionnalités telles que les unités irrationnelles arbitrairement échelle, Impression 3D, d'animation et son stéréophonique.

Prix

En 1971, Knuth a été le récipiendaire de la première ACM Prix Grace Murray Hopper. Il a reçu plusieurs autres prix, dont le Turing Award, le National Medal of Science, le John von Neumann Médaille et le Prix Kyoto.

En reconnaissance de la contribution de Knuth au domaine de la science informatique, en 1990, il a reçu le titre académique one-of-a-kind du professeur de L'Art de la programmation informatique, qui a depuis été révisé pour le professeur Émérite de The Art of Computer Programming.

En 1992, il est devenu un associé de la Académie française des sciences. Cette même année, il se retira de la recherche et de l'enseignement régulier au Université de Stanford pour finir L'Art de la programmation informatique. En 2003, il a été élu membre étranger de la Royal Society.

Knuth a été élu Fellow (première classe de Fellows) de la Société de mathématiques appliquées et industrielles en 2009 pour ses contributions remarquables à mathématiques . Il est un membre de la Académie norvégienne des Sciences et des Lettres. En 2012 il est devenu un membre de la American Mathematical Society.

Honneurs accordés sur Knuth comprennent:

• Première ACM Grâce Murray Hopper Award, 1971
• Turing Award, 1974
• National Medal of Science, 1979
• Médaille Franklin, 1988
• John von Neumann Médaille, 1995
• Prix Harvey de la Technion, 1995
• Prix Kyoto, 1996
• Fellow de la Computer History Museum, 1998
• Prix Katayanagi 2010
• BBVA Frontiers Foundation Award de connaissances, 2010
• Stanford University School du Prix des héros en génie, 2011

Travaux

Une courte liste de ses œuvres:

• Donald E. Knuth, L'Art de la programmation informatique, Volumes 1-4, Addison-Wesley Professional

1. Volume 1: Algorithmes fondamentaux (3e édition), 1997. Addison-Wesley Professional, ISBN 0-201-89683-4
2. Volume 2: Seminumerical Algorithmes (3e édition), 1997. Addison-Wesley Professional, ISBN 0-201-89684-2
3. Volume 3: Tri et recherche (2e édition), 1998. Addison-Wesley Professional, ISBN 0-201-89685-0
4. Volume 4A: combinatoire Algorithmique, partie 1, 2011. Addison-Wesley Professional, ISBN 0-201-03804-8
5. Volume 4: Algorithmes combinatoires (le reste), en préparation

• Donald E. Knuth, The Art of Computer Programming, fascicules:

1. Volume 1, Fascicule 1: MMIX-A RISC ordinateur pour le nouveau millénaire, 2005. ISBN 0-201-85392-2
2. Volume 4, Fascicule 0: Introduction à combinatoires algorithmes et fonctions booléennes. 2008. ISBN 0-321-53496-4
3. Volume 4, Fascicule 1: astuces et techniques sur les bits; Binary Decision Diagrams. 2009. ISBN 0-321-58050-8
4. Volume 4, Fascicule 2: Génération toutes les lignes et de permutations, 2005. ISBN 0-201-85393-0
5. Volume 4, Fascicule 3: Génération de toutes les combinaisons et des partitions, 2005. ISBN 0-201-85394-9
6. Volume 4, Fascicule 4: Génération tous les arbres-Histoire de la combinatoire Generation, 2006. ISBN 0-321-33570-8

• Donald E. Knuth, Informatique & Composition:

1. Volume A, Le TeXbook (Reading, Massachusetts: Addison-Wesley, 1984), x + 483pp. ISBN 0-201-13447-0
2. Volume B, TeX: Le Programme (Reading, Massachusetts: Addison-Wesley, 1986), xviii + 600pp. ISBN 0-201-13437-3
3. Volume C, Le METAFONTbook (Reading, Massachusetts: Addison-Wesley, 1986), xii + 361pp. ISBN 0-201-13445-4
4. Volume D, METAFONT: Le programme (lecture, Massachusetts: Addison-Wesley, 1986), xviii + 566pp. ISBN 0-201-13438-1
5. Volume E, Ordinateur Polices de caractères modernes (Reading, Massachusetts: Addison-Wesley, 1986), xvi + 588pp.

• Knuth, Donald E. Sélectionné Série de documents

1. Donald E. Knuth, Programmation Littéraire (Stanford, en Californie: Centre pour l'étude de la langue et de l'information - Lecture Notes CSLI, non. 27), 1992. ISBN 0-937073-80-6
2. Donald E. Knuth, Selected Papers sur Informatique (Stanford, Californie: Centre pour l'étude de la langue et de l'information - Lecture Notes CSLI, n ° 59.), 1996. ISBN 1-881526-91-7
3. Donald E. Knuth, typographie numérique (Stanford, Californie: Centre pour l'étude de la langue et de l'information - Lecture Notes CSLI, pas 78.), 1999. ISBN 1-57586-010-4
4. Donald E. Knuth, Selected Papers sur analyse des algorithmes (Stanford, Californie: Centre pour l'étude de la langue et de l'information - Lecture Notes CSLI, n ° 102.), 2000. ISBN 1-57586-212-3
5. Donald E. Knuth, Selected Papers sur Ordinateur Langues (Stanford, Californie: Centre pour l'étude de la langue et de l'information - Lecture Notes CSLI, pas 139.), 2003. ISBN 1-57586-381-2 (tissu), ISBN 1-57586-382-0 (broché)
6. Donald E. Knuth, Selected Papers sur mathématiques discrètes (Stanford, Californie: Centre pour l'étude de la langue et de l'information - Notes de cours CSLI, pas 106.), 2003. ISBN 1-57586-249-2 (tissu), ISBN 1-57586-248-4 (broché)
7. Donald E. Knuth, Selected Papers sur la conception d'algorithmes (Stanford, Californie: Centre pour l'étude de la langue et de l'information - Notes de CSLI de cours, pas 191.), 2010. ISBN 1-57586-583-1 (tissu), ISBN 1-57586-582-3 (broché)
8. Donald E. Knuth, Selected Papers sur Fun and Games (Stanford, Californie: Centre pour l'étude de la langue et de l'information - Lecture Notes CSLI, pas 192.), 2011. ISBN 978-1-57586-585-0 (tissu), ISBN 978-1-57586-584-3 (livre de poche)
9. Donald E. Knuth, Companion aux documents de Donald Knuth (Stanford, Californie: Centre pour l'étude de la langue et de l'information - Lecture Notes CSLI, pas 202.), 2011. ISBN 978-1-57586-635-2 (tissu), ISBN 978-1-57586-634-5 (livre de poche)

• Graham, Ronald L .; Knuth, Donald E .; Patashnik, Oren (1994). Mathématiques Béton: Une fondation pour l'informatique (deuxième éd.). Lire, MA: Addison-Wesley Publishing Company. pp. xiv + 657. ISBN 0-201-55802-5. M 1397498.  
• Donald E. Knuth, chiffres surréalistes: Comment deux ex-étudiants activé pour Mathématiques pures et trouvé le bonheur total. 1974, ISBN 0-201-03812-9. Plus d'informations peuvent être trouvées à site officiel du livre
• Donald E. Knuth, The Stanford GraphBase: Une plateforme pour combinatoire Informatique (New York, ACM Press) 1993. seconde poche impression 2009. ISBN 0-321-60632-9
• Donald E. Knuth, 03:16 Textes Bible Illuminated (Madison, Wisconsin: AR Editions), 1990. ISBN 0-89579-252-4
• Donald E. Knuth, Les choses ingénieur en informatique parle rarement (Centre pour l'étude de la langue et de l'information - Notes de CSLI Conférence n ° 136), 2001. ISBN 1-57586-326-X