北京大学《理论计算机科学基础》刘田视频教程

0 课程介绍

1-1 预备知识

1-2 确定型有穷自动机例子

1-3 确定型有穷自动机的形式化定义

1-4 设计确定型有穷自动机

1-5 正则运算与封闭性

1-6 非确定型有穷自动机

1-7 DFA与NFA的等价性

1-8 正则语言的封闭性

2-1 正则表达式及形式化定义

2-2 正则表达式与有穷自动机的等价性（1）

2-3 正则表达式与有穷自动机的等价性（2）

2-4 非正则语言

2-5 泵引理的证明

2-6 泵引理的应用

3-1 上下文无关文法的例子

3-2 上下文无关文法的定义

3-3 设计上下文无关文法

3-4 文法的歧义性

3-5 乔姆斯基范式

3-6 下推自动机的形式定义

3-7 下推自动机例子

4-1 PDA与CFG等价性

4-2 从CFG构造PDA的算法

4-3 从CFG构造PDA的例子

4-4 从PDA构造CFG的算法(上)

4-5 从PDA构造CFG的算法(下)

4-6 上下文无关语言的泵引理

4-7 应用泵引理的例子

5-1 单带图灵机的例子

5-2 单带图灵机的定义

5-3 图灵机判定语言的例子

5-4 图灵机的各种等价变形

5-5 枚举器与识别器

5-6 算法的定义

5-7 图灵机算法的描述

5-8 递归定理及其证明（自我复制）

5-9 递归定理的应用（通用机）

6-1 关于正则语言的可计算问题

6-2 关于上下文无关语言的可计算问题

6-3 不可计算的问题（计数法）

6-4 对角化方法

6-5 一个非图灵可识别语言

6-6 与图灵机有关的不可计算问题（归约的例子）

6-7 利用计算历史的归约

6-8 波斯特对应问题（还是归约的例子）

6-9 归约的定义、性质和用途

6-10 补充（Rice定理）和总结

7-1 函数的阶

7-2 时间复杂性、时间复杂性类

7-3 P类

7-4 NP类

7-5 coNP类、EXP类、 P与NP问题

7-6 空间复杂性、 空间复杂性类

7-7 萨维奇定理、PSPACE类

7-8 亚线性空间、 L类、NL类

7-9 NL=coNL

7-10 空间层次定理

7-11 时间层次定理

7-12 交错式复杂性类

7-13 多项式时间层次（PH类）

8-1 多项式时间归约

8-2 库克定理

8-3 NP完全与NP难

8-4 几个NP完全问题

8-5 PSPACE完全问题

8-6 对数空间归约、NL完全问题

8-7 图灵归约、相对化

8-8 电路、P完全问题

8-9 并行计算NC类