Donald Ervin Knuth

Život

Mládí

Donald Ervin Knuth se narodil roku 1938 v Milwaukee v americkém státě Wisconsin. Prvním vzorem mu byl jeho otec, který vyučoval účetnictví na místní luteránské střední škole a malému Donaldovi předal zápal pro vzdělání a také pro hudbu.

Svoji výjimečnost Knuth poprvé projevil v osmé třídě, když vyhrál soutěž pořádanou společností na sladkosti Ziegler: úkolem bylo vytvořit co nejvíce slov z písmen textu „Ziegler's Giant Bar” a zatímco referenční řešení obsahovalo 2500 slov, Donald vymyslel slov 4500, a to bez použití apostrofu. Za jasnou výhru získal televizní přijímač a také zásobu cukrovinek po zbytek školní docházky.

I přesto ale svou další budoucnost neviděl v matematice či fyzice, ale v hudbě, které na střední škole věnoval téměř veškerý volný čas. Jeho názor změnila až nabídka stipendia pro studium fyziky od Case Institute of Technology v Ohiu. +more Zde Knuth objevil svůj zápal pro matematiku, která mu na střední škole připadala nudná, a na doporučení svého učitele matematické analýzy změnil obor z fyziky na matematiku.

V roce 1956 se Donald poprvé setkal s počítačem - sálovým IBM 650, což byl první sériově vyráběný počítač na světě. Počítači ihned propadl - celou noc se z manuálu učil základy programování a hned také vymýšlel, jak uvedené příklady zlepšit. +more První jeho program faktorizoval čísla, další hrál pro změnu piškvorky a další zas analyzoval výkonnost jednotlivých hráčů školního basketbalového družstva.

Díky výjimečným výsledkům mu Case Institute v roce 1960 jako vůbec prvnímu studentovi v historii udělil po dokončení bakalářského studia i magisterský titul v oboru matematika. Poté odešel studovat na California Institute of Technology, kde o tři roky později získal titul doktorský za disertaci Finite semifields and projective planes. +more Mezi další jeho práce z tohoto období pak patří spočtení eulerova čísla na 1271 desetinných míst a článek o vyhodnocování polynomů počítačem. Ještě během studií, v roce 1961, se Donald Knuth oženil s Nancy Jill Carterovou, s kterou má dvě děti Johna Martina (*1965) a Jennifer Sierru (*1966).

Umění programování

Donald Knuth a Steve Wozniak v roce 2011 Na Caltech zůstal i po dokončení postgraduálního studia jako odborný asistent. +more Již od roku 1960 Knuth rovněž pracoval jako konzultant pro Burroughs Corporation. Zabýval se zde softwarem i hardwarem a potkal zde mnoho inspirativních lidí, zejména pak Edsgera Dijkstru, který právě v oné době dokončoval spolu s J. A. Zonneveldem první implementaci překladače pro Algol 60.

Na svém celoživotním díle, monografii Umění programování (anglicky The Art of Computer Programming), začal pracovat v roce 1962, tedy ještě coby doktorand. Původně se mělo jednat o publikaci o překladačích pro nakladatelství Addison-Wesley. +more Když ale text do roku 1966 narostl do délky tří tisíc stran rukopisu, bylo zřejmé, že vzniká něco mnohem většího. Nakonec se s nakladatelstvím dohodl na sepsání sedmi svazků, jež by pokrývaly nejdůležitější znalosti z informatiky a algoritmizace, spolu s jejich detailní matematickou analýzou.

První díl o základních algoritmech vyšel v roce 1968, druhý o generování náhodných čísel a aritmetických algoritmech o rok později a třetí o řazení a vyhledávání v roce 1973. První svazek čtvrtého dílu o kombinatorických metodách vyšel až roku 2011. +more Čtvrtý díl je rozdělen do čtyř svazků; jednotlivé části postupně vycházely ve formě tzv. „fasciklů”, tedy pracovních verzí, ke kterým se může vyjádřit odborná veřejnost. Pátý díl bude věnován algoritmům syntaktické analýzy a Knuth jeho dokončení plánuje na rok 2020. Po jeho dokončení se vrátí k prvním třem dílům, které zaktualizuje - doplní do nich témata, která v době psaní prvních svazků ještě nebyla prozkoumána. Šestý díl by měl pojednávat o teorii bezkontextových jazyků a finální sedmý by se měl věnovat překladačům.

I přes nedokončenost je ale Umění programování, kterému se často přezdívá „programátorská bible”, vysoce ceněno. Například americký vědecký časopis American Scientist jej zařadil mezi sto nejvýznamnějších vědeckých publikací 20. +more století. Vznikly také překlady do řady cizích jazyků, přičemž v češtině vydalo nakladatelství Computer Press zatím první dva díly.

Zajímavostí pak je, že ukázky kódu v knize jsou uvedeny v jazyce symbolických adres hypotetického počítače MIX (respektive jeho RISC verze MMIX v pozdějších vydáních). K architektuře MIX vzniklo několik emulátorů (například GNU MDK).

TeX

Dlouhá pauza po vydání třetího svazku Umění programování byla způsobena především Knuthovou nespokojeností s tehdejší sazbou matematické literatury. Systém pro počítačovou sazbu, který nazval TeX, vyvíjí od roku 1977. +more Kromě TeXu vytvořil také systém pro vytváření písem za použití matematiky Metafont. O těchto systémech také napsal čtyřsvazkovou sérii knih Computers and Typesetting, která spolu s faktem, že oba systémy nabídl zdarma k používání, pomohla širokému rozšíření systémů, především pak TeXu.

