Donald Knuth

Donald Knuth

Nom original	(en) Donald Ervin Knuth
Biografia
Naixement	10 gener 1938 (86 anys) Milwaukee (Wisconsin)
Catedràtic
Dades personals
Religió	Luteranisme
Formació	Institut Tecnològic de Califòrnia - matemàtiques (1960–1963) Universitat Case Western Reserve - matemàtiques (–1960) Milwaukee Lutheran High School (–1956)
Tesi acadèmica	Finite Semifields and Projective Planes  (1963 )
Director de tesi	Marshall Hall
Activitat
Camp de treball	Combinatòria, ciències de la computació i anàlisi d'algorismes
Lloc de treball	Stanford
Ocupació	matemàtic, professor d'universitat, enginyer, acadèmic, programador, historiador de les matemàtiques, escriptor, informàtic, creador tipogràfic
Ocupador	Institut d'Anàlisi de la Defensa (1968–1969) Burroughs Corporation (1960–1968) Universitat Stanford Institut Tecnològic de Califòrnia
Membre de	Societat Americana de Matemàtiques (Membre de la Societat Americana de Matemàtiques) (2012–) Societat Filosòfica Americana (2012–) Societat de Matemàtiques Aplicades i Industrials (membre de la Societat de Matemàtiques Aplicades i Industrials) (2009–) Acadèmia de Ciències de Rússia (membre estranger) (2008–) Royal Society (Membre estranger de la Royal Society) (2003–) Acadèmia Bavaresa de Ciències (1998–) Association for Computing Machinery (membre de l'Association for Computing Machinery) (1994–) Acadèmia Francesa de les Ciències (membre estranger) (1992–) Institut d'Enginyers Elèctrics i Electrònics (1982–) Association for Computing Machinery (1982–) Acadèmia Nacional d'Enginyeria (1981–) Acadèmia Nacional de Ciències dels Estats Units (membre de l'Acadèmia Nacional de Ciències dels Estats Units) (1975–) Acadèmia Americana de les Arts i les Ciències (1973–) Acadèmia Noruega de Ciències i Lletres British Computer Society Societat Matemàtica de Londres
Instrument	Orgue
Obra
Obres destacables programació literària WEB CWEB (1968) The Art of Computer Programming (1978) TeX (1979) METAFONT (1985) Computer Modern
Estudiant doctoral	Leonidas John Guibas, Michael Fredman, Scott Kim, Vaughan Pratt, Robert Sedgewick, Jeffrey Vitter, Andrei Broder, Bernard Marcel Mont-Reynaud, Luis Trabb Pardo, Gary Don Knott, John Fredrick Reiser, Lyle Harold Ramshaw, Christopher John Van Wyk, Ignacio Andrés Zabala Salelles, Mark Robbin Brown, Franklin Mark Liang, John Douglas Hobby, Pang-Chieh Chen, Ramsey Wadi Haddad, Tomas Feder, Richard Lee Sites, Daniel Hill Greene, Michael Frederick Plass, Clark Allan Crane, Isu Fang, Edwin Hallowell Satterthwaite, Jr., Wayne Theodore Wilner, Richard Eric Sweet, Bruce Guenther Baumgart, Ashok Subramanian, Steven Ira Gallant i Anil Ramesh Gangolli
Localització dels arxius	Museu d'Història de l'Ordinador
Premis
(2016)  Conferenciant John von Newmann../... 29+
Lloc web	www-cs-faculty.stanford.edu…

Donald Ervin Knuth (Wisconsin, 10 de gener de 1938) és professor emèrit de la Universitat Stanford i un dels experts en ciències de la computació més coneguts del món. Se'l coneix principalment com a autor de l'obra The Art of Computer Programming, una de les referències més respectades en el camp de les ciències de la computació. Pràcticament, va crear el camp d'anàlisi d'algorismes i va fer moltes aportacions transcendentals en diverses branques teòriques de la ciència de la computació. És el creador del sistema tipogràfic TeX i del sistema de disseny Metafont, i fou un dels precursors en l'estil de programació literària. També és l'autor de 3:16 Bible Texts Illuminated (1991, ISBN 0-89579-252-4), llibre en el qual intenta examinar la Bíblia per un procés de mostreig estratificat aleatori. És a dir, una anàlisi del capítol 3, versicle 16 de cada llibre. Està casat amb Jill Knuth, que va publicar un llibre sobre litúrgia, i té 2 fills.

Biografia

Infància i estudis

