下面的教学日程提供了该课程讲义，习题课以及考试的相关信息。
Course calendar.
| 课次 |
主题 |
重要日期 |
| 课程简介和基础知识回顾 |
| L1 |
课程简介 |
布置作业1 |
| R1 |
数学知识回顾 |
|
| 有限自动机，正则语言，正则表达式 |
| L2 |
确定有限自动机 (DFA) |
|
| L3 |
非确定有限自动机 (NFA) |
上交作业1
布置作业2 |
| R2 |
DFAs 和 NFAs |
|
| L4 |
正则表达式 |
|
| L5 |
非正则语言 |
上交作业2
布置练习作业2.5 |
| R3 |
正则表达式和非正则语言复习 |
|
| L6 |
自动机的算法 |
|
| L7 |
第1次测验 |
布置作业3 |
| R4 |
第一次测验讲解自动机复习 |
|
| 计算理论 |
| L8 |
图灵机 |
|
| L9 |
非确定图灵机 |
上交作业3
布置作业4 |
| R5 |
图灵机 |
|
| L10 |
不可判定性 |
|
| L11 |
PCP |
上交作业4
布置作业5 |
| R6 |
不可判定性 |
|
| L12 |
计数器机器以及栈机器 |
|
| L13 |
可规约性 |
上交作业5
布置练习作业5.5 |
| R7 |
计数机器及栈机器, 可规约性, Rice定理 |
|
| L14 |
递归定理 |
|
| L15 |
第二次测验 |
布置作业6 |
| R8 |
测验二讲解，可计算性总结 |
|
| 计算复杂性理论 |
| L16 |
时间复杂度 |
|
| L17 |
非确定性时间复杂度 |
上交作业6
布置作业7 |
| R9 |
P 和 NP |
|
| L18 |
NP-完全理论 |
|
| L19 |
库克列文定理（Cook-Levin Theorem） |
上交作业7
布置作业8 |
| R10 |
多项式时间归约 |
|
| L20 |
NP-完全性 II |
上交作业8
布置练习作业8.5 |
| R11 |
NP-完全理论 |
|
| L21 |
高级时间复杂度理论 |
|
| L22 |
第三次测验 |
布置作业9 |
| R12 |
第三次测验讲解，并结束时间复杂度 |
|
| L23 |
空间复杂度 |
|
| L24 |
空间复杂度 II |
上交作业9
布置练习作业10 |
| R13 |
空间复杂度 III |
|
| L25 |
概率复杂度理论 |
|
| L26 |
概率复杂性理论(续) |
布置练习作业10.5 |
| R14 |
概率复杂性和交互式证明 |
|
|
期末考试复习(可选) |
|
|
期末考试 |
|