Introduction to the Theory of Computation pdf epub mobi txt 电子书 下载 2025

想要找书就要到 小美书屋

立刻按 ctrl+D收藏本页

你会得到大惊喜!!

This book is aimed as an introductory text book on computer science theory. The book is suited for both undergraduate and graduate studies. The first three chapters of the book, regular expressions, context free languages and the Church-Turing thesis are apt for an introductory class for the undergraduate level. The remaining 7 chapters provide more than enough content for advanced undergraduate or graduate studies.

This is the first book on computer science theory that I have seen, which is actually written in understandable English. As compared to the previous introductory texts by Hopcroft or Papadimitriou, Sipser shuns writting the entire book using just symbols of formal mathematics. This is not to say that there is no formalism in the book. There is adequate use of formal mathematics in the proofs of the book, but not so much as to scare even in most intrepid readers like in previous books on this subject.The fact I liked most about this book is that every proof in the book is accompanied by a "Proof Idea" which explains using diagrams and plain english how exactly the proof works. This followed by the formal proof. The problems at the end of each chapter are fairly interesting, and some of the * marked problems can be fairly challenging for a first time student.

Another amazing thing about this book is the amount of content it covers. I would have never expected a book of only 400 pages to cover computer science theory all the way from introductory undergraduate to advanced graduate levels. This is because, the author focuses only on core concepts and strives to make them as clear as possible. For example, this book has only one chapter on regular expressions, while every other book that I have seen has at least 3-4 chapters full of gory details. This is because Sipser does not go into the gory mechanical details of converting DFAs to NFAs, or writing Turing machines and so on, but instead explains just the important concepts and gives a few examples. Also a wealth of information is to be found in the problems at the end of the chapter. Many of these problems like the Myhill-Nerode theorem are of the kind you will find actually proved in other texts, but left as an exersice here. This is because they are relatively simple to prove once all the concepts are understood. Moreover an educator has the option of which of these problems they want to delve deeper into.

Any student who studies or wishes to study computer science theory should definitely get their hands on this book, irrespective of whether they have already used a different book.

本篇介绍来自amazon.com读者评价

Michael Fredric Sipser (born September 17, 1954) is a theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of Applied Mathematics and Dean of Science at the Massachusetts Institute of Technology.

Preface
To the student
To the educator
The current edition
Feedback to the author
Acknowledgments
0 Introduction
0.1 Automata, Computability, and Complexity
0.2 Mathematical Notions and Terminology
0.3 Definitions, Theorems, and Proofs
0.4 Types of Proofs
Part One: Automata and Languages
1 Regular Languages
1.1 Finite Automata
1.2 Nondeterminism
1.3 Regular Expression
1.4 Nonregular Languages
2 Context-Free Languages
2.1 Context-Free Grammar
2.2 Pushdown Automata
2.3 Non-Context-Free Languages
Part Two: Computability Theory
3 The Church-Turing Thesis
3.1 Turing Machines
3.2 Variants of Turing Machines
3.3 The Definition of Algorithm
4 Decidability
4.1 Decidable Languages
4.2 The Halting Problem
5 Reducibility
5.1 Undecidable Problems from Language Theory
5.2 A Simple Undecidable Problem
5.3 Mapping Reducibility
6 Advanced Topics in Computability Theory
6.1 The Recursion Theorem
6.2 Decidability of Logical Theories
6.3 Turing Reducibility
6.4 A Definition of Information
Part Three: Complexity Theory
7 Time Complexity
7.1 Measuring Complexity
7.2 The Class P
7.3 The Class NP
7.4 NP-Completeness
7.5 Additional NP-Complete Problems
8 Space Complexity
8.1 Savitch's Theorem
8.2 The Class PSPACE
8.3 PSPACE-Completeness
8.4 The Classes L and NL
8.5 NL-Completeness
8.6 NL equals coNL
9 Intractability
9.1 Hierarchy Theorems
9.2 Relativization
9.3 Circuit Complexity
10 Advanced Topics in Complexity Theory
10.1 Approximation Algorithms
10.2 Probabilistic Algorithms
10.3 Alternation
10.4 Interactive Proofs Systems
10.5 Parallel Computation
10.6 Cryptography
Selected Bibliography
Index
· · · · · · (收起)