Kořeny knihy sahají do druhé poloviny šedesátých let. Jednotlivá vydání jsou postupně vylepšována, přesto jádro učebnice zůstává nezměněné. Umění programování se totiž soustředí na „nadčasovou“ teorii a vůbec se nezabývá aktuálními technologiemi nebo zvyklostmi v programátorské praxi. Tím se odlišuje od běžných učebnic pro vývojáře. V současnosti jsou z Umění programování plně dokončeny pouze první tři svazky Základní algoritmy, Seminumerické algoritmy, Třídění a vyhledávání. Do češtiny byly přeloženy zatím jen první dva díly. Následující čtyři díly (Kombinatorické algoritmy, Syntaktická analýza, Teorie bezkontextových jazyků, Techniky kompilátorů) se nacházejí v různém stupni rozpracování.
Originální verzi vydalo nakladatelství Addison-Wesley, které je proslavené publikací podobně zaměřených studijních materiálů (např. Concrete Mathematics: A Foundation for Computer Science). Nejedná se přímo o odborné vědecké publikace, které známe například z produkce nakladatelství Springer Verlag. Na druhou stranu po dokončení bude série Umění programování natolik obsáhlá, že čtenář, který nastuduje všechny díly a poctivě si promyslí všechna cvičení, získá velmi solidní teoretický základ. Takto nabyté dovednosti a znalosti výrazně překračují standard vysokoškolských studijních oborů zaměřených na informatiku.
Titulní strana knihy
Obsah knihy Seminumerické algoritmy
Podle předmluvy odkazuje adjektivum „seminumerický“ v názvu knihy ke skutečnosti, že probíraná látka se nachází na pomezí numerických a symbolických výpočtů. Knihu tvoří dvě kapitoly. První, kratší kapitola Náhodná čísla se zabývá definováním základních pojmů, rozborem pojmu náhodná posloupnost, metodami generování (pseudo)náhodné posloupnosti, metodami generování různých náhodných rozdělení a statistickými testy náhodnosti posloupnosti. Druhá rozsáhlejší kapitola Aritmetika zkoumá reprezentaci čísla v různých pozičních číselných soustavách, algoritmy pro numerické výpočty ve vysoké přesnosti, základní algebraické struktury, modulární aritmetiku, aplikace Čínské zbytkové věty, dělitelnost, vlastnosti prvočísel, testy prvočíselnosti, aritmetiku polynomů, algoritmy pro efektivní výpočty hodnot polynomů v daném bodě, bilineární formy, práci s nekonečnými mocninnými řadami. Kniha opomíjí příliš teoretické partie aritmetiky spadající do teorie složitosti a vypočítatelnosti. Kniha například nerozebírá zásadní větu, že řešitelnost celočíselné (diofantické) rovnice není algoritmicky rozhodnutelná.
Ke každé podkapitole je připojeno množství navazujících cvičení. Předem tak víme, že v řešení se použijí tvrzení předcházející podkapitoly, čímž se mnohdy výrazně snižuje obtížnost. V knize se setkáme s implementačními, numerickými, důkazovými, diskusními a dalšími typy úloh. Jako ilustraci rozmanitosti úloh uvádím zkrácená a místy přeformulovaná znění několika zadání:
-
Do jaké podoby se zredukuje spektrální test v jedné dimenzi?
-
Napište program, který náhodně zamíchá balíček karet, sehraje některou z her solitérového typu a analyzuje výsledek hry. Diskutujte kumulovanou statistiku mnoha výsledků těchto simulací.
-
V pořadu Myslící stroj byly sehrány scénky podle scénáře náhodně vygenerovaného počítačem. V létě 1952 Christopher Strachey s pomocí náhodného generátu vytvořil následující dopis. Čtenáře jistě napadne mnoho myšlenek, jak „naučit“ počítač tvůrčímu psaní; a právě to je cílem tohoto cvičení.
-
Jaký je úplný rozklad polynomu x5 + x4 + x2 + x + 2 nad polem racionálních čísel?
-
Dokažte, že náhodný primitivní polynom nad celými čísly je „skoro vždy“ irreducibilní.
-
Potřebujete bez počítače zvolit jednu náhodnou desítkovou číslici. Diskutujte, která z následujících metod je nejvhodnější. a) Otevřeme telefonní seznam a vezmeme první číslici z prvního čísla na stránce. ... h) Do dostihů je přihlášeno deset koní, které neznáte. Před závodem koně očíslujeme a po závodě vybereme číslici vítěze.
Cvičení jsou označena čísly od 0 do 50 podle předpokládané obtížnosti. Dále mohou být cvičení označena písmenem M (matematicky orientované) a VM (vyžaduje „vyšší matematiku“). Výše uvedená cvičení jsou označena jako M10, 40, 46, M25, VM30 a 20. V závěru výtisku se bezmála 200 stránek věnuje podrobnému řešení všech cvičení.
Závěrečné poznámky
Autor Donald Knuth je známým počítačovým vědcem, který byl vyznamenán mimo jiné Turingovou cenou. Donald Knuth se věnoval i typografii. Pro účely sazby druhého vydání Umění programování začal vyvíjet systém TeX, který byl vůbec prvním pokročilým typografickým softwarem. V současné době je sada maker LaTeX pro systém TeX nejpoužívanějším řešením pro sazbu odborných publikací.
Druhý díl nevyžaduje znalost prvního dílu, a tudíž může být rozumné si zakoupit pouze druhý díl. Pro účely výkladu byly Donaldem Knutem navrženy speciální stroje MIX a MMIX, přičemž jejich popis je uveden pouze v prvním díle série a na několika místech druhého dílu jsou předvedeny zdrojové kódy pro MIX. Anglickou dokumentaci těchto počítačů naleznete volně na internetu.
Kniha má 776 stran, formát je 167 × 225 mm, kniha je vázána a má laminovaný potah desek. Těmito vlastnostmi vzhledově připomíná například Matematické vzorce od Hanse-Jochena Bartsche. Běžná cena knihy je 990 Kč.
Umění programování od Donalda Knutha nemá nic společného s knihou Umění programování v Unixu od Erica Raymonda.
Pět argumentů pro koupi knihy
-
V knize naleznete stravitelným způsobem vysvětlenou matematiku se zajímavými úlohami.
-
Získané znalosti využijete při psaní numerického softwaru.
-
Kniha je ukázkou „vysoké“ typografie u rozsáhlého, složitě strukturovaného textu s množstvím matematických zápisů. Umění programování lze studovat jako ukázku, jak má správně vypadat matematická sazba.
-
Kniha odkazuje na vědecké publikace a články. U většiny výsledků je uveden autor a původní vědecký článek.
-
Jde o jednu z reprezentativních publikací, která má velký historický význam. U knižní řady Umění programování se dá mluvit o sběratelské hodnotě.
