P10 课程介绍05:46
P21-1 预备知识07:43
P31-2 确定型有穷自动机例子11:23
P41-3 确定型有穷自动机的形式化定义17:51
P51-4 设计确定型有穷自动机05:57
P61-5 正则运算与封闭性28:16
P71-6 非确定型有穷自动机37:43
P81-7 DFA与NFA的等价性17:41
P91-8 正则语言的封闭性10:30
P102-1 正则表达式及形式化定义13:19
P112-2 正则表达式与有穷自动机的等价性（1）24:36
P122-3 正则表达式与有穷自动机的等价性（2）27:37
P132-4 非正则语言06:25
P142-5 泵引理的证明12:55
P152-6 泵引理的应用19:53
P163-1 上下文无关文法的例子09:46
P173-2 上下文无关文法的定义10:21
P183-3 设计上下文无关文法10:12
P193-4 文法的歧义性06:25
P203-5 乔姆斯基范式16:22
P213-6 下推自动机的形式定义09:06
P223-7 下推自动机例子15:11
P234-1 PDA与CFG等价性02:20
P244-2 从CFG构造PDA的算法21:08
P254-3 从CFG构造PDA的例子03:51
P264-4 从PDA构造CFG的算法(上)22:51
P274-5 从PDA构造CFG的算法(下)22:57
P284-6 上下文无关语言的泵引理19:22
P294-7 应用泵引理的例子19:04
P305-1 单带图灵机的例子13:48
P315-2 单带图灵机的定义13:39
P325-3 图灵机判定语言的例子21:56
P335-4 图灵机的各种等价变形21:47
P345-5 枚举器与识别器10:43
P355-6 算法的定义08:25
P365-7 图灵机算法的描述15:06
P375-8 递归定理及其证明（自我复制）19:31
P385-9 递归定理的应用（通用机）21:16
P396-1 关于正则语言的可计算问题19:45
P406-2 关于上下文无关语言的可计算问题09:02
P416-3 不可计算的问题（计数法）04:02
P426-4 对角化方法10:33
P436-5 一个非图灵可识别语言07:49
P446-6 与图灵机有关的不可计算问题（归约的例子）22:45
P456-7 利用计算历史的归约22:10
P466-8 波斯特对应问题（还是归约的例子）16:54
P476-9 归约的定义、性质和用途07:52
P486-10 补充（Rice定理）和总结02:44
P497-1 函数的阶07:56
P507-2 时间复杂性、时间复杂性类17:54
P517-3 P类08:56
P527-4 NP类25:13
P537-5 coNP类、EXP类、 P与NP问题05:17
P547-6 空间复杂性、 空间复杂性类08:36
P557-7 萨维奇定理、PSPACE类15:34
P567-8 亚线性空间、 L类、NL类12:29
P577-9 NL=coNL21:15
P587-10 空间层次定理18:55
P597-11 时间层次定理08:13
P607-12 交错式复杂性类12:43
P617-13 多项式时间层次（PH类）08:41
P628-1 多项式时间归约25:32
P638-2 库克定理19:03
P648-3 NP完全与NP难05:48
P658-4 几个NP完全问题35:27
P668-5 PSPACE完全问题26:20
P678-6 对数空间归约、NL完全问题06:50
P688-7 图灵归约、相对化25:17
P698-8 电路、P完全问题20:28
P708-9 并行计算NC类16:14
