Donald Knuth - Donald Knuth

Donald Knuth
KnuthAtOpenContentAlliance.jpg
Knuth v roce 2005
narozený
Donald Ervin Knuth

( 1938-01-10 )10.01.1938 (věk 83)
Milwaukee, Wisconsin , USA
Národnost americký
Vzdělávání
Známý jako
Manžel / manželka Nancy Jill Carterová
Děti 2
Ocenění
Vědecká kariéra
Pole
Instituce Stanford University ,
University of Oslo
Teze Konečné semifieldy a projektivní roviny  (1963)
Doktorský poradce Marshall Hall, Jr.
Doktorandi
webová stránka cs .stanford .edu /~ knuth

Donald Ervin Knuth ( / k ə n Ü θ / kə- NOOTH , narozen 10.01.1938) je americký počítačový vědec , matematik a emeritní profesor na Stanford University . V roce 1974 obdržel Curingovu cenu ACM , neformálně považovanou za Nobelovu cenu informatiky. Knuth byl nazýván „otcem analýzy algoritmů “.

Je autorem vícesvazkového díla Umění počítačového programování . Podílel se na vývoji rigorózní analýzy výpočetní složitosti algoritmů a systematizoval pro ni formální matematické techniky. V tomto procesu také popularizoval asymptotickou notaci . Kromě zásadních příspěvků v několika odvětvích teoretické počítačové vědy je Knuth tvůrcem počítačového sazovacího systému TeX , souvisejícího jazyka pro definování písem a vykreslovacího systému METAFONT a rodiny moderních písem Computer Modern .

Jako spisovatel a učenec vytvořil Knuth počítačové programovací systémy WEB a CWEB určené k podpoře a usnadnění gramotného programování a navrhl architektury instrukčních sad MIX / MMIX . Knuth důrazně odmítá udělování softwarových patentů , přičemž vyjádřil svůj názor na americký patentový a známkový úřad a Evropskou patentovou organizaci .

Životopis

Raný život

Knuth se narodil v Milwaukee , Wisconsin , aby Ervin Henry Knuth a Louise Marie Bohning. Své dědictví popisuje jako „středozápadní luteránskou němčinu“. Jeho otec vlastnil malou tiskárnu a učil účetnictví. Donald, student luteránské střední školy Milwaukee , přemýšlel o důmyslných způsobech řešení problémů. Například v osmé třídě se přihlásil do soutěže o nalezení počtu slov, která by bylo možné uspořádat tak, aby vytvořila písmena v „Zieglerově obří liště“; soudci identifikovali 2500 takových slov. S časem získaným mimo školu kvůli předstíranému bolení břicha a řešení problému jiným způsobem, Knuth použil nezkrácený slovník a určil, zda by každý záznam ve slovníku mohl být vytvořen pomocí písmen ve frázi. Pomocí tohoto algoritmu identifikoval více než 4500 slov a vyhrál soutěž. Jako ceny škola získala novou televizi a dostatek bonbónů, které mohli jíst všichni jeho spolužáci.

Vzdělávání

Knuth získal stipendium z fyziky na Case Institute of Technology (nyní součást Case Western Reserve University ) v Clevelandu ve státě Ohio, zapsal se v roce 1956. Nastoupil také do kapitoly Beta Nu bratrstva Theta Chi . Při studiu fyziky na Case, Knuth byl představen na IBM 650 , časný komerční počítač . Po přečtení manuálu k počítači se Knuth rozhodl přepsat kód sestavy a kompilátoru pro stroj používaný ve škole, protože věřil, že to zvládne lépe.

V roce 1958 vytvořil Knuth program, který má pomáhat basketbalovému týmu jeho školy vyhrávat hry. Přiřadil „hodnoty“ hráčům, aby změřil jejich pravděpodobnost získání bodů, což je nový přístup, o kterém později informovaly Newsweek a CBS Evening News .

Knuth byl jedním ze zakládajících redaktorů časopisu Case Institute's Engineering and Science Review , který v roce 1959 získal národní ocenění jako nejlepší technický časopis. Poté přešel z fyziky na matematiku a v roce 1960 získal dva tituly od Case: titul bakaláře přírodních věd, a současně magistr vědy zvláštním oceněním fakulty, který jeho práci považoval za mimořádně vynikající.

