Donald Knuth - velikán algoritmického myšlení

Autor několikasvazkového díla Umění programování, na němž pracuje od roku 1962, bývá označován jako „guru počítačového programování“ a řazen mezi nevlivnější vědce současnosti.

Donald Knuth - velikán algoritmického myšlení


„Velmi si přeji, aby práce počítačových vědců byla posuzována i z hlediska krásy a opravdového zaujetí, nikoli pouze úzkým prizmatem ekonomických zájmů,“ svěřil se profesor Donald Knuth v nedávném rozhovoru. On sám po celý život tímto způsobem k informatice přistupoval. Při průzkumu co nejefektivnějších způsobů tvorby a analýzy algoritmů objevoval zároveň krásu, již v sobě matematika i programování skrývají. A tento pohled potvrdil i jako jeden z průkopníků zdarma využitelných programů, když své softwarové produkty, ať už jde o programy TeX, Metafont či systém WEB, poskytl všem uživatelům zdarma k dispozici.

Zásadní přínos Donalda Knutha pro počítačovou vědu však nespočívá v těchto programech, jakkoli jsou navýsost užitečné, ani v prosazování otevřených formátů, nýbrž v jeho vědecké práci soustřeďující se zvláště na problematiku tvorby a analýzy algoritmů. S tímto přínosem souvisí i jeho dosud nedokončená mnohosvazková monografie Umění programování, v níž syntetizoval základní poznatky oboru v ucelené a přehledné formě a která se stala jednou ze základních děl informatiky.

Jak jsme mohli sledovat v předcházejících částech tohoto seriálu, vývoj informatiky se v polovině minulého století, kdy se tento obor úspěšně emancipoval od matematických, fyzikálních i ryze technických disciplín, polarizoval do dvou základních skupin, na technickou a teoretickou informatiku. Zatímco technická větev se soustředila na vývoj procesorových a paměťových struktur, návrhy čipů, počítačové architektury, transakčních systémů a komunikačních sítí, teoretická část s úspěchem rozvíjela teorii automatů, datových struktur a algoritmů, formálních jazyků, programování, kódování a šifrování, kompresi dat či teorii vypočitatelnosti a komplexnosti. Co v této teoretické, „problémově orientované informatice“ po dlouhou dobu chybělo, byl ucelený vhled do samotné esenciální podstaty oboru, z níž všechny tyto specializované oblasti vycházely a která umožňovala jejich rozvoj. Když si Donald Knuth tento nedostatek uvědomil, rozhodl se, že se pokusí takovou knihu, lépe řečeno sérii knih, vytvořit. Tak začalo vznikat dílo, jež během let pomáhá posouvat obor informatiky (se zvláštním důrazem na problematiku vytváření programů) na novou úroveň, a to zvláště tím, že přináší ucelený a komplexní přehled poznatků, z nichž toto odvětví pramení a které jej nadále utvářejí.

„Tuto sérii knih s láskou a vzpomínkami věnuji počítači typu 650, jenž byl kdysi instalován na Case Institute of Technology a se kterým jsem prožil mnoho nezapomenutelných večerů.“ Tak zní úvodní slova věnování k tomuto monumentálnímu dílu, v němž se Donaldu Knuthovi podařilo hlubokou erudici vzácným způsobem propojit s estetickým vnímáním. Není proto od věci připomenout si nejen okolnosti vzniku tohoto cenného souboru knih, ale i pozoruhodnou osobnost jejich autora.

Od hudby k programování

Donald Knuth se narodil na začátku roku 1938 v Milwaukee ve státu Wisconsin. Jeho otec pracoval jako účetní, ale současně také provozoval malou tiskárnu (což vysvětluje pozdější hluboký zájem jeho syna o typografii a sazbu). Byl také varhaníkem v luteránském kostele a později učitelem. To vše mělo na Donalda velký vliv. Otec jej zasvěcoval nejen do problematiky tisku knih, ale také učil hrát na klavír, a protože se ukázalo, že chlapec má hudební sluch, přihlásil jej do hudební školy. Tam se Donovo nadání potvrdilo, záhy si ke klavíru přibral i trubku a později saxofon. Zkoušel i komponovat, a to docela zdárně, takže se zdálo, že o jeho budoucnosti je rozhodnuto – bude se věnovat hudbě.

