Rekurzivní úvod do teorie výpočtů

Původní název:

A Recursive Introduction to the Theory of Computation

Obsah knihy:

Cílem této učebnice je podat výklad teorie výpočtů.

Po zavedení pojmu výpočetní model a uvedení různých příkladů autor zkoumá omezení efektivního výpočtu prostřednictvím základní teorie rekurze. Autoreference a další metody jsou představeny jako základní a základní nástroje pro konstrukci a manipulaci s algoritmy.

Odtud kniha uvažuje o složitosti výpočtů a zavádí pojem míry složitosti. Nakonec kniha vrcholí úvahami o časových a prostorových mírách a o klasifikaci vypočitatelných funkcí jako proveditelných nebo neproveditelných. Autor předpokládá pouze základní znalosti diskrétní matematiky a výpočetní techniky, takže tato učebnice je ideální pro úvodní kurz pro absolventy.

Vychází z mnoha takových kurzů, které autor přednášel, a proto jsou v ní zahrnuta četná cvičení. K většině těchto cvičení jsou navíc uvedena řešení.