V roce 1963 získal jako poradce matematik Marshall Hall doktorát z matematiky na California Institute of Technology .

Brzká práce

Po obdržení doktorátu se Knuth připojil k Caltechově fakultě jako odborný asistent.

Přijal pověření k napsání knihy o kompilátorech počítačového programovacího jazyka . Při práci na tomto projektu se Knuth rozhodl, že nemůže dostatečně zpracovat toto téma, aniž by nejprve vyvinul základní teorii počítačového programování, z níž se stalo Umění počítačového programování . Původně plánoval vydat toto jako jedinou knihu. Když Knuth rozvinul svůj obrys knihy, dospěl k závěru, že k důkladnému pokrytí tématu potřebuje šest svazků a poté sedm. První svazek vydal v roce 1968.

Těsně před vydáním prvního dílu Umění počítačového programování odešel Knuth z Caltechu, aby přijal zaměstnání v divizi výzkumu komunikace Ústavu obranných analýz , poté se nachází v kampusu Princetonské univerzity , který prováděl matematický výzkum v kryptografii na podporu národní bezpečnosti. Agentura .

V roce 1967 se Knuth zúčastnil konference Společnosti pro průmyslovou a aplikovanou matematiku a někdo se zeptal, co udělal. V té době byla počítačová věda rozdělena na numerickou analýzu, umělou inteligenci a programovací jazyky. Na základě své studie a knihy Umění počítačového programování se Knuth rozhodl příště, když se někdo zeptal, že řekne: „Analýza algoritmů“.

Knuth poté opustil svou pozici, aby se připojil k fakultě Stanfordské univerzity v roce 1969, kde je nyní emeritním profesorem informatiky Fletchera Jonese.

Spisy

Knuth je spisovatel a také počítačový vědec.

Umění počítačového programování ( TAOCP )

Hlavní článek: Umění počítačového programování

„Nejlepší způsob, jak komunikovat z jedné lidské bytosti na druhou, je prostřednictvím příběhu.“

-  Donald Knuth

V sedmdesátých letech popsal Knuth informatiku jako „zcela nový obor bez skutečné identity. A úroveň dostupných publikací nebyla tak vysoká. Mnoho novin, které vyšly, bylo prostě špatně ... Takže jedna z mých motivací měl uvést na pravou míru příběh, který byl velmi špatně vyprávěn. “

V letech 1972 až 1973 strávil Knuth rok na univerzitě v Oslu mezi lidmi, jako byl Ole-Johan Dahl . Zde měl ve skutečnosti napsat sedmý svazek své knižní série, svazek, který se měl zabývat programovacími jazyky. Když však přišel do Osla, Knuth dokončil pouze první dva svazky, a tak strávil rok ve třetím svazku vedle učení. Třetí díl série vyšel těsně poté, co se Knuth vrátil v roce 1973 na Stanford.

Do roku 2011 byly publikovány první tři svazky a první část objemu čtyř jeho série. Byla vydána také Concrete Mathematics: A Foundation for Computer Science 2. vyd., Která vznikla rozšířením sekce matematické přípravné přípravy svazku 1 TAoCP . V dubnu 2020 Knuth řekl, že tvrdě pracuje na části B svazku 4 a očekává, že kniha bude mít alespoň části A až F.

Další práce

Knuth je také autorem Surreal Numbers , matematický novelette na John Conway ‚s teorie množin výstavbu alternativního systému čísel. Místo jednoduchého vysvětlení předmětu se kniha snaží ukázat vývoj matematiky. Knuth chtěl, aby kniha připravila studenty na originální, kreativní výzkum.

V roce 1995 napsal Knuth předmluvu ke knize A = B od Marka Petkovška , Herberta Wilfa a Dorona Zeilbergera . Knuth je také příležitostným přispěvatelem jazykových hádanek do Word Ways: The Journal of Recreational Linguistics .

Knuth se také ponořil do rekreační matematiky . On přispíval články do Journal of rekreační matematika začíná v roce 1960, a byla uznána jako hlavní přispěvatel v Joseph Madachy ‚s matematiky na dovolenou .

Knuth se také objevil v řadě videí Numberphile a Computerphile na YouTube, kde diskutoval o tématech od psaní surrealistických čísel až po to, proč nepoužívá e -mail .

