Rekurzívny úvod do teórie výpočtovej techniky

Pôvodný názov:

A Recursive Introduction to the Theory of Computation

Obsah knihy:

Cieľom tejto učebnice je podať výklad teórie výpočtov.

Po zavedení pojmu model výpočtu a uvedení rôznych príkladov autor skúma obmedzenia efektívneho výpočtu prostredníctvom základnej teórie rekurzie. Autoreferencia a ďalšie metódy sú predstavené ako základné a východiskové nástroje na konštrukciu a manipuláciu algoritmov.

Ďalej sa v knihe uvažuje o zložitosti výpočtov a zavádza sa pojem miery zložitosti. Nakoniec kniha vrcholí úvahami o časových a priestorových mierach a klasifikáciou vypočítateľných funkcií ako uskutočniteľných alebo neuskutočniteľných. Autor predpokladá len základnú znalosť diskrétnej matematiky a výpočtovej techniky, takže táto učebnica je ideálna pre úvodný kurz na úrovni absolventov.

Vychádza z mnohých takýchto kurzov, ktoré autor prezentoval, a preto sú v nej zahrnuté početné cvičenia. Okrem toho sú k väčšine týchto cvičení uvedené aj riešenia.