$ Že má Knuth smysl pro humor, můžeme vypozorovat například z číslování verzí obou systémů - místo tradičního zvyšování čísla verze, se označení verze TeXu prodlužuje vždy o další číslici rozvoje Ludolfova čísla a verze Metafontu se pro změnu blíží k číslu Eulerovu. +more Knuthovým přáním je, aby se po jeho smrti systémy již dále nevyvíjely, ale zůstaly ve finálních verzích s označením π, respektive e. Dalším žertíkem je pak vyplácení 2,56 $ za nalezení typografické chyby v jeho libovolné publikaci. Tato částka nebyla vybrána náhodně - 256 centů Knuth označuje za jeden „hexadecimální dolar”.

Odchod na Stanford a další projekty

Ještě před odchodem z California Institute of Technology na Stanford přispěl Donald Knuth v polovině šedesátých let k rozvoji překladačů objevem LR analýzy. Jedná se speciální deterministickou verzi syntaktické analýzy zdola nahoru. +more Také se podílel na algoritmu pro vyvozování důsledků z axiomů a ověřování důkazů v axiomatických systémech, který vytvořil v roce 1966 se svým studentem Peterem Bendixem, a který dnes nese jména obou autorů - Knuthův-Bendixův algoritmus.

Knuth odešel na Stanford ještě před začátkem prací na TeXu, v roce 1968, a s touto kalifornskou univerzitou spojil zbytek své kariéry. Se studentem Vaughanem Prattem zde v polovině sedmdesátých let vytvořil jednoduchý, avšak efektivní algoritmus pro hledání výskytu podřetězce v řetězci. +more Nezávisle na nich totožný postup objevil i James H. Morris, a tak algoritmus dnes známe pod názvem Knuthův-Morrisův-Prattův algoritmus (KMP). Na Stanfordu coby profesor teoretické informatiky vyučoval především kurzy o matematice a datových strukturách. Své přednášky o matematice jakožto základu informatiky, shrnul v knize Concrete Mathematics: A Foundation for Computer Science, kterou napsal spolu s Ronaldem Grahamem a Orenem Patashnikem. Legendární byl i jeho řešitelský seminář A Programming and Problem-Solving-Seminar. Od roku 1993 však pořádá přednášky již jen velmi zřídka, a svůj čas věnuje práci na Umění programování.

Knuth také vymyslel nový přístup k programování, který nazval literární programování (anglicky literate programming), ve kterém je na prvním místě dobrá čitelnost a srozumitelnost pro čtenáře kódu. Toho je dosaženo množstvím komentářů v přirozeném jazyce, jež převažují nad výkonným kódem. +more Pro toto paradigma také naprogramoval systémy WEB a CWEB, ale princip literárního programování můžeme nalézt například i v programovacím jazyku Haskell.

Knuth zasáhl i do jiných oblastí než je programování: Například během týdenní dovolené v Oslu napsal „matematickou novelu” Surreal Numbers: How two ex-students turned on to pure mathematics and found total happiness, která pojednává o dvou bývalých studentech, kteří studují Conwayův číselný systém - tedy systém, který Knuth v té době rovněž zkoumal. Kniha nepojednává tolik o samotném číselném systému, jako spíše o způsobu jak k takovému problému při bádání přistupovat. +more Jde o první beletrii, ve které byly uveřejněny výsledky výzkumu dříve, než se objevily v odborném článku.

Ve volném čase se Knuth věnuje hudbě - především hraje na varhany, které si sám navrhl.

Stejně jako jeho rodiče je Donald Knuth luteránem. Systematický přístup vědce spojil s vírou v díle 3:16 Bible Texts Illuminated, ve kterém analyzuje šestnáctý verš třetí kapitoly každé biblické knihy. +more O víře píše i v knize Things a computer Scientist rarely talks about.

V roce 2006 porazil rakovinu prostaty.

Ocenění

Knuth za svou práci získal řadu ocenění. V roce 1971 získal od ACM Cenu Grace Murray Hopperové, dále mu byla udělena například prestižní Turingova cena (1974) a z rukou prezidenta Cartera převzal Národní vyznamenání za vědu (1979). +more Také získal například Kyotskou cenu (1996) nebo Medaili Johna von Neumanna (1995). Donald Knuth je členem britské Královské společnosti, francouzské akademie věd nebo Americké matematické společnosti.

V roce 1996 se stal čestným doktorem brněnské Masarykovy univerzity.

Odkazy

Reference

Literatura

Sedgewick, R. : Algorithms in C. +more Reading, Mass: Addison-Wesley, 1990, . * Shasha, D. ; Lazere, C. : Out of Their Minds : The Lives and Discoveries of 15 Great Computer Scientists. New York, NY: Copernicus, 1998, . * Slater, R. : Portraits in Silicon. Cambridge, Mass: MIT Press, 1987,.

Související články

Umění programování * Knuthův zápis * TeX * MIX (fiktivní počítač) * MMIX

Externí odkazy

[url=http://www-cs-faculty.stanford.edu/~knuth/]Domácí stránka Donalda Knutha na Stanfordově univerzitě[/url]

Kategorie:Spisovatelé literatury o programování Kategorie:Američtí programátoři Kategorie:Američtí informatici Kategorie:Američtí matematici Kategorie:Matematici 20. +more století Kategorie:Kombinatorici Kategorie:Průkopníci počítačů Kategorie:TeX Kategorie:Nositelé Turingovy ceny Kategorie:Američtí křesťané Kategorie:Luteráni Kategorie:Absolventi Kalifornského technologického institutu Kategorie:Nositelé Národního vyznamenání za vědu Kategorie:Držitelé čestných doktorátů Masarykovy univerzity Kategorie:Narození v roce 1938 Kategorie:Žijící lidé Kategorie:Muži Kategorie:Narození 10. ledna Kategorie:Narození v Milwaukee Kategorie:Držitelé čestných doktorátů Univerzity Tübingen.