Elements of the Theory of Computation

0.0

The practical successes of computer science are built on its elegant and solid foundations. The purpose of this book is to introduce students to these fundamental ideas, models, and results that permeate computer science-the basic paradigms of this field. Much of modern computation is based more or less explicitly on these ideas and models of lasting value though mathematical in nature. It is hard to understand computer science without first being exposed to these formal foundations. This book provides coverage of the basics of classical and contemporary theory of computation. The topics covered include the theory of automata and formal languages, computability by Turing machines and recursive functions, uncomputability, computational complexity, and Boolean logic. The second edition also provides a descent introduction to the subject of algorithms. The rudiments of the design and analysis of algorithms are first introduced and then linked with the models of computation studied in the text. The book also explains an array of algorithmic techniques that have been successfully used in dealing with NP-complete problems. In a nutshell, the essentials of the subject of computation and algorithms are made more accessible to students in a way that is mathematically sound but the viewpoint is that of computer science. Table of Contents Preface to the First Edition. Preface to the Second Edition. Introduction. 1. Sets, Relations, and Languages. 2. Finite Automata. 3. Context-free Languages. 4. Turing machines. 5. Undecidability. 6. Computational Complexity. 7. NP-completeness. Index.