Od raných školních let však Donald vynikal také v matematice a přírodních vědách. Životopisci v této souvislosti neopomenou zmínit jeho vítězství v celonárodní soutěži žáků základních škol, kterou pořádala potravinářská společnost Ziegler. Děti měly sestavit co nejvíc slov z písmen, jež jsou obsaženy v názvu tyčinky „Ziegler's Giant Bar“. Třináctiletý Donald Knuth pomocí exaktní metody, kterou si pro tento účel vytvořil, sestavil těchto slov na čtyři a půl tisíce, což mu vyneslo jasné prvenství. Škola díky tomu získala od pořadatele soutěže nejen nový televizor, ale i mohutnou zásobu čokoládových tyčinek.

I když stále většinu času věnoval hudbě, jeho matematický talent byl nepřehlédnutelný, což se projevilo ještě více na střední škole. O tom ostatně vypráví jiná historka. Jednoho dne, když se chystal na koncert se školní kapelou, mu ujel autobus. Čekání na další spoj si krátil tím, že se pokusil vyřešit úlohu, kterou třídě zadal profesor matematiky a fyziky. Správné řešení i originalita postupu, díky němuž dospěl k výsledku, mu od profesora matematiky zajistily nejlepší známku. Vliv tohoto profesora také rozhodl, že nadaný student začal studovat fyziku na clevelandském Case Institute of Technology.

Přes toto rozhodnutí se v té době ještě nevzdával myšlenky, že svou budoucnost zasvětí hudbě. Co definitivně rozhodlo, bylo jeho setkání s počítačem. Clevelandský institut vlastnil IBM 650, jeden z prvních mainframů, které se využívaly nejen v průmyslu, ale našly si cestu i na řadu univerzit. Donald byl v roce 1957 vybrán do skupiny, která měla v rámci letního semestru na tomto školním počítači zpracovat statistické údaje o škole. Práce na počítači jej zcela uchvátila. Nejenže se podílel na zpracování statistik, ale po večerech studoval manuál k počítači, aby se dokonale seznámil s jeho konstrukcí i programovým vybavením. Než semestr skončil, přepsal překladač počítače, protože zjistil, že dokáže program napsat lépe.

Programování se stalo jeho novou vášní a dokonce zastínilo i lásku k hudbě. To možná není přesné. Neboť Donald Knuth od počátku vnímal tvorbu programů nejen jako ryze technickou záležitost, ale i jako umění. Kvůli počítačům dokonce změnil obor a zaměřil se na studium matematiky. Programování jej také brzy proslavilo.

Následujícího roku totiž vytvořil program určený k analýze výkonnosti univerzitního basketbalového týmu, který trenéři začali využívat. Tým institutu v roce 1960 vskutku získal pohár v zápolení univerzit, což přineslo Donaldovi nečekanou publicitu – IBM použilo jeho fotku ve svých propagačních materiálech a o programu vyšel krátký článek i v celonárodním týdeníku Newsweek. A co víc, vedení školy mu za vynikající práci i vytvoření užitečného programu udělilo oba vědecké tituly (bakalář a master) zároveň. Díky tomu mohl v doktorském studiu pokračovat na prestižním Caltechu (California Institute of Technology). Zbývá dodat, že již během vysokoškolského studia publikoval dva významné matematické články (nemluvě o humoristickém článku nazvaném Potrzebijský systém vah a měr, jenž byl parodií na diskurz standardní metrické soustavy a který je ukázkou Knuthova pověstného smyslu pro humor).

