北京大学“理论计算机科学基础”课程
转自https://courses.edx.org/courses/course-v1:PekingX+04830260x+3T2015/course/
Introduction to Theoretical Computer Science 理论计算机科学基础
北京大学“理论计算机科学基础”课程！
本视频的ppt:https://mannuan.github.io/计算理论课件/
视频选集
（1/69）
1-1 预备知识
07:43
1-2 确定型有穷自动机例子
11:23
1-3 确定型有穷自动机的形式化定义
17:50
1-4 设计确定型有穷自动机
05:56
1-5 正则运算与封闭性
28:16
1-6 非确定型有穷自动机
37:42
1-7 DFA与NFA的等价性
17:41
1-8 正则语言的封闭性
10:29
2-1 正则表达式及形式化定义
13:18
2-2 正则表达式与有穷自动机的等价性（1）
24:35
2-3 正则表达式与有穷自动机的等价性（2）
27:36
2-4 非正则语言
06:25
2-5 泵引理的证明
12:55
2-6 泵引理的应用
19:53
3-1 上下文无关文法的例子
09:45
3-2 上下文无关文法的定义
10:21
3-3 设计上下文无关文法
10:11
3-4 文法的歧义性
06:24
3-5 乔姆斯基范式
16:22
3-6 下推自动机的形式定义
09:21
3-7 下推自动机例子
15:10
4-1 PDA与CFG等价性
02:19
4-2 从CFG构造PDA的算法
21:08
4-3 从CFG构造PDA的例子
03:50
4-4 从PDA构造CFG的算法(上)
22:51
4-5 从PDA构造CFG的算法(下)
22:56
4-6 上下文无关语言的泵引理
19:21
4-7 应用泵引理的例子
19:03
5-1 单带图灵机的例子
13:48
5-2 单带图灵机的定义
13:39
5-3 图灵机判定语言的例子
21:55
5-4 图灵机的各种等价变形
21:46
5-5 枚举器与识别器
10:42
5-6 算法的定义
08:24
5-7 图灵机算法的描述
15:05
5-8 递归定理及其证明（自我复制）
19:30
5-9 递归定理的应用（通用机）
21:18
6-1 关于正则语言的可计算问题
19:44
6-2 关于上下文无关语言的可计算问题
09:01
6-3 不可计算的问题（计数法）
04:01
6-4 对角化方法
10:33
6-5 一个非图灵可识别语言
07:48
6-6 与图灵机有关的不可计算问题（归约的例子）
22:44
6-7 利用计算历史的归约
22:10
6-8 波斯特对应问题（还是归约的例子）
16:53
6-9 归约的定义、性质和用途
07:52
6-10 补充（Rice定理）和总结
02:44
7-1 函数的阶
07:56
7-2 时间复杂性、时间复杂性类
17:53
7-3 P类
08:56
7-4 NP类
25:13
7-5 coNP类、EXP类、 P与NP问题
05:16
7-6 空间复杂性、 空间复杂性类
08:35
7-7 萨维奇定理、PSPACE类
15:33
7-8 亚线性空间、 L类、NL类
12:28
7-9 NL=coNL
21:15
7-10 空间层次定理
18:55
7-11 时间层次定理
08:13
7-12 交错式复杂性类
12:43
7-13 多项式时间层次（PH类）
08:40
8-1 多项式时间归约
25:31
8-2 库克定理
19:02
8-3 NP完全与NP难
05:47
8-4 几个NP完全问题
35:27
8-5 PSPACE完全问题
26:20
8-6 对数空间归约、NL完全问题
06:49
8-7 图灵归约、相对化
25:17
8-8 电路、P完全问题
20:28
8-9 并行计算NC类
16:14
直击2026诺贝尔奖>>
专家&UP主独家解读，上B站看懂诺贝尔奖！
顶部