Umění programování, 1. díl - Základní algoritmy

Recenze jedné z nejvlivnějších učebnic programování od světoznámého autora, držitele Turningovy ceny, IEEE Computer Pioneer Award či americké národní medaile za vědu, Donalda Ervina Knutha.

Série knih Umění programování má celkem 5 svazků a 10 kapitol. Tato recenze je psána o prvním svazku, zvaném Základní algoritmy a nesoucím 2 kapitoly celého mistrovského díla. Umění programování je opravdu velmi rozsáhlý zdroj pro teoretické i praktické řešení programátorských problémů od elementárních výpočtů až po složité kombinatorické problémy. Jak sám autor píše, kniha je stále ve vývoji a po přepracování všech svazků na třetí vydání se chystá znovu celou sérii aktualizovat pro zachycení všech ostatních prvků moderního programování. Struktura celého veledíla vypadá následovně:

Svazek 1. Základní algoritmy

• Kapitola 1. Základní principy
• Kapitola 2. Informační stuktury

Svazek 2. Seminumerické algoritmy

• Kapitola 3. Náhodná čísla
• Kapitola 4. Aritmetika

Svazek 3. Řazení a vyhledávání

• Kapitola 5. Řazení
• Kapitola 6. Vyhledávání

Svazek 4. Kombinatorické algoritmy

• Kapitola 7. Kombinatorické vyhledávání
• Kapitola 8. Rekurze

Svazek 5. Syntaktické algoritmy

• Kapitola 9. Lexikální prohledávání
• Kapitola 10. Lexikální analýza

Cvičení

Kniha je bohatě protkána velmi vydařenými cvičeními, která následují po každé podkapitole nebo chcete-li, po každém rozebíraném problému. Většinu cvičení by měl zvládnout člověk se středoškolskou znalostí matematiky, a to včetně diferenciálního a integrálního počtu či znalosti komplexních čísel. Cvičení spíše matematického rázu jsou v knize označována písmenem M, písmeny VM jsou označována cvičení, jež vyžadují znalost některých věcí z vysokoškolské matematiky. Série má svoji hiearchii i co se týče náročnosti cvičení na vypracování. Autor ji popisuje čísly 00 - 50, a to s následujícím popisem:

• 00 - okamžitá odpověď
• 10 - jednoduchá (do jedné minuty)
• 20 - průměrná (čtvrt hodiny)
• 30 - středně obtížná
• 40 - semestrální projekt
• 50 - výzkumný problém

Jak už jste jistě postřehli, narazíte i na cvičení nazvaná jako výzkumný problém. V praxi to znamená problém, na který dosud nebylo nalezeno plně uspokojivé řešení. Jako příklad jednoho takového výzkumného problému uvedu následující cvičení. [Poznámka: Algoritmus E uvedený ve cvičení níže je algoritmus pro zjištění největšího společného dělitele dvou čísel.]

[50] (R. W. Floyd) Vytvořte počítačový program, který na vstupu převezme program v nějakém programovacím jazyce a nepovinně také jistá tvrzení a dále se pokusí doplnit zbývající tvrzení potřebná k důkazu správnosti programu. (Tento program by se například měl pokusit dokázat platnost Algoritmu E, přičemž vyjde jen z tvrzení A1, A4 a A6. Další výklad viz příspěvky R. W. Floyd a J. C. King, IFIP Congress proceedings, 1971.)

Kapitola 1. - Základní principy

V první kapitole je na prvních několika desítkách stran shrnut a podrobně vysvětlen matematický základ, který budete ke čtení celé série potřebovat. Pokud to vezmu popořadě, jako první vás čeká osvětlení principů matematické indukce, která je, jak sám autor poznamenává, nesmírně důležitá pro rozbor algoritmů či matematických problémů. Dále následuje náhled do problematiky čísel, mocnin a logaritmů, poté operace se součty a součiny, použití celočíselných funkcí a úvod do teorie čísel. Na dalších stranách se setkáte s kombinatorickými problémy, a to přesně s permutacemi, faktoriály a binomickými koeficienty. Poté následují harmonická a Fibonacciho čísla, což je problematika číselného rozvoje, a v neposlední řadě generující funkce pro práci s posloupnostmi čísel. Jako dvě poslední podkapitoly matematické části shledáte analýzu algoritmů a asymptotickou reprezentaci zahrnující O-notace, Eulerův sumační vzorec a některé asymptotické výpočty. Celá tato matematická část je pojata do potřebné hloubky a s potřebnou dávkou vysvětlení, aby byly použité vztahy relativně snadno pochopitelné a, jak již jsem řekl na začátku recenze, člověk se znalostí středoškolské matematiky by se neměl setkat s žádným větším problémem. Za každou výše zmíněnou problematikou samozřejmě následuje sada cvičení, na níž si můžete zjistit, zda onu problematiku zcela chápete. Cvičení jsou samozřejmě opatřena řešeními, jež naleznete na konci knihy.