Práce týkající se jeho náboženské víry

Kromě svých spisů o informatice je Knuth, luterán , také autorem iluminovaných biblických textů 3:16 , v nichž zkoumá Bibli procesem systematického vzorkování , konkrétně analýzou kapitoly 3, verše 16 každého z nich. rezervovat. Každý verš je doprovázen ztvárněním kaligrafického umění, ke kterému přispěla skupina kaligrafů pod vedením Hermanna Zapfa . Následně byl pozván na přednášku na MIT o svých názorech na náboženství a informatiku za projektem 3:16, což vyústilo v další knihu Věci, o které počítačový vědec zřídka mluví , kde publikoval přednášky „Bůh a počítač Věda “ .

Názor na softwarové patenty

Knuth je zásadně proti politice udělování softwarové patenty na triviální řešení, které by mělo být zřejmé, ale vyjádřil složitější, výhled pro netriviální řešení, jako je například metoda interior-point z lineárního programování . Svůj nesouhlas vyjádřil přímo Úřadu pro patenty a ochranné známky Spojených států a Evropské patentové organizaci .

Počítačové úvahy

Knuth pořádá několikrát ročně neformální přednášky na Stanfordské univerzitě , které nazval „Computer Musings“. Byl hostujícím profesorem na Oxfordské univerzitě katedry informatiky ve Spojeném království do roku 2017 a čestným členem Magdalen College .

Programování

Digitální sazba

V roce 1970 vydavatelé TAOCP opuštěné Monotype ve prospěch phototypesetting . Knuth byl natolik frustrován neschopností druhého systému přiblížit se kvalitě předchozích svazků, které byly vysázeny pomocí staršího systému, že si vzal čas na práci na digitálním sazení a vytvořil TeX a Metafont .

Gramotné programování

Při vývoji TeX vytvořil Knuth novou metodiku programování, kterou nazval gramotné programování , protože věřil, že programátoři by měli programy považovat za literární díla. „Místo toho, abychom si představovali, že naším hlavním úkolem je instruovat počítač, co má dělat, soustřeďme se spíše na vysvětlování lidem, co chceme, aby počítač dělal.“

Knuth ztělesnil myšlenku gramotného programování ve webovém systému. Stejný zdroj WEB se používá pro tkaní souboru TeX, a zamotat se Pascal zdrojový soubor. Ty zase vytvářejí čitelný popis programu, respektive spustitelný binární soubor. Pozdější iterace systému, CWEB , nahradí Pascal s C .

Knuth použil WEB k programování TeX a METAFONT a oba programy vydal jako knihy: TeXbook , který původně vyšel v roce 1984, a The METAFONTbook , který původně vyšel v roce 1986. Přibližně ve stejnou dobu LaTeX , nyní široce přijaté makro balíček založený na TeXu, byl nejprve vyvinut Leslie Lamport , který později publikoval svůj první uživatelský manuál v roce 1986.

Hudba

Knuth je varhaník a skladatel . V roce 2016 dokončil hudební skladbu pro varhany s názvem Fantasia Apocalyptica , kterou popisuje jako „překlad řeckého textu Zjevení svatého Jana Božského do hudby“. Ve Švédsku měl premiéru 10. ledna 2018.

Osobní život

Donald Knuth si vzal Nancy Jill Carter dne 24. června 1961, zatímco on byl postgraduální student na California Institute of Technology. Mají dvě děti: John Martin Knuth a Jennifer Sierra Knuth.

čínské jméno

Knuthovo čínské jméno je Gao Dena ( zjednodušená čínština :高 德纳; tradiční čínština :高 德納; pinyin : Gao Dénà ). V roce 1977 mu dal toto jméno Frances Yao , krátce před 3týdenním výletem do Číny . V čínském překladu svazku 1 Umění počítačového programování ( zjednodušená čínština :计算机 程序 设计 艺术; tradiční čínština :電腦 程式 設計 藝術; pinyin : Jìsuànjī chéngxù shèjì yìshù ) Knuth vysvětluje, že přijal své čínské jméno, protože chtěl být známý rostoucím počtem počítačových programátorů v té době v Číně. V roce 1989, jeho čínský název byl umístěn na vrcholu Journal of Computer Science and Technology ‚s hlavičkou, který Knuth říká:‚Cítím se v blízkosti všech Číňanů, i když nemohu mluvit jazyk‘.

