视频选集
- P21-1 预备知识
- P31-2 确定型有穷自动机例子
- P41-3 确定型有穷自动机的形式化定义
- P51-4 设计确定型有穷自动机
- P61-5 正则运算与封闭性
- P71-6 非确定型有穷自动机
- P81-7 DFA与NFA的等价性
- P91-8 正则语言的封闭性
- P102-1 正则表达式及形式化定义
- P112-2 正则表达式与有穷自动机的等价性（1）
- P122-3 正则表达式与有穷自动机的等价性（2）
- P132-4 非正则语言
- P142-5 泵引理的证明
- P152-6 泵引理的应用
- P163-1 上下文无关文法的例子
- P173-2 上下文无关文法的定义
- P183-3 设计上下文无关文法
- P193-4 文法的歧义性
- P203-5 乔姆斯基范式
- P213-6 下推自动机的形式定义
- P223-7 下推自动机例子
- P234-1 PDA与CFG等价性
- P244-2 从CFG构造PDA的算法
- P254-3 从CFG构造PDA的例子
- P264-4 从PDA构造CFG的算法(上)
- P274-5 从PDA构造CFG的算法(下)
- P284-6 上下文无关语言的泵引理
- P294-7 应用泵引理的例子
- P305-1 单带图灵机的例子
- P315-2 单带图灵机的定义
- P325-3 图灵机判定语言的例子
- P335-4 图灵机的各种等价变形
- P345-5 枚举器与识别器
- P355-6 算法的定义
- P365-7 图灵机算法的描述
- P375-8 递归定理及其证明（自我复制）
- P385-9 递归定理的应用（通用机）
- P396-1 关于正则语言的可计算问题
- P406-2 关于上下文无关语言的可计算问题
- P416-3 不可计算的问题（计数法）
- P426-4 对角化方法
- P436-5 一个非图灵可识别语言
- P446-6 与图灵机有关的不可计算问题（归约的例子）
- P456-7 利用计算历史的归约
- P466-8 波斯特对应问题（还是归约的例子）
- P476-9 归约的定义、性质和用途
- P486-10 补充（Rice定理）和总结
- P497-1 函数的阶
- P507-2 时间复杂性、时间复杂性类
- P517-3 P类
- P527-4 NP类
- P537-5 coNP类、EXP类、 P与NP问题
- P547-6 空间复杂性、 空间复杂性类
- P557-7 萨维奇定理、PSPACE类
- P567-8 亚线性空间、 L类、NL类
- P577-9 NL=coNL
- P587-10 空间层次定理
- P597-11 时间层次定理
- P607-12 交错式复杂性类
- P617-13 多项式时间层次（PH类）
- P628-1 多项式时间归约
- P638-2 库克定理
- P648-3 NP完全与NP难
- P658-4 几个NP完全问题
- P668-5 PSPACE完全问题
- P678-6 对数空间归约、NL完全问题
- P688-7 图灵归约、相对化
- P698-8 电路、P完全问题
- P708-9 并行计算NC类