• 投稿

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

4.0万
525
2017-12-14 17:09:50
347
169
1486
238
转自https://courses.edx.org/courses/course-v1:PekingX+04830260x+3T2015/course/ Introduction to Theoretical Computer Science 理论计算机科学基础 北京大学“理论计算机科学基础”课程！ 本视频的ppt:https://mannuan.github.io/计算理论课件/
考试
大学
学习
科学
教育
课程
语言
编程
漫暖的阳光 发消息
前端渣渣
能劝一个是一个!这法子去指甲厚黄巨牛
24岁美艳小姨
视频选集
（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

爆肝30天！我做了一款《跳跳史莱姆》游戏！！
点击体验>>

当语文考试只剩下10分钟时：
-超级无敌铁金刚-
11.4万 28

大学开放之后belike
半彩AI
288.2万 476

大学对外开放后的神人belike
不懂爱的喵miao
124.6万 66

小孩现在学习实在太累了？张雪峰：说这话的人脑子有问题！
升学规划知识精选
17.8万 728

揪心！兰州大学人都跑没了！
华晔老师
17.5万 126

北京科技大学插座事件#ghg
卢冲天是也
70.0万 77

大学生毕业出路实力排行
何英东一号
17.7万 208

各科成绩
你的珑仔
38.2万 172

web开发
漫暖的阳光
282 0

百发百中自动进球的足球！
超核世界
1.0万 0

【高考志愿填报】张雪峰的话再次正中眉心，文科专业都是混子专业
张雪峰助考助研
10.8万 87

高考加油！哈工大向你发出邀请，共赴星河之约！
哈尔滨工业大学
4941 7

大学对外开放后的某些神人belike
风的AI日记
249.5万 309

2026年电工证考试三级（高级）、四级（中级）理论知识精讲班，有完整版视频
毕过星
7025 1

华南理工大学2026版英文宣传片上线！Welcome to SCUT！
华南理工大学
6679 9

今日挑战：北大新生战地理
学霸来了XBLL
61.6万 1281

寝室里把谁都当假想敌的姐
刘参谋疯狂学长
34.5万 0

偏微分方程可视化，看见世界运行的底层数学。
科普宇宙1
17.9万 29

拿到这种题目你会着急的算下去吗？ 别急，让我带你看清题目的真面目，下次再碰到类似题目一招就能搞定
边rap边教学
12.8万 53

【张宇】命运会反复考验你，直到拿出真正的礼物，各位，请务必坚持到底！
爱启航旗舰店
7319 0
展开
上B站看播客，邂逅同频共振！
客服
顶部
赛事库 课堂 2021拜年纪