Obavy o zdraví

V roce 2006 byla Knuthovi diagnostikována rakovina prostaty . V prosinci toho roku podstoupil operaci a prohlásil: „Trochu radiační terapie ... preventivně, ale prognóza vypadá docela dobře“, jak uvedl ve své videobiografii.

Humor

Jedna z Knuthových odměn

Knuth dříve platil nálezci poplatek 2,56 USD za jakékoli typografické chyby nebo chyby objevené v jeho knihách, protože „256 haléřů je jeden hexadecimální dolar“ a 0,32 $ za „cenné návrhy“. Podle článku v Massachusetts Institute of Technology je Technology Review , tyto kontroly Knuth odměna jsou ‚mezi nejvíce ceněných trofejí computerdom je‘. Knuth musel v roce 2008 kvůli bankovním podvodům přestat posílat skutečné šeky a místo toho nyní každému nálezci chyb dává „vkladový certifikát“ z veřejně kótovaného zůstatku ve své fiktivní „Bank of San Serriffe “.

Jednou varoval zpravodaje: „Dejte si pozor na chyby ve výše uvedeném kódu; Pouze jsem dokázal, že je správný, nezkoušel jsem ho.“

Knuth publikoval svůj první „vědecký“ článek ve školním časopise v roce 1957 pod názvem „The Potrzebie System of Weights and Measures“. V tom, on definoval fundamentální jednotku z délky jako tloušťka Mad No. 26, a pojmenovaný fundamentální jednotka síly „whatmeworry“. Mad publikoval článek v čísle 33 (červen 1957).

Aby demonstroval koncept rekurze , Knuth v rejstříku The Art of Computer Programming , Volume 1 , záměrně odkazoval na „Circular Definition“ a „Definition, Round“ .

Předmluva o betonové matematice má následující odstavec:

Když DEK učil na Stanfordu poprvé betonovou matematiku, vysvětlil poněkud podivný název tím, že to byl jeho pokus naučit matematický kurz tvrdý místo měkký. Oznámil, že v rozporu s očekáváním jeho kolegové, že se to bude učit teorii agregátů ani kamenem Vkládání větu , a dokonce ani kámen Čech kompaktifikace . (Několik studentů z oboru stavebnictví vstalo a tiše odešlo z místnosti.)

Na konferenci TUG 2010 Knuth oznámil satirického nástupce TeXu založeného na XML s názvem „iTeX“ ( vyslovováno  [iː˨˩˦tɛks˧˥] , prováděno se zvoněním), který by podporoval funkce, jako jsou libovolně škálované iracionální jednotky , 3D tisk , vstup ze seismografů a monitorů srdce, animace a stereofonní zvuk.

Ceny a vyznamenání

V roce 1971 byl Knuth držitelem první ceny ACM Grace Murray Hopper Award . Získal různá další ocenění včetně Turingovy ceny , Národní medaile za vědu , medaile Johna von Neumanna a Kjótské ceny .

Knuth byl zvolen Distinguished Fellow of British Computer Society (DFBCS) v roce 1980 jako uznání příspěvků Knutha do oblasti počítačové vědy.

V roce 1990 mu byl udělen jedinečný akademický titul profesora umění počítačového programování , který byl od té doby přepracován na emeritního profesora umění počítačového programování .

Knuth byl zvolen do Národní akademie věd v roce 1975. V roce 1981 byl také zvolen členem Národní akademie inženýrství za organizaci rozsáhlých oblastí počítačových věd tak, aby byly přístupné všem segmentům počítačové komunity. V roce 1992 se stal spolupracovníkem Francouzské akademie věd . Také ten rok odešel z pravidelného výzkumu a výuky na Stanfordské univerzitě , aby dokončil Umění počítačového programování . V roce 2003 byl zvolen zahraničním členem Královské společnosti (ForMemRS) .

Knuth byl zvolen jako Fellow (první třída Fellows) ze Společnosti pro průmyslovou a aplikovanou matematiku v roce 2009 za jeho vynikající příspěvky k matematice. Je členem Norské akademie věd a dopisů . V roce 2012 se stal členem Americké matematické společnosti a členem Americké filozofické společnosti . Mezi další ocenění a vyznamenání patří:

Publikace

Krátký seznam jeho publikací obsahuje:

Umění počítačového programování :

  1. ——— (1997). Umění počítačového programování . 1: Základní algoritmy (3. vydání). Addison-Wesley Professional. ISBN 978-0-201-89683-1.
  2. ——— (1997). Umění počítačového programování . 2: Seminumerické algoritmy (3. vyd.). Addison-Wesley Professional. ISBN 978-0-201-89684-8.
  3. ——— (1998). Umění počítačového programování . 3: Třídění a vyhledávání (2. vyd.). Addison-Wesley Professional. ISBN 978-0-201-89685-5.
  4. ——— (2011). Umění počítačového programování . 4A: Kombinatorické algoritmy. Addison-Wesley Professional. ISBN 978-0-201-03804-0.
  5. ——— (2005). MMIX - počítač RISC pro nové tisíciletí . 1, Fascicle 1. ISBN 978-0-201-85392-6.
  6. ——— (2008). Umění počítačového programování . 4, Fascicle 0: Úvod do kombinatorických algoritmů a booleovských funkcí. ISBN 978-0-321-53496-5.
  7. ——— (2009). Umění počítačového programování . 4, Fascicle 1: Bitwise Tricks & Techniques, Binary decision diagrams. ISBN 978-0-321-58050-4.
  8. ——— (2005). Umění počítačového programování . 4, Fascicle 2: Generování všech n -tic a permutací. ISBN 978-0-201-85393-3.
  9. ——— (2005). Umění počítačového programování . 4, Fascicle 3: Generování všech kombinací a oddílů. ISBN 978-0-201-85394-0.
  10. ——— (2006). Umění počítačového programování . 4, Fascicle 4: Generování všech stromů - historie kombinatorické generace. ISBN 978-0-321-33570-8.
  11. ——— (2018). Umění počítačového programování . 4, Fascicle 5: Mathematical Preliminaries Redux, Backtracking, Dancing Links. ISBN 978-0-134-67179-6.
  12. ——— (2015). Umění počítačového programování . 4, Fascicle 6: Uspokojitelnost. ISBN 978-0-134-39760-3.

Počítače a sazba (všechny knihy jsou vázané, pokud není uvedeno jinak):

  1. ——— (1984). Počítače a sazba . A, TeXbook. Reading, MA : Addison-Wesley. ISBN 978-0-201-13447-6., x+483pp.
  2. ——— (1984). Počítače a sazba . A, TeXbook. Reading, MA : Addison-Wesley. ISBN 978-0-201-13448-3. (měkká vazba).
  3. ——— (1986). Počítače a sazba . B, TeX: Program. Reading, MA : Addison-Wesley. ISBN 978-0-201-13437-7., xviii+600 stran.
  4. ——— (1986). Počítače a sazba . C, METAFONTbook. Reading, MA : Addison-Wesley. ISBN 978-0-201-13445-2., xii+361pp.
  5. ——— (1986). Počítače a sazba . C, METAFONTbook. Reading, MA : Addison-Wesley. ISBN 978-0-201-13444-5. (měkká vazba).
  6. ——— (1986). Počítače a sazba . D, METAFONT: Program. Reading, MA : Addison-Wesley. ISBN 978-0-201-13438-4., xviii+566pp.
  7. ——— (1986). Počítače a sazba . E, Počítačová moderní písma. Reading, MA : Addison-Wesley. ISBN 978-0-201-13446-9., xvi+588pp.
  8. ——— (2000). Počítače a sazba . Krabicová sada AE. Reading, MA : Addison-Wesley. ISBN 978-0-201-73416-4.