Nascut a Milwaukee, Wisconsin, Knuth va rebre la seva llicenciatura summa cum laude i el seu màster (tots dos simultàniament, el jurat va considerar el seu treball de llicenciatura com a equivalent a un M.Sc.) en matemàtiques del Case Institute of Technology. (ara Universitat Case Western Reserve) el 1960.

La seva primera anàlisi d'algoritmes es remunta a l'estiu de 1962. Aleshores va quedar impressionat per un treball de l'informàtic soviètic Andreï Ershov.

En aquesta ocasió, Knuth va descobrir un vincle entre l'eficiència d'un algorisme hashing i les matemàtiques que es remunta a Ramanujan.

El 1963, va defensar amb èxit el seu doctorat. D. (PhD) en matemàtiques a l'Institut Tecnològic de Califòrnia.^[1][2]

Carrera acadèmica

El 1968, es va convertir en membre de la facultat de la Universitat Stanford, on finalment va rebre un títol acadèmic creat per a ell: Professor Emèrit de l' Art de la Programació d' Computadors. El 1971, Knuth va ser el primer destinatari del premi Grace Murray Hopper de l'Association for Computing Machinery (ACM). Va rebre nombrosos altres honors, com ara el Premi Turing, la Medalla Nacional de la Ciència (Estats Units), la Medalla John von Neumann ^[3] de l'IEEE, així com el Premi Kyoto i la Medalla Franklin . Va ser escollit membre associat de l'Acadèmia Francesa de les Ciències el 1992 i membre de la Royal Society el 2003.

Personalitat

xec de recompensa 2,56 dòlars de Donald Knuth per trobar un error en un dels seus llibres.

Knuth és una figura de la informàtica coneguda pel seu humor friki: per exemple, ofereix una bonificació de 2,56 dòlars per cada error tipogràfic descobert als seus llibres, explicant que «256 cèntims fan un dòlar hexadecimal» (per als errors de la seva obra 3:16 Bible Texts Illuminated, però, la prima és de 3,16 dòlars). Els números de versió de TeX convergeixen a pi, és a dir, les versions es succeeixen així: " 3 ", " 3.1 ", " 3.14 », etc., els números de versió de Metafont convergeixen cap al Nombre e. També va advertir als usuaris d'un dels seus programes : " Atenció als errors d'aquest codi ; Només vaig demostrar que era correcte, no ho vaig provar».^[4]

Knuth va deixar d'utilitzar el correu electrònic, dient que l'havia utilitzat entre 1975 i l'11 de gener de 1990, i això va ser suficient per a tota la vida. Ell troba més eficient mantenir una correspondència en "mode per lots ”, i dedicar-hi un dia cada sis mesos, responent el correu clàssic.^[5]

Vida personal, altres signes d'humor

Donald Knuth

Knuth és autor d'un centenar d'articles i d'uns deu llibres sobre algorismes i matemàtiques discretes; els tres primers volums, amb les parts ja publicades del volume 4 (4A i 4B) de The Art of Computer Programming (TAOCP), continuen sent obres de referència.

Per tal de tenir una bona qualitat de disseny per a la segona edició del seu TAOCP, Knuth va crear dos programes de programari lliure, posteriorment àmpliament utilitzats en tipografia i matemàtiques professionals, TeX i Metafont. El seu interès per la tipografia també el va portar a crear el tipus de lletra Computer Modern, el tipus de lletra predeterminat de TeX.

A Knuth li agrada la música i sobretot li agrada tocar l'orgue. En va fer construir un a casa seva.^[6] Knuth fa al·lusió al seu orgue a l'índex del volum 3 de The Art of Computer Programming: l'entrada Royalties, fa referència al gràfic disposició de tubs d'orgue.

Està casat amb Nancy Jill Carter,^[7] que va publicar un llibre sobre la litúrgia i va fer les il·lustracions del llibre sobre números surrealistes.^[8] Tenen dos fills. Amb ella va recollir fotografies de senyals de trànsit americans (senyals de perill en forma de diamant), centrant-se en els més sorprenents.^[9]

Knuth va publicar el seu primer article (que tenia un fort contingut humorístic) al número de juny de 1957 de la revista estatunidenca Mad.

Després d'un error tipogràfic en la delta minúscula (δ), Knuth va apel·lar a corregir el problema i va demanar que actualitzés la tipografia Computer Modern, dient que «no suportava escriure documents amb aquest símbol, ara no suporta llegir documents que encara el fan servir».^[10]

Obres

