Introduction to the Theory of Computation
- ISBN-10
- 0619217642
- ISBN-13
- 9780619217648
- Series
- Introduction to the Theory of Computation
- Category
- Computational complexity
- Pages
- 437
- Language
- English
- Published
- 2006
- Publisher
- Thomson/Course Technology
- Author
- Michael Sipser
Description
"Intended as an upper-level undergraduate or introductory graduate text in computer science theory," this book lucidly covers the key concepts and theorems of the theory of computation. The presentation is remarkably clear; for example, the "proof idea," which offers the reader an intuitive feel for how the proof was constructed, accompanies many of the theorems and a proof. Introduction to the Theory of Computation covers the usual topics for this type of text plus it features a solid section on complexity theory--including an entire chapter on space complexity. The final chapter introduces more advanced topics, such as the discussion of complexity classes associated with probabilistic algorithms.
Get the book
Other editions
Similar books
-
Introduction to Languages and the Theory of Computation
By John C. MartinA distinctive feature of this text is its gentle and gradual introduction of the necessary mathematical tools in the context in which they are used.
-
Introduction to Automata Theory, Formal Languages and Computation
By Shyamalendu KandarFormal languages and automata theory is the study of abstract machines and how these can be used for solving problems. The book has a simple and exhaustive approach to topics like automata theory, formal languages and theory of computation.
-
Theory of Computation
By Dexter C. KozenThe book contains an invaluable collection of lectures for first-year graduates on the theory of computation. Topics and features include more than 40 lectures for first year graduate students, and a dozen homework sets and exercises.
-
Computability and Complexity: From a Programming Perspective
By Neil D. JonesNew results in the book include a proof that constant time factors do matter for its programming-oriented model of computation. (In contrast, Turing machines have a counterintuitive "constant speedup" property: that almost any program can ...
-
Theory of Computer Science: Automata, Languages and Computation
By K. L. P. Mishra, N. CHANDRASEKARANThis Third Edition, in response to the enthusiastic reception given by academia and students to the previous edition, offers a cohesive presentation of all aspects of theoretical computer science, namely automata, formal languages, ...
-
Programs and Machines: An Introduction to the Theory of Computation
By Richard BirdPrograms and Machines: An Introduction to the Theory of Computation
-
Introduction To The Theory Of Neural Computation
By John A. HertzIn each group of the intermediate layer the four units learn to respond to three vertical, or three horizontal lines. The output layer learns the correlations between the two groups in the intermediate layer, which normally leads to ...
-
Theory of Computation
By George TourlakisD. Gries and F. B. Schneider. A Logical Approach to Discrete Math. Springer-Verlag, New York, 1994. A. Grzegorczyk. Some classes of recursive functions. Rozprawy Matematyczne, 4: 1-45, 1953. H. Müller.
-
Models of Computation: An Introduction to Computability Theory
By Maribel FernándezAt the end of each chapter there is a list of exercises, solutions to selected exercises are provided in the final chapter of the book. The book gives an in-depth analysis of the basic concepts underlying each model of computation.
-
Limits of Computation: An Introduction to the Undecidable and the Intractable
By Edna E. Reiter, Clayton Matthew Johnsonbecomes “Given this chess board and a suggested move, can White force a win by making this move?” In all cases that we will use, there are an infinite number of possible inputs, which are divided into the yes instances and the no ...