强撸MIT之6.045

强撸MIT之6.045

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


Materials


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

构造法,反证法,归纳法


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


发表评论

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