El treball de Donald Knuth es refereix especialment als algorismes i a les matemàtiques discretes, però també va crear programari que encara s'utilitza àmpliament avui en dia, TeX i Metafont.

Aportacions a les matemàtiques

• Notació de fletxa de Knuth ;
• Obres sobre les Taules de Young.

Aportacions als algorismes

Don Knuth és el creador d'uns quants algorismes que porten el seu nom, entre ells :

• l' algorisme de Knuth–Morris–Pratt, algorisme de cerca de subcadenes;
• Cerca en profunditat: Algorisme recursiu de Knuth;
• l'algorisme RSK;
• la finalització de Knuth-Bendix.

Programari TeX i Metafont

La tipografia d'ordinador moderna.

Knuth és el creador del sistema de composició de documents TeX i del sistema de creació de fonts Metafont.

Insatisfet amb la manera d'imprimir els seus llibres, va dedicar uns quants anys de la seva vida, a partir de 1977, a escriure programari que li permetés obtenir una representació correcta de fórmules matemàtiques per a la tipografia professional. Es tracta d'un llenguatge de marques com SGML, que permet centrar-se en l'estructura del document, deixant el treball de maquetació al compilador. L'objectiu de Knuth quan va crear TeX era tenir un llenguatge de descripció de contingut que oferís una representació d'alta qualitat amb el mínim esforç i que fos independent de l'arquitectura del maquinari. Subministrat amb les seves fonts, TeX és un dels primers programari lliure, o gairebé. De fet, l'única restricció que Knuth imposa a qualsevol modificació és que no pren el nom de TeX. Avui dia, hi ha diverses extensions de TeX, les més populars són pdfTeX, XeTeX i LuaTeX.

Metafont és un llenguatge utilitzat per compondre fonts ràster. Desenvolupat al mateix temps que TeX, va ser utilitzat per Knuth per crear el tipus de lletra Computer Modern. El llenguatge Metafont també va donar lloc a MetaPost, que permet produir figures PostScript a partir d'una descripció geomètrica.

Altres idees destacades

Knuth és el creador de molts conceptes de programació. Podem citar:

• analitzadors gramaticals formals LR(k);
• el mètode dels atributs semàntics en la compilació;
• el concepte de programació alfabetitzada .

L'art de la programació d'ordinadors

Knuth és conegut com l'autor de The Art of Computer Programming (TAOCP), un dels referents en el camp de la informàtica. Aquest llibre va establir anàlisi d'algorismes, que consisteix a utilitzar les matemàtiques per estudiar el rendiment (en el temps, la memòria, etc.) d'un algorisme sobre totes les seves possibles execucions.

A principis del segle XXI, Knuth dedica ara quasi tota la seva energia a completar els set volums de TAOCP (la primera edició del primer volum data de 1968 i només han aparegut els tres primers volums, així com tres fascicles del quart volum).

Informàtica i composició

Aquest és el conjunt format per :

• ’‘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, Mass: Addison-Wesley, 1986),ISBN 0-201-13445-4
• ’‘METAFONT: The Program (Reading, Massachusetts: Addison-Wesley, 1986),ISBN 0-201-13438-1
• ’‘Tipus de lletra informàtics moderns (Reading, Massachusetts: Addison-Wesley, 1986),ISBN 0-201-13446-2

Nombres surrealistes

Un text que presenta els números surrealistes de Conway d'una manera divertida:

• Knuth, Donald Ervin. Surreal Numbers : How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness : A Mathematical Novelette (en anglès). Addison-Wesley Professional, 1974, p. 119. ISBN 0-201-03812-9. ;

Altres llibres

Knuth també és l'autor de 3:16 Bible Texts Illuminated (1991)ISBN 0-89579-252-4, en què intenta examinar la Bíblia mitjançant una anàlisi del capítol 3, verset 16 de cada llibre. Cada vers s'acompanya d'una cal·ligrafia produïda per un grup de cal·lígrafs dirigits per Hermann Zapf.

El llibre Elements for a History of Computing, publicat per CLSI Publications (Stanford) i la Société Mathématique de France (2011), reuneix uns quants articles de Donald Knuth sobre la història de la computació, escollits i traduïts per Patrick Cégielski, i en part reescrits sobre aquesta ocasió.

Treballant amb Ronald Graham i Oren Patashnik, va desenvolupar les seccions de matemàtiques de TAOCP com a llibre de cursos de combinatòria, titulat Matemàtiques concretes .

Honors

Donald Knuth ha rebut més d'un centenar de premis i honors arreu del món.^[11][12]