Knihy sebraných papírů:

  1. ——— (1992). Gramotné programování . Poznámky k výuce. Stanford, CA : Centrum pro studium jazyka a informací —CSLI. ISBN 978-0-937073-80-3.
  2. ——— (1996). Vybrané příspěvky z informatiky . Poznámky k výuce. Stanford, CA : Centrum pro studium jazyka a informací — CSLI. ISBN 978-1-881526-91-9.
  3. ——— (1999). Digitální typografie . Poznámky k výuce. Stanford, CA : Centrum pro studium jazyka a informací — CSLI. ISBN 978-1-57586-010-7.
  4. ——— (2000). Vybrané příspěvky o analýze algoritmů . Poznámky k výuce. Stanford, CA : Centrum pro studium jazyka a informací — CSLI. ISBN 978-1-57586-212-5.
  5. ——— (2003). Vybrané příspěvky v počítačových jazycích . Poznámky k výuce. Stanford, CA : Centrum pro studium jazyka a informací — CSLI. ISBN 978-1-57586-381-8., ISBN  1-57586-382-0 (brožováno)
  6. ——— (2003). Vybrané příspěvky z diskrétní matematiky . Poznámky k výuce. Stanford, CA : Centrum pro studium jazyka a informací — CSLI. ISBN 978-1-57586-249-1., ISBN  1-57586-248-4 (brožováno)
  7. Donald E. Knuth, Selected Papers on Design of Algorithms (Stanford, California: Center for the Study of Language and Information — CSLI Lecture Notes, no. 191), 2010. ISBN  1-57586-583-1 (tkanina), ISBN  1 -57586-582-3 (brožováno)
  8. Donald E. Knuth, Selected Papers on Fun and Games (Stanford, California: Center for the Study of Language and Information — CSLI Lecture Notes, no. 192), 2011. ISBN  978-1-57586-585-0 (latka), ISBN  978-1-57586-584-3 (brožováno)
  9. Donald E. Knuth, Companion to the Papers of Donald Knuth (Stanford, California: Center for the Study of Language and Information — CSLI Lecture Notes, no. 202), 2011. ISBN  978-1-57586-635-2 (tkanina) , ISBN  978-1-57586-634-5 (brožováno)

Další knihy:

  1. Graham, Ronald L ; Knuth, Donald E .; Patashnik, Oren (1994). Betonová matematika: Základ pro počítačovou vědu (druhé vydání.). Reading, MA: Addison-Wesley. ISBN 978-0-201-55802-9. MR  1397498 . xiv+657 stran
  2. Knuth, Donald Ervin (1974). Neskutečná čísla: jak se dva bývalí studenti obrátili k čisté matematice a našli úplné štěstí: matematická novela . Addison-Wesley. ISBN 978-0-201-03812-5.
  3. Donald E. Knuth, The Stanford GraphBase: Platform for Combinatorial Computing (New York, ACM Press) 1993. druhý brožovaný tisk 2009. ISBN  0-321-60632-9
  4. Donald E. Knuth, 3:16 Biblické texty osvětlené (Madison, Wisconsin: AR Editions), 1990. ISBN  0-89579-252-4
  5. Donald E. Knuth, Věci, o kterých počítačový vědec zřídka mluví (Centrum pro studium jazyka a informací-Přednášky CSLI č. 136), 2001. ISBN  1-57586-326-X
  6. Donald E. Knuth, MMIXware: RISC Computer for the Third Millenium (Heidelberg: Springer-Verlag— Lecture Notes in Computer Science, no. 1750), 1999. viii+550pp. ISBN  978-3-540-66938-8
  7. Donald E. Knuth a Silvio Levy, The CWEB System of Structured Documentation (Reading, Massachusetts: Addison-Wesley), 1993. iv+227pp. ISBN  0-201-57569-8 . Třetí tisk 2001 s podporou hypertextu, ii + 237 stran.
  8. Donald E. Knuth, Tracy L. Larrabee a Paul M. Roberts, Mathematical Writing (Washington, DC: Mathematical Association of America), 1989. ii+115pp
  9. Daniel H. Greene a Donald E. Knuth, Mathematics for the Analysis of Algorithms (Boston: Birkhäuser), 1990. viii+132pp.
  10. Donald E. Knuth, Mariages Stables: et leurs relations avec d'autres problemsèmes combinationatoires (Montréal: Les Presses de l'Université de Montréal) , 1976. 106pp.
  11. Donald E. Knuth, Axioms and Hulls (Heidelberg: Springer-Verlag — Lecture Notes in Computer Science, no. 606), 1992. ix+109pp. ISBN  3-540-55611-7

Viz také

Reference

Bibliografie

externí odkazy