Rekurzív bevezetés a számításelméletbe

Eredeti címe:

A Recursive Introduction to the Theory of Computation

Könyv tartalma:

A tankönyv célja, hogy bemutassa a számításelméletet.

A számítási modell fogalmának bevezetése és különböző példák bemutatása után a szerző a hatékony számítás korlátait vizsgálja az alapvető rekurzióelméleten keresztül. Az önreferencia és más módszerek mint az algoritmusok felépítésének és manipulálásának alapvető és alapvető eszközei kerülnek bemutatásra.

Innen kiindulva a könyv a számítások bonyolultságát vizsgálja, és bemutatja a bonyolultsági mérték fogalmát. Végül a könyv az idő- és térmértékek figyelembevételével, valamint a kiszámítható függvények megvalósítható vagy nem megvalósítható kategóriákba sorolásával zárul. A szerző csak alapvető ismereteket feltételez a diszkrét matematikában és a számítástechnikában, így ez a tankönyv ideális egy felsőfokú bevezető kurzushoz.

A szerző által bemutatott számos ilyen kurzuson alapul, ezért számos feladatot tartalmaz. Ezenfelül a legtöbb ilyen feladat megoldását is közli.