O introducere recursivă în teoria calculatoarelor

Titlul original:

A Recursive Introduction to the Theory of Computation

Conținutul cărții:

Scopul acestui manual este de a prezenta o prezentare a teoriei calculului.

După introducerea conceptului de model de calcul și prezentarea diferitelor exemple, autorul explorează limitele calculului eficient prin intermediul teoriei de bază a recursivității. Auto-referința și alte metode sunt introduse ca instrumente fundamentale și de bază pentru construirea și manipularea algoritmilor.

În continuare, cartea analizează complexitatea calculelor și este introdusă noțiunea de măsură a complexității. În cele din urmă, cartea culminează cu luarea în considerare a măsurilor de timp și spațiu și cu clasificarea funcțiilor calculabile ca fiind fezabile sau nu. Autorul presupune doar o familiaritate de bază cu matematica discretă și calculul, ceea ce face ca acest manual să fie ideal pentru un curs introductiv de nivel universitar.

Acesta se bazează pe multe astfel de cursuri prezentate de autor și, prin urmare, sunt incluse numeroase exerciții. În plus, sunt furnizate soluțiile la majoritatea acestor exerciții.