Premis

• 1971: Premi Grace Murray Hopper de l'Association for Computing Machinery
• 1972: Borsa Guggenheim
• 1974: Premi Turing per The Art of Computer Programming^[11]
• 1975: Premi Halmos-Ford
• 1979: National Medal of Science, lliurat pel President dels États-Unis Jimmy Carter el 14 gener 1980^[13]
• 1980: Premi W. Wallace McDowell
• 1986: Premi ACM Software System pel projecte TeX^[14]
• 1986: Premi Leroy P. Steele^[15]
• 1988: Medalla Franklin de l'Institut Franklin^[16]
• 1993: Premi Halmos-Ford
• 1994: Medalla Adelskold de l'Reial Acadèmia Sueca de Ciències^[12]
• 1995: Medalla John von Neumann de l'Institute of Electrical and Electronics Engineers^[17]
• 1995: Premi Harvey de l'Institut de Tecnologia d'Israel^[18]
• 1996: Premi Kyoto a la categoria Ciències de la informació
• 2006: Medalla d'or de la universitat d'Estat d'enginyeria d'Armènia^[12]
• 2006: Medalla d'or de la universitat d'Estat d'Erevan^[12]
• 2010: Premi Katayanagi^[19]
• 2010: Premios Fundación BBVA Fronteras del Conocimiento^[20]
• 2011: Medalla Faraday de l'|Institution of Engineering and Technology.^[21]
• 2011: Premi Hero Stanford University School of Engineering^[22]
• 2018: Premi Trotter (Texas A&M)

Va rebre multitud de doctors’‘honoris causa :

• 1986 : Universitat de París Sud (Orsay)
• 1991 : Université Concordia^[23]
• 1993 : Université de Marne-la-Vallée^[24]
• 1996 : Universitat Masaryk^[25]
• 2000 : Universitat de Waterloo^[12]
• 2001 : Universitat de Tübingen^[12]
• 2002 : Universitat d'Oslo^[26] · ^[27]
• 2003 : Universitat Harvard^[28]
• 2003 : Universitat d'Anvers^[29]
• 2003 : Universitat de Macrdònis^[12]
• 2004 : Faculté des arts et des sciences de la universitat de Montreal^[12]
• 2005 : ETH Zürich^[30]
• 2006 : Universitat de Wisconsin^[12]
• 2007 : Universitat Bordeaux I^[31]
• 2011 : Universitat de Glasgow^[26]
• Universitat Estatal de Sant Petersburg^[26]
• Universitat de Stony Brook^[23]

Societats erudites

• 1973: Membre de l'Acadèmia Americana d'Arts i Ciències a la secció de Ciències Físiques i Matemàtiques ^[32]
• 1975: Membre de l'Acadèmia Nacional de Ciències (Estats Units) ^[33]
• 1980: Membre distingit de la British Computer Society ^[26]
• 1981: Membre de l' Acadèmia Nacional d'Enginyeria dels Estats Units ^[34]
• 1982: Membre de l'Associació de Maquinària Informàtica ^[11]
• 1982: Membre honorari de l'Institut d'Enginyers Elèctrics i Electrònics ^[35]
• 1992: Associat estranger de l'Acadèmia de Ciències (França), escollit el 30 març 1992}} a la secció de Ciències Mecàniques i Informàtiques ^[36]
• 1998: Membre honorari del Museu d'Història de la Computació ^[37]
• 1998: Membre de l'Acadèmia de Ciències de Baviera ^[38]
• 2003: membre estranger de la Royal Society ^[39]
• 2008: Membre de l'Acadèmia Russa de Ciències ^[40]
• 2009: Membre de la Society for Industrial and Applied Mathematics
• 2012: Membre de l'American Philosophical Society
• 2015: Membre honorari de la London Mathematical Society ^[12]
• Membre de la Societat Americana de Matemàtiques
• Membre de l'Acadèmia Noruega de Ciències i Lletres ^[41]

Referències