Než nastoupil na Caltech, pracoval krátce také pro Burroughs Corporation. Společnost Burroughs, jež byla v té době jedním z konkurentů IBM se na trhu prosadila především díky elektronkovému sálovému počítači Burroughs 205. Ten vycházel ze stroje Datatron 205 od firmy ElectroData, kterou společnost Burroughs koupila, a disponoval bubnovou magnetickou pamětí o kapacitě 4 tisíce slov (jedno slovo mělo 41 bitů), díky jejíž zvláštní konstrukci byl počítač na svou dobu poměrně rychlý. Programoval se samozřejmě v assembleru, přičemž vyspělejší verze tohoto assembleru, označovaná jako Shell Assembler, umožňovala kromě symbolických názvů a instrukcí pracovat i symbolickými adresami a makry, což bylo z hlediska programování výhodné.

Když se Knuth s tímto mainframem i způsobem jeho programování seznámil, uzavřel se společností Burroughs smlouvu na vytvoření překladače jazyka Angol 58, který byl tehdy horkou novinkou. Úspěšný výsledek práce mu přinesl nejen finanční ohodnocení, ale i místo externího konzultanta. Pozoruhodné také je, že zakázku dokázal vypracovat za pouhé tři a půl měsíce, a to během prázdnin, než nastoupil na Caltech. Jako bonus dodal k překladači i podrobný manuál. (V literatuře se přitom uvádí, že tento Knuthův kompiler obsahoval pouze jednu chybu, což je na program napsaný v assembleru za tak krátkou dobu bezesporu pozoruhodný výsledek.)

Poté, co v roce 1963 získal Donald Knuth doktorát, působil několik let na Caltechu jako vědecký pracovník. V té době měl ve svém oboru již věhlas. Kromě činnosti na univerzitě pracoval také pro Association for Computing Machinery, instituci sdružující nejvýznamnější počítačové vědce, a byl editorem odborného časopisu Programovací jazyky (Programmig Languages). Ve své vědecké práci se soustředil na aplikaci počítačové techniky při řešení algebraických a kombinatorických úloh a zvláště na analýzu algoritmů. Významné práce v této oblasti mu v roce 1968 umožnily stát se profesorem počítačové vědy na Stanfordské univerzitě. Téhož roku rovněž vyšel první díl jeho životního díla.

Zpět k základním kamenům

Monografie Umění programování (The Art of Computer Programming) měla být původně nevelká brožura. V roce 1962, tedy ještě během jeho doktorského studia, se na Donalda Knutha obrátilo nakladatelství odborné literatury Addison-Wesley s návrhem, zda by nechtěl napsat příručku o programování. Knuth souhlasil a podepsal s nakladatelem smlouvu. Knihu, jež měla mít dvanáct kapitol a rozsah zhruba do dvou stovek stran, začal psát v témže roce, jenomže záhy zjistil, že by bylo daleko přínosnější, kdyby jednotlivá témata související s programováním (se zvláštním důrazem na vytváření a analýzu algoritmů) probral do hloubky.

Zpracování informací bylo zahájeno s vývojem matematického myšlení a Knuth se rozhodl, že tyto základní matematické principy, na nichž fungují počítače a jejich programování, pokusí osvětlit krok za krokem a pokud možno v náležitých souvislostech a co nejúplněji. Protože počet stránek stále narůstal, vypracoval koncepci celého díla do několika svazků a seznámil s touto změnou svého nakladatele. Ten s tím souhlasil, neboť kvalitní práce tohoto rozsahu, jež by čtenáře podrobně seznámila s matematickými principy programování, na trhu dosud chyběla.

Jak už bylo předznamenáno, první díl Umění programování vyšel v roce 1968. Jeho název zněl Základní algoritmy. Kniha si okamžitě získala pozornost jak odborné veřejnosti, tak i laických zájemců o počítače. První díl se věnuje tématům, jimiž jsou diskrétní matematika, programování ve strojovém jazyce (Kapitola 1) a datové struktury (Kapitola 2). Aby co nejlépe seznámil čtenáře s problematikou počítačového algoritmu, rozhodl se Knuth, že pro výklad nevyužije žádný z vyšších programovacích jazyků, které se v té době již hojně používaly (tedy FORTRAN či COBOL), ale namísto toho zvolil výklad ve strojově orientovaném jazyce. To mu umožnilo daleko lépe navázat na samotné matematické principy algoritmizace a vysvětlit řadu velmi důležitých otázek nízké úrovně, jako jsou linkování koprogramů, generování náhodných čísel či problematiku související s efektivním využíváním paměti. „Člověk s vážnějším zájmem o počítače,“ je Knuth přesvědčen, „by měl mít dobré znalosti strojového jazyka, protože je jednou z nejdůležitějších součástí počítače.“

