强撸MIT之6.045

强撸MIT之6.045

6.045: Automata, Comput, & Complexity

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


资料

  • Introduction to the Theory of Computation
    third edition by MICHAEL SIPSER

  • ERRATA
    简称勘误表,作者良心维护中,点个赞

  • Solution-Manual
    简称答案,Sipser是个喜欢给答案的宝宝

  • 在线学生资源
    一小部分要美帝学生证才能访问🙂

  • OCW
    这门课并没有视频🙂

  • 斌头三三的学习笔记
    谷歌搜索“计算理论导引”排第三哟

  • 北大的mooc
    来自北大的同学的推荐

  • 后置课程
    据说是研究生课程哟 🙂
    6.840:Theory of Computation

    A more extensive and theoretical treatment of the material in 6.045J/18.400J, emphasizing computability and computational complexity theory. Regular and context-free languages. Decidable and undecidable problems, reducibility, recursive function theory. Time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems. Students in Course 18 must register for the undergraduate version, 18.404.
    ——M. Sipser


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

一大波数学定义(在书的开头扔一波数学基础应该是CS理论课本的套路)

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

构造法,反证法,归纳法


Part One: Automata and Languages

1 Regular Languages

2 Context-Free languages


Part Two: Computability Theory

3 The Church-Turing Thesis

4 Decidability

5 Reducibility

6 Advanced Topics in Computability Theory


Part Three: Complexity Theory

7 Time Complexity

8 Space Complexity

9 Intractability

10 Advanced Topics in Complexity Theory


发表评论

电子邮件地址不会被公开。 必填项已用*标注