本部分包含了习题课上的讨论资料以及在习题课上要求学生来解决的问题。
Recitation files.
| 课时 # |
主题 |
| R1 |
数学知识回顾 (PDF) |
| R2 |
DFA和NFA (PDF) |
| R3 |
正则表达式和非正则语言 (PDF) |
| R4 |
测验中的问题和自动机总结 (PDF) |
| R5 |
图灵机 (PDF) |
| R6 |
不可判定性 (PDF) |
| R7 |
计数机器和栈机器，规约性，Rice定理 (PDF) |
| R8 |
测验2讲解，可计算性总结 (PDF) |
| R9 |
P 和 NP (PDF) |
| R10 |
多项式时间规约 |
| R11 |
NP-完全性 (PDF) |
| R12 |
测验3讲解并结束时间复杂度的内容 |
| R13 |
空间复杂度 III(PDF) |
| R14 |
概率复杂性和交互式证明 |