Tato volba ovšem představovala zároveň problém, že kniha bude omezena na jeden konkrétní stroj. Ale autor jej vyřešil tak, že vytvořil hypotetický „ideální“ počítač MIX pracující podle velmi jednoduchých pravidel, ale zároveň značně připomínající tehdejší skutečné počítače. Na příkladu počítače MIX, jehož vlastnosti jsou v knize zevrubně probrány, pak Knuth velmi srozumitelně popisuje možnosti programovacího jazyka nejnižší úrovně. (Řada dobrovolníků později napsala simulátory tohoto „mýtického“ počítače, které jsou dnes ideální pomůckou při výuce programování.)

V následujících pěti letech vyšly další dva díly nazvané Seminumerické algoritmy (1969) a Řazení a vyhledávání (1973). To už nebylo pochyb, že Umění programování se stalo základní knihou oboru informatiky. To ostatně později stvrdil fakt, že kniha byla časopisem American Scientist zařazena mezi stovku nejvýznamnějších vědeckých publikací 20. století. V průběhu deseti let, kdy tyto tři díly vznikaly, se však vývoj počítačové vědy, jednoho z nejdynamičtěji se rozvíjejících oborů, značně posunul kupředu. Proto se Knuth s nakladatelstvím Addison-Wesley dohodl, že než vyjdou další pokračování, připraví revidované vydání prvních tří dílů.

Krása odborného textu

Přípravu druhého vydání Umění programování přerušil spor mezi autorem a nakladatelem. Knuthovi, jenž byl přesvědčen, že i odborná publikace by měla splňovat základní estetické požadavky, se nezamlouval způsob sazby, který nakladatel používal. Z tohoto důvodu se rozhodl, že práci na knize odloží a napíše vlastní sázecí program, díky němuž bude možné vytvořit kvalitní sazbu komplikovaných matematických textů.

Jak bylo jeho zvykem, do problematiky se pustil s úctyhodnou důkladností. (Navíc tím navazoval na práci svého otce, jenž, jak jsme zmínili, vlastnil malou tiskárnu.) Prostudoval nejen literaturu věnovanou typografii a sazbě, ale svou koncepci konzultoval s předními odborníky. Při práci na programu postupně odhalil řadu matematických zákonitostí, které se skrývají za zdánlivě intuitivní prací typografa. Tyto zákonitosti pak v podobě sofistikovaných algoritmů vřadil do svého systému, který pojmenoval TeX (což čtěme jako „Tech“, neboť název je odvozen od řeckého slova „techné“, označujícího umění či dovednost.) Souběžně s TeXem vytvořil i program Metafont umožňující práci s písmem.

Když Donald Knuth v roce 1978 představil první verzi systému TeX na půdě Americké matematické společnosti (American Mathematical Society), vzbudil tím zasloužený zájem. Kvalitní tisk odborných publikací, zvláště těch, které obsahovaly množství vzorců a tabulek, byl dlouhodobým problémem. Knuth svůj systém navíc vyvíjel tak, aby byl přenositelný na libovolnou platformu, ať už jde o mainframy či unixové pracovní stanice (později i klony IBM PC či počítače Apple Macintosh). Tato přenositelnost společně s faktem, že autor poskytl uživatelům oba programy zcela zdarma, výrazně přispěla k rozšíření TeXu. Již v roce 1980 vzniklo při Americké matematické společnosti sdružení TUG (TeX Users Group). To od té doby rozvíjí program TeX a jeho nadstavby, mimo jiné také pořádá pravidelné srazy svých členů, vydává časopis a organizuje nejrůznější typy školení týkající se TeXu a přidruženého softwaru. TeX si tak získal velkou popularitu zejména u odborné veřejnosti. Lze bez nadsázky říci, že tento program výrazně změnil praxi vydávání odborné matematické a technické literatury.

