投稿

【北京大学】理论计算机科学基础（全70讲）

27.5万

3482

2019-05-27 19:26:04

https://study.163.com/ 北京大学理论计算机科学基础全70讲主讲老师：刘田

计算机科学

账号已注销发消息

AMD千帧整机芯更强价更香！

3万人感兴趣

0 课程介绍

05:46

1-1 预备知识

07:43

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

11:23

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

17:51

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

05:57

1-5 正则运算与封闭性

28:16

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

37:43

1-7 DFA与NFA的等价性

17:41

1-8 正则语言的封闭性

10:30

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

13:19

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

24:36

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

27:37

2-4 非正则语言

06:25

2-5 泵引理的证明

12:55

2-6 泵引理的应用

19:53

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

09:46

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

10:21

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

10:12

3-4 文法的歧义性

06:25

3-5 乔姆斯基范式

16:22

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

09:06

3-7 下推自动机例子

15:11

4-1 PDA与CFG等价性

02:20

4-2 从CFG构造PDA的算法

21:08

4-3 从CFG构造PDA的例子

03:51

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

22:51

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

22:57

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

19:22

4-7 应用泵引理的例子

19:04

5-1 单带图灵机的例子

13:48

5-2 单带图灵机的定义

13:39

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

21:56

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

21:47

5-5 枚举器与识别器

10:43

5-6 算法的定义

08:25

5-7 图灵机算法的描述

15:06

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

19:31

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

21:16

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

19:45

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

09:02

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

04:02

6-4 对角化方法

10:33

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

07:49

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

22:45

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

22:10

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

16:54

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

07:52

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

02:44

7-1 函数的阶

07:56

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

17:54

7-3 P类

08:56

7-4 NP类

25:13

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

05:17

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

08:36

7-7 萨维奇定理、PSPACE类

15:34

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

12:29

7-9 NL=coNL

21:15

7-10 空间层次定理

18:55

7-11 时间层次定理

08:13

7-12 交错式复杂性类

12:43

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

08:41

8-1 多项式时间归约

25:32

8-2 库克定理

19:03

8-3 NP完全与NP难

05:48

8-4 几个NP完全问题

35:27

8-5 PSPACE完全问题

26:20

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

06:50

8-7 图灵归约、相对化

25:17

8-8 电路、P完全问题

20:28

8-9 并行计算NC类

16:14

顶部