您可以通过在Amazon.com上购书来支持MIT开放课件。
通过和Amazon.com的合作 MIT OCW提供购买本课程参考书籍的直接链接。点击书的标题，
您就可以在Amazon.com上面购买书籍了，OCW将会受到您购买金额的10%。
您的支持会让MIT提供更多和更好的开放课程。
本部分包含了每周需要阅读的资料。其中大部分都是课程的课本的阅读和学习。课本如下： Sipser, Michael. 计算理论导引（Introduction to the Theory of Computation）.
2nd ed. Boston, MA: Course Technology, 2005. ISBN: 0534950973.
Course readings.
| 学时 # |
主题 |
阅读材料 |
| 课程简介和基础知识回顾 |
| L1 |
课程简介 |
第 0 章 |
| R1 |
数学知识回顾 |
第 0 章 |
| 有限自动机，正则语言，正则表达式 |
| L2 |
确定有限自动机 (DFA) |
第 1.1节 |
| L3 |
非确定有限自动机(NFA) |
|
| R2 |
DFA和NFA |
第 1.1和 1.2节 |
| L4 |
正则表达式 |
第 1.3 节 |
| L5 |
非正则语言 |
第 1.4 节 |
| R3 |
正则表达式和非正则语言复习 |
第1.3, 1.4节 |
| L6 |
自动机的算法 |
第1 章以及4.1节 |
| L7 |
第1次测验 |
|
| R4 |
第一次测验讲解自动机复习 |
|
| 计算理论 |
| L8 |
图灵机 |
第3 章(第3.1, 3.3节以及3.2节中非确定性内容以外的部分) |
| L9 |
非确定图灵机 |
第3.2节 (尤其是138-141页), 第4.2节(尤其是160-164页) |
| R5 |
图灵机 |
第3章 |
| L10 |
不可判定性 |
第4张 (156-158页有关上下文无关语言的可以跳过）, 第5.1节(一直到176页) |
| L11 |
PCP |
相关历史知识(176页)及5.2节 |
| R6 |
不可判定性 |
第4章 (到176页), 5.1节 (除了181-182页), 5.2节 |
| L12 |
计数器机器以及栈机器（Counter and Stack Machines） |
Hopcroft, John, Rajeev Motwani, and Jeffrey Ullman.等人所著的 自动机，语言，以及计算导论（Introduction to Automata Theory, Languages and Computation）. 2nd ed. Reading, MA: Addison Wesley, 2000, section 8.5. ISBN: 0201441241. |
| L13 |
可规约性 |
第5.3节 |
| R7 |
计数机器及栈机器, 可规约性, Rice定理 |
5.3节
上面提到的那本书 |
| L14 |
递归定理 |
6.1节 |
| L15 |
第二次测验 |
|
| R8 |
测验二讲解，可计算性总结 |
|
| 计算复杂性理论 |
| L16 |
时间复杂度 |
7.1和7.2节 |
| L17 |
非确定性时间复杂度 |
7.3节 |
| R9 |
P 和 NP |
7.1, 7.2, 7.3节 |
| L18 |
NP-完全理论 |
7.4节( 除了定理7.30外) |
| L19 |
库克列文定理（Cook-Levin Theorem） |
7.4 节(定理7.30) |
| R10 |
多项式时间归约 |
|
| L20 |
NP-完全性 II |
Section 7.5
7.5节
也可有选择的阅读: Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. 算法导论（Introduction to Algorithms）. Cambridge, MA: MIT Press, 1990, chapter 36.5. ISBN: 0262530910. |
| R11 |
NP-完全理论 |
7.5节 |
| L21 |
高级时间复杂度理论 |
9.1, 9.2节 |
| L22 |
第三次测验 |
|
| R12 |
第三次测验讲解，并结束时间复杂度 |
|
| L23 |
空间复杂度 |
8.4, 8.5以及8.6节 |
| L24 |
空间复杂度 II |
8.4, 8.5以及8.6节 |
| R13 |
空间复杂度 III |
8.4, 8.5以及8.6节 |
| L25 |
概率复杂度理论 |
10.2节 |
| L26 |
概率复杂性理论(续) |
10.2节 |
| R14 |
概率复杂性和交互式证明 |
10.4节（可选的） |
|
期末考试复习(可选) |
|
|
期末考试 |
|