Rekursywne wprowadzenie do teorii obliczeń

Oryginalny tytuł:

A Recursive Introduction to the Theory of Computation

Zawartość książki:

Celem tego podręcznika jest przedstawienie teorii obliczeń.

Po wprowadzeniu pojęcia modelu obliczeń i przedstawieniu różnych przykładów, autor bada ograniczenia efektywnych obliczeń za pomocą podstawowej teorii rekurencji. Samoreferencja i inne metody są wprowadzane jako fundamentalne i podstawowe narzędzia do konstruowania algorytmów i manipulowania nimi.

Następnie książka rozważa złożoność obliczeń i wprowadza pojęcie miary złożoności. Wreszcie, książka kończy się rozważaniem miar czasu i przestrzeni oraz klasyfikacją funkcji obliczalnych jako wykonalnych lub niewykonalnych. Autor zakłada jedynie podstawową znajomość matematyki dyskretnej i informatyki, dzięki czemu podręcznik ten idealnie nadaje się na kurs wprowadzający dla absolwentów.

Jest on oparty na wielu takich kursach prezentowanych przez autora, dlatego zawiera liczne ćwiczenia. Ponadto do większości z nich dołączone są rozwiązania.