V dalším pokračování 1. kapitoly vás autor seznámí s počítačem MIX, pro nějž budou vytvořeny vzorové algoritmy. Pro kódovou prezentaci řešených problémů bylo použito strojového jazyka (ASSEMBLER) pro tento počítač. Jak autor zmiňuje, mohl použít některý z vyšších programovacích jazyků, ale pro rozsáhlou použitelnost zvolil jazyk strojový. Možná se zaleknete, že počítač MIX je stroj z 60. - 70. let minulého století, ale nejde zde o naučení se programovacího jazyka, ale o pochopení principů programování, jež jsou používanými základy dodnes. Tím samozřejmě myslím, že kniha je pojata podle nejnovějších programátorských trendů. Mimoto D. E. Knuth připravuje, po přepracování všech knih na 3. vydání, vydání čtvrté, které již bude psáno pro počítač MMIX 2009. Ale abych se vrátil k obsahu kapitoly. Jsou zde popsány vlastnosti počítače MIX a možnosti strojového jazyka pro něj použitého. Seznámíte se zde se základními příkazy pro práci s daty a pamětí, dále s prvními jednoduchými příklady algoritmů napsaných v ASSEMBLERU. Na posledních listech první kapitoly se seznámíte s některými základními technikami programování - například s podporgramy, koprogramy, interpretačními programy a vstupy a výstupy.

Kapitola 2. - Informační struktury

Kapitola Informační struktury je tvořena z pěti podkapitol, z nichž jsou dvě dále bohatě rozvinuté do několika dílčích problémů. V této části se velmi dobře a podrobně seznámíte se strukturovanými proměnnými (jako je například pole) a s informačními strukturami jako takovými, s nimiž se naučíte pracovat v mnoha různých směrech. Abych vás obeznámil, s čím vším se v kapitole setkáte, tak to shrnu do kratičké rekapitulace témat. Hned po úvodu do problematiky vás autor zavede do tajů lineárních seznamů, což jsou jednodušší informační struktury, které se dále dělí na zásobníky, fronty a oboustranné fronty, dále na kruhové seznamy, obousměrné propojené seznamy a pole a ortogonální seznamy. Důležitými pojmy pro práci s těmito prvky jsou sekvenční a spojová alokace, jež jsou zde také precizně popsány. Druhou obsáhlejší podkapitolou jsou stromy, což znamená již složitější větvené struktury. Je zřejmé, že práce se stromy bude mnohem náročnější než práce s lineárními seznamy. Ovšem díky autorovým zkušenostem se vaše znalosti obohatí o spoustu nových tipů a fíglů, jak tyto struktury efektivně ovládat. Nastíním vám také výčet toho, co se v kapitole dozvíte. Zaprvé je to procházení binárním stromem a reprezentace stromu binárním stromem, posléze i jiné reprezentace stromu. V rozsáhlejším měřítku autor probírá základní matematické vlastnosti stromů a nakonec seznamy a uvolňování paměti. Ke konci knihy se dozvíte i něco o vícenásobně propojených strukturách a dynamické alokaci paměti.

Stejně jako předešlý obsah knihy je tato část velice dopodrobna popsaná, tudíž není problém ji pochopit. Autor se hodně věnuje teoretické části struktur a práce s nimi. Krom příkladových algoritmů je zde opět široká škála cvičení, na nichž si ověříte, do jaké hloubky jste problém pochopili. Kapitola shrnuje vesměs ta nejdůležitější fakta o informačních strukturách, jejich statické a dynamické vlastnosti či algoritmy pro vytváření, změny, přístup a odstraňování strukturálních informací. Pro práce se strukturami, především stromy je potřebná dobrá znalost diagramů, množin a matic, ale o tom si samozřejmě přečtete vše potřebné v předešlé kapitole.

Knihu vám vřele doporučuji, protože se jedná o opravdový skvost programátorské literatury a domnívám se, že by neměla chybět v knihovně žádného člověka, který se chce o programování (navrhování algoritmů) do hloubky zajímat.