<page> <title>Donald Knuth</title> <id>15911</id> <revision> <id>31403617</id> <timestamp>2008-07-08T11:54:47Z</timestamp> <contributor> <ip>220.45.27.112</ip> </contributor> <comment>ortho</comment> <text xml:space="preserve">[[Image:Donald Knuth DSC00624.jpg|thumb|right|Donald Knuth]] '''Donald Ervin Knuth''' ({{IPA|[kəˈnuËθ]}}<ref name="FAQ">[http://www-cs-faculty.stanford.edu/~knuth/faq.html "Frequently Asked Questions" sur la page personnelle de Knuth]. La prononciation proposée est Ka-NOUSS.</ref>) ([[10 janvier]] [[1938]] à [[Milwaukee]], [[Wisconsin]] - ) est un [[informatique|informaticien]] américain de renom et [[professeur émérite]] en [[informatique]] à l'[[université de Stanford]]<ref>{{en}} [http://www-cs-faculty.stanford.edu/~knuth/ http://www-cs-faculty.stanford.edu/~knuth/].</ref> (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]]. Il est l'auteur d'une centaine d'articles et d'une dizaine de livres sur l'algorithmique et les mathématiques discrètes ; les 3 premiers volumes de ''The Art of Computer Programming'' (le quatrième volume est inachevé à l'heure actuelle bien que commencé il y a presque 40 ans) demeurent des ouvrages de référence, ce qui est exceptionnel dans une science comme l'informatique, qui évolue très rapidement. Afin d'avoir d'une bonne qualité de mise en page pour la deuxième édition de son ''The Art of Computer Programming'', Knuth a créé 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 l'a également poussé à créer la police ''[[Computer Modern]]'', police par défaut de TeX. == Biographie == Né à [[Milwaukee]], dans le [[Wisconsin]], Knuth a reçu 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]] en 1960 du Case Institute of Technology (devenu depuis [[université Case Western Reserve]]). Sa première analyse d'algorithme remonte à l'été 1962. Knuth découvre à cette occasion un lien entre l'efficacité d'un [[fonction de hachage|algorithme de hachage]] et des mathématiques remontant à [[Srinivasa Ramanujan|Ramanujan]]. Il obtient ensuite son Ph.D ([[doctorat]]) en [[mathématiques]] au [[California Institute of Technology]] en [[1963]]. En [[1968]], il devient membre de la faculté de l'université de Stanford, où il a préalablement reçu un titre académique créé à son intention : ''Professor Emeritus of the Art of Computer Programming''. En [[1971]], Knuth est le premier à recevoir le prix [[Association for Computing Machinery|ACM]] ''[[Grace Hopper|Grace Murray Hopper]] Award''. Il a reçu de nombreuses autres distinctions honorifiques, entre autres le [[prix Turing]], la [[National Medal of Science]], la [[médaille John von Neumann]]<ref>[http://www.ieee.org/portal/pages/about/awards/pr/vonneupr.html Liste des lauréats de la médaille John von Neumann]</ref> 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 (France)|Académie des sciences]] [[France|française]] en [[1992]] et membre de la [[Royal Society]] en [[2003]]. Il est marié à Nancy Jill Carter, et a deux enfants, John et Jennifer. == 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 [[Algorithme de recherche de sous-chaîne|recherche de sous-chaîne]] * l'[[Knuth-Bendix (algorithme)|algorithme de 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]]. [[Image:Computer modern sample.svg|thumb|right|La police de caractères Computer Modern]] Knuth, mécontent de la façon dont étaient imprimés ses livres, consacra plusieurs années de sa vie, à partir de 1977, pour é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 [[Standard Generalized Markup Language|SGML]], qui permet de se concentrer sur la structure du document et laisser 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 [[Logiciel libre|logiciels libres]], ou presque. En effet, la seule restriction que Knuth imposait à toute modification est qu'elle ne prît pas le nom de TeX. Le logiciel fut donc repris et amélioré par [[Leslie Lamport]] pour devenir [[LaTeX]]. [[Metafont]] est un langage utilisé pour composer des polices matricielles qui fut utilisé par Knuth pour créer la police [[:en:Computer Modern]]. Il a été développé en même temps que TeX. Le langage Metafont a lui 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. Parmi ceux-ci on peut citer : * les analyseurs de [[grammaire formelle|grammaires formelles]] LR(k) ; * la méthode des [[Grammaire attribuée|attributs sémantiques]] en [[compilateur|compilation]] ; * le concept de [[programmation lettrée]] (''literate programming''). == Ouvrages == === ''[[The Art of Computer Programming]]'' === Knuth est connu comme l'auteur de l'ouvrage ''[[The Art of Computer Programming]]'' (couramment appelé ''TAOCP''), une des références dans le domaine de l'[[informatique]], pour ne pas dire ''la bible'' (un mot cher à Knuth…) des informaticiens. Ce livre a établi un domaine : l'[[algorithmique|analyse d'algorithmes]] qui consiste à se servir des [[mathématiques]] pour étudier les performances (en temps, mémoire…) d'un [[Algorithmique|algorithme]] sur l'ensemble de ses exécutions possibles. Cet ''Art de Programmer'' que promeut Knuth consiste en le message suivant : plutôt que de ''hacker'' en assembleur et de faire gagner quelques secondes au programme (ce serait une optimisation qui a son mérite mais qui n'est pas universelle ni pérenne car elle dépend trop de la machine sur lequel tournera l'algorithme), il vaut mieux prendre du recul sur le problème considéré, en extraire les structures combinatoires en jeu, étudier via les outils mathématiques ad hoc les propriétés typiques de ces structures (Knuth établit très souvent le comportement en moyenne en utilisant des techniques de [[série génératrice|séries génératrices]]), ce qui permet au final de mieux affûter l'algorithme à utiliser, et d'avoir ainsi de gigantesques gains d'efficacité. C'est également là le sens qu'il faut donner à son aphorisme {{citation|L'optimisation prématurée est la racine de tous les maux (ou presque) en programmation}}. Knuth consacre désormais presque toute son énergie à achever les 7 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), 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 === Autres livres === Knuth est également l'auteur de ''3:16 Bible Texts Illuminated'' ([[1991]]), ISBN 0895792524, 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 calligraphistes dirigés par [[Hermann Zapf]]. L'ouvrage n'a pas été traduit en français. == Personnel == === Un geek === Knuth est une [[:Catégorie:Personnalité en informatique|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 sous prétexte 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 [[Base naturelle des logarithmes|e]]. Il a également mis en garde les utilisateurs d'un de ses logiciels ainsi : « Faites attention aux [[Bogue (informatique)|bugs]] dans ce code ; je n'ai fait que démontrer qu'il était correct, je ne l'ai pas essayé » <ref>[http://www-cs-faculty.stanford.edu/~knuth/faq.html FAQ sur le site personnel de Donald Knuth]</ref>). Knuth a cessé d'utiliser le [[courrier électronique]] en prétendant 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 [[Traitement par lots|batch]] », et y consacrer une journée tous les trois mois, en répondant par courrier « classique ». === Anecdotes === Knuth apprécie la musique et aime en particulier jouer de l'[[orgue]]. Dans sa propre maison, il dispose d'un orgue qu'il a construit lui-même. Knuth nie cependant avoir tout talent particulier pour jouer de cet instrument. Il est marié à [[Jill Knuth]], qui a publié un livre sur la [[liturgie]] et réalisé les illustrations du livre sur les [[nombres surréels]]<ref>Donald Ervin Knuth, [http://www-cs-faculty.stanford.edu/~uno/sn.html ''Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness : A Mathematical Novelette''], Addison-Wesley Professional (1974) - ISBN 0201038129</ref>. Ils ont deux enfants. Avec elle, il collectionne les photographies de panneaux de signalisation routière (signalisation de danger de forme losangée) américain, s'intéressant évidemment aux plus surprenants<ref>[http://www-cs-faculty.stanford.edu/~uno/diamondsigns/diam.html site des panneaux.]</ref>. Knuth a publié son premier article dans un magazine scolaire en [[1957]]. À forte teneur humoristique, celui-ci a été publié dans le numéro de juin 1957 du magazine américain ''MAD''. == Citations == *{{citation|Attention aux bugs dans le code ci-dessus. Je ne l'ai pas testé, j'ai seulement prouvé qu'il était correct.}} *{{citation|La science est ce que nous comprenons suffisamment bien pour l'expliquer à un ordinateur. L'art, c'est tout ce que nous faisons d'autre.}} ([[1996]])<ref>Avant-propos au livre [http://www.cis.upenn.edu/~wilf/AeqB.html A=B]</ref> *{{citation|L'optimisation prématurée est la racine de tous les maux (ou presque) en programmation.}}<ref>"Computer Programming as an Art" discours de réception du [[Turing Award]] [[1974]]</ref> *{{citation|Je définis Unix comme ''30 définitions différentes des expressions régulières vivant sous le même toit''.}}<ref>chapitre 33 du livre ''Digital Typography'', p. 649.</ref> *{{citation|Une formule mathématique ne devrait jamais être la "propriété" de qui que ce soit ! Les mathématiques appartiennent à Dieu.}}<ref>chapitre 1 du livre ''Digital Typography'', p. 8.</ref> == Récompenses == * [[Association for Computing Machinery|ACM]] [[Prix Grace Murray Hopper]], [[1971]] * [[Prix Turing]], [[1974]] * [[National Medal of Science|Médaille nationale de la science]], [[1979]] * [[Médaille Franklin]], [[1988]] * [[Médaille John von Neumann]], [[1995]] * Prix Harvey du [[Technion|Institut de technologie d'Israël]], [[1995]] * [[Prix Kyoto]], [[1996]] == Voir aussi == === Liens internes === * [[Algorithme de Knuth-Morris-Pratt]] * [[Algorithme de Trabb Pardo-Knuth]] * [[Knuth-Bendix (algorithme)|Procédure de Knuth-Bendix]] * [[Notation des puissances itérées de Knuth]] * [[Prix Knuth]] === Liens externes === * {{en}} [[q:en:Donald Knuth|Wikiquote - Citations de Donald Knuth]] * {{en}} [http://www-cs-faculty.stanford.edu/~knuth/ La page web de Donald Knuth à l'université de Stanford] * {{en}} [http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Knuth.html Une longue biographie de Knuth] * {{en}} [http://scpd.stanford.edu/knuth/ Vidéos de présentations avec Donald Knuth] * {{en}} [http://algo.inria.fr/AofA/Research/11-97.html La première analyse d'algorithme de Knuth] === Références === {{reflist}} Certains renseignements viennent de son [http://www-cs-staff.stanford.edu/~uno/vita.pdf CV] {{pdf}}. {{Lauréats du prix Turing}} {{Portail|informatique}} {{DEFAULTSORT:Knuth, Donald}} [[Catégorie:Personnalité américaine en informatique]] [[Catégorie:Mathématicien américain]] [[Catégorie:Naissance en 1938]] [[Catégorie:Personnalité en informatique dans le domaine du libre]] [[Catégorie:Personnalité en informatique théorique]] [[Catégorie:Personnalité en langages de programmation]] [[Catégorie:Personnalité en méthodes formelles]] [[Catégorie:Lauréat du prix Turing]] [[Catégorie:Médaille nationale des sciences]] [[Catégorie:Hacker]] [[Catégorie:Membre de la Royal Society]] [[ar:دونالد كانوث]] [[ast:Donald Knuth]] [[bg:Доналд Кнут]] [[bn:ডোনালà§à¦¡ কানà§à¦¥]] [[ca:Donald Knuth]] [[cs:Donald Ervin Knuth]] [[da:Donald E. Knuth]] [[de:Donald Ervin Knuth]] [[en:Donald Knuth]] [[eo:Donald Knuth]] [[es:Donald Knuth]] [[eu:Donald Knuth]] [[fa:دانلد کنوت]] [[fi:Donald Knuth]] [[he:×“×•× ×œ×“ ×§×× ×•×ª']] [[hu:Donald Knuth]] [[id:Donald Knuth]] [[is:Donald Knuth]] [[it:Donald Knuth]] [[ja:ドナルド・クヌース]] [[jv:Donald Knuth]] [[ka:დáƒáƒœáƒáƒšáƒ“ კნუთი]] [[ko:ë„ë„드 í¬ëˆ„스]] [[lb:Donald E. Knuth]] [[li:Donald Knuth]] [[ml:ഡൊണാളàµâ€à´¡àµ നൂതàµà´¤àµ]] [[mr:डोनालà¥à¤¡ कà¥à¤¨à¥à¤¥]] [[nl:Donald Knuth]] [[no:Donald Knuth]] [[pl:Donald Knuth]] [[pt:Donald Knuth]] [[ro:Donald E. Knuth]] [[ru:Кнут, Дональд Ðрвин]] [[sh:Donald Knuth]] [[sk:Donald Ervin Knuth]] [[sl:Donald Knuth]] [[sr:Donald Knut]] [[sv:Donald Ervin Knuth]] [[th:โดนัลด์ คนูธ]] [[tl:Donald Knuth]] [[tr:Donald Knuth]] [[vi:Donald Knuth]] [[zh:高德纳]]</text> </revision> </page>