Profesor umění programování

Zatímco Donald Knuth věnoval svou pozornost počítačové typografii a sazbě, zbývalo mu méně času na práci na Umění programování. Na začátku osmdesátých let sice vyšlo druhé, revidované vydání druhého dílu, ale nové vydání třetího dílu se objevilo až na konci let devadesátých. Čtvrtý díl, nazvaný Kombinatorické algoritmy, začal vycházet až v prvním desetiletí tohoto století. To se Knuth, od roku 1995 již emeritní profesor počítačové vědy na Stanfordu (jemuž byla univerzitou zároveň udělena čestná profesura v oboru „umění programování“), mohl na plný úvazek věnovat dokončení tohoto velkolepého díla. Nedočkaví čtenáři jej navíc přesvědčili, aby čtvrtý díl rozdělil do menších svazků, což se v prvním vydání stalo – jednotlivé svazky ovšem vycházely na přeskáčku. V současné době autor píše díl pátý, který má vyjít v roce 2015.

Začteme-li se pozorně do některého z dosud vydaných dílů Umění programování, užasneme nad jasností i hloubkou vhledu, který nám Donald Knuth zprostředkovává. A sotva nás pak překvapí, že je řazen mezi desítku nejvlivnějších vědců současnosti společně s astrofyziky Stephenem Hawkingem a Alanem Guthem, lingvistou Noamem Chomskym, biologem Richardem Dawkinsem, etoložkou Jane Godallovou či fyzikem Stevenem Weinbergem.


 

Donald Ervin Knuth (1938),

americký matematik a počítačový vědec; emeritní profesor počítačové vědy Stanfordovy univerzity. Vystudoval matematiku a fyziku na Case Institute of Technology v Clevelandu, doktorát z matematiky získal na Caltechu (California Institute of Technology). Svůj profesní život spojil se Stanfordovou univerzitou, kde působil jako profesor počítačové vědy. Knuth, který je průkopníkem v oblasti matematické analýzy algoritmů, svými pracemi významně přispěl k rozvoji teoretické počítačové vědy a programování. Napsal řadu odborných publikací a článků, je autorem několikasvazkového a mimořádně vlivného díla Umění programování (The Art of Computer Programming), na němž začal pracovat již v roce 1962 a jehož dalším dílům se dodnes věnuje. Kromě toho vytvořil systémy Metafont a TeX, které se staly standardy počítačové sazby. Za svůj mimořádný přínos v oblasti teoretické počítačové vědy obdržel Knuth řadu významných cen, rovněž získal množství čestných doktorátů, mj. též čestný doktorát Masarykovy univerzity v Brně.

 


 

Literární programování (Literate programming)

Jde o přístup ke psaní počítačových programů, v němž je dokumentace stejně důležitá jako samotný kód programu, ne-li důležitější. Tím se zásadně mění tradiční filosofie psaní programů. Programátor namísto toho, aby sděloval počítači, co má jeho program dělat, se zaměřuje na to, aby vysvětlil čtenářům svého programu, co chce, aby program dělal. Z počítačových programů se tak stávají literární díla, jejichž posláním je poskytnout informace o tom, jak v nich obsažené programy fungují. Tento přístup k programování pak přináší obrovskou výhodu. Neboť pokud je čtenář přehledně a srozumitelně seznámen s tím, co jednotlivé části programu dělají, jak spolu souvisejí či komunikují a jak celý program pracuje, je také schopen jej upravovat a měnit, aniž se dopustí vážných pochybení, která vznikají při nesprávném či pouze přibližném pochopení činnosti programu.


Úvodní foto: IDG

Vyšlo v CIO Business World 5/2012
Časopis lze koupit se slevou 20 %





Komentáře