投稿

北京大学“理论计算机科学基础”课程

4.0万

525

2017-12-14 17:09:50

转自https://courses.edx.org/courses/course-v1:PekingX+04830260x+3T2015/course/ Introduction to Theoretical Computer Science 理论计算机科学基础北京大学“理论计算机科学基础”课程！本视频的ppt:https://mannuan.github.io/计算理论课件/

漫暖的阳光发消息

前端渣渣

电脑里住了个 AI 打工人，一句话丢任务给阶跃 AI，真能替你干完

3000+人感兴趣

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

顶部