• 投稿

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

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/计算理论课件/
教育
科学
语言
课程
大学
学习
考试
编程
漫暖的阳光 发消息
前端渣渣
视频选集
（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天！我做了一款《跳跳史莱姆》游戏！！
点击体验>>

web开发
漫暖的阳光
281 0

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

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

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

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

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

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

大学开放之后belike
半彩AI
288.1万 475

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

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

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

选词填空技巧教学
褚褚褚同学
3704 10

史上最崩溃的一次连麦，张雪峰也是说出大实话了
升学规划学习精选
2.0万 26

我是大一学生生活费2000，但是上大学后我开始虚荣，还借网贷超前消费，后来看了你视频把网贷还了，现在在攒钱，运动学习，保持积极态度
戒社
20.5万 190

【张宇】命运会反复考验你，直到拿出真正的礼物，各位，请务必坚持到底！
爱启航旗舰店
7259 0

清北率暴跌83%！衡水都扛不住的新高考，普通人怎么破局？
胡源高中数学选填速解
136.6万 307

AI时代，什么大学会被颠覆？
Becky在地球村
6422 12

27考研强化 -193题 | 本题归纳了判定单调性常用基本方法与理论
考研数学武忠祥老师
1.7万 32

图解法求理论塔板数
迷途知返o-o
2300 0

今日挑战：北大新生战地理
学霸来了XBLL
61.5万 1277
展开
决战动漫高手之巅！
客服
顶部
赛事库 课堂 2021拜年纪