Janusz Marecki
Jacek Skalmierski Computer Studio, 2004
Preface
The book introduces the basic elements of theoretical computer science, such as formal languages, automata, computational models and classes of algorithms. Since both algorithms as well as computational models are associated with particular languages, first part of the book is dedicated to the theory of formal languages and automata. Starting from the basic languages, the book subsequently analyses languages of increased complexity, finishing the study on languages only recognizable by the Turing Machine or its equivalent computational model. The book then discusses (i) recursive functions that can be expressed in the Turing Machine formalism, (ii) various computational models such as the lambda calculus and (iii) algorithm complexity classes. Finally, the book outlines different classes of algorithms, studies their complexity and provides their pseudo-code implementation. The control questions at the end of the book can be used to test the acquired knowledge.
BibTex