1. «Donald Ervin Knuth | American mathematician and computer scientist» (en anglès). Encyclopedia Britannica. [Consulta: 10 gener 2020].
2. «Donald E. Knuth | Encyclopedia.com» (en anglès americà). www.encyclopedia.com. [Consulta: 10 gener 2020].
3. Liste des lauréats de la médaille John von Neumann.
4. FAQ sur le site personnel de Donald Knuth Arxivat 2008-03-06 a Wayback Machine..
5. «FAQ sur le site personnel de Donald Knuth». Arxivat de l'original el 2007-08-11. [Consulta: 14 gener 2024].
6. «Pàgina del seu lloc dedicada a aquest orgue.». Arxivat de l'original el 2008-12-17. [Consulta: 17 gener 2024].
7. Information de son CV Arxivat 2017-04-01 a Wayback Machine..
8. 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)]». Arxivat de l'original el 2017-04-21. [Consulta: 17 gener 2024].
9. «lloc dels panells». Arxivat de l'original el 2017-07-10. [Consulta: 17 gener 2024].
10. (anglès) Message important pour tous les utilisateurs de TeX Arxivat 2015-05-20 a Wayback Machine..
11. «DONALD (DON) ERVIN KNUTH» (en anglès). Association for Computing Machinery. [Consulta: 27 maig 2019].
12. «Donald Ervin Knuth» (en anglès). Universitat de St Andrews. [Consulta: 28 maig 2019].
13. «The President's National Medal of Science: Recipient Details» (en anglès). [Consulta: 27 maig 2019].
14. «ACM Software System Award» (en anglès). [Consulta: 27 maig 2019].
15. «Prizes and Awards» (en anglès). [Consulta: 27 maig 2019].
16. «DONALD ERVIN KNUTH» (en anglès). [Consulta: 27 maig 2019].^{[Enllaç no actiu]}
17. «IEEE John Von Neumann Medal Recipients» (en anglès). [Consulta: 27 maig 2019].
18. «Harvey Prize» (en anglès). [Consulta: 27 maig 2019].^{[Enllaç no actiu]}
19. «Katayanagi». CMU.
20. «Fronteras» (en castellà). FBBVA, 2010. Arxivat de l'original el 2016-08-19. [Consulta: 17 gener 2024].
21. «The Faraday Medallists» (en anglès). [Consulta: 27 maig 2019].
22. Myers, Andrew «de juny de /knuth-engineering-hero-060111.html Stanford's Don Knuth, a pioneering hero of computer programming». Stanford Report, 1er juny 2001 [Consulta: 27 juny 2011].
23. «Honorary Degree Citation - Donald Ervin Knuth» (en anglès). [Consulta: 28 maig 2019].
24. Docteurs’‘honoris causa de l'UMLV Arxivat 2010-04-21 a Wayback Machine..
25. «Donald E. Knuth» (en polonès). [Consulta: 28 maig 2019].
26. «Honorary Degree for Stanford Computer Scientist» (en anglès). Universitat de Glasgow. [Consulta: 27 maig 2019].
27. «de juny de 5/people-65.html Honors and Awards» (en anglès). [Consulta: 28 maig 2019].
28. «Honorary Degrees» (en anglès). [Consulta: 27 maig 2019].
29. «Honorary Doctorates» (en anglès). [Consulta: 28 maig 2019].
30. «Honorary Doctors» (en anglès). Arxivat de l'original el 2019-04-15. [Consulta: 27 maig 2019].
31. Journées en l'honneur de Donald E. Knuth Arxivat 2008-11-07 a Wayback Machine..
32. «Donald Ervin Knuth» (en anglès). Acadèmia Americana de les Arts i les Ciències. [Consulta: 27 maig 2019].
33. «Donald E. Knuth» (en anglès). Acadèmia Nacional de Ciències dels Estats Units. [Consulta: 27 maig 2019].
34. «Dr. Donald Knuth» (en anglès). Acadèmia Nacional d'Enginyeria dels Estats Units. [Consulta: 27 maig 2019].
35. «IEEE Honorary Membership» (en anglès). Institute of Electrical and Electronics Engineers. [Consulta: 27 maig 2019].
36. «Donald Knuth» (en francès). Acadèmia Francesa de les Ciències. [Consulta: 27 maig 2019].
37. «Donald Knuth» (en anglès). Computer History Museum. [Consulta: 27 maig 2019].
38. «Prof. Dr. Donald E. Knuth» (en anglès). Acadèmia Bavaresa de les Ciències. [Consulta: 27 maig 2019].
39. «Donald Knuth» (en anglès). Royal Society. [Consulta: 27 maig 2019].
40. «Кнут Дональд Эрвин» (en rus). Acadèmia de Ciències de Rússia. [Consulta: 27 maig 2019].
41. «Gruppe 1: Matematiske fag» (en noruec). Acadèmia Noruega de Ciències i Lletres. Arxivat de l'original el 2013-11-10. [Consulta: 27 maig 2019].

Vegeu també

• Sistema quater-imaginari