Provides an introduction to some of the central ideas of theoretical computer science, including circuits, finite automata, Turing machines and computability, efficient algorithms and reducibility, the P versus NP problem, NP-completeness, the power of randomness, cryptography, computational learning theory, and quantum computing. Examines the classes of problems that can and cannot be solved in various computational models.
——S. Aaronson
Contents
Materials
- Introduction to the Theory of Computation
third edition by MICHAEL SIPSER -
ERRATA
简称勘误表，作者良心维护中，点个赞 -
Solution-Manual
简称答案，Sipser 竟然给了大部分习题的答案 -
在线学生资源
一小部分要美帝学生证才能访问🙂 -
OCW
这门课并没有视频🙂 -
斌头三三的学习笔记
曾经谷歌搜索“计算理论导引”排第三 hhh -
北大的mooc
同学的推荐
Preface
这里有一段关于 “为什么要学理论”的论述，说的很好：
Theory is relevant to practice. It provides conceptual tools that practitioners use in computer engineering. Designing a new programming language for a specialized application? What you learned about grammars in this course comes in handy. Dealing with string searching and pattern matching? Remember finite automata and regular expressions. Confronted with a problem that seems to require more computer time than you can afford? Think back to what you learned about NP-completeness. Various application areas, such as modern cryptographic protocols, rely on theoretical principles that you will learn here.
Theory also is relevant to you because it shows you a new, simpler, and more elegant side of computers, which we normally consider to be complicated machines. The best computer designs and applications are conceived with elegance in mind. A theoretical course can heighten your aesthetic sense and help you build more beautiful systems.
Finally, theory is good for you because studying it expands your mind. Computer technology changes quickly. Specific technical knowledge, though useful today, becomes outdated in just a few years. Consider instead the abilities to think, to express yourself clearly and precisely, to solve problems, and to know when you haven’t solved a problem. These abilities have lasting value. Studying theory trains you in these areas.
0 Introduction
0.1 Automata, Computability, and Complexity
对这几个核心概念的概述
0.2 Mathematical Notions and Terminology
一大波数学定义
0.3 Definitions, Theorems, and Proofs
里面这句话讲得很好：
Seeing where you run into difficulty when you attempt to find a counterexample can help you understand why the statement is true.
0.4 Types of Proofs
构造法，反证法，归纳法