Automata

开始时间: 04/22/2022 持续时间: 6 weeks

所在平台: CourseraArchive

课程类别: 计算机科学

大学或机构: Stanford University(斯坦福大学)

授课老师: Jeff Ullman

课程主页: https://www.coursera.org/course/automata

课程评论: 3 个评论

评论课程        关注课程

课程简介

This course covers finite automata, context-free grammars, Turing machines, undecidable problems, and intractable problems (NP-completeness).

课程评论(3条)

1

超級現實的超現實理想主義者 2014-01-08 19:30 1 票支持; 0 票反对

轮次:
Nov 4th 2013

背景:
这门课程的背景其实不是太多,主要都是证明题,如果熟悉数学归纳法基本上就没太大问题了。当然,一个良好的心态还是有必要的(听过这门课就明白了)。

内容:
内容其实就是计算理论,前半部分有很多和编译器的课程有一定的重合,后半部分主要讲图灵机以及P和NP。说实话这门课我听到一半就已经是在听不下去了,一方面是因为老爷子年事已高,可能英语习惯属于老一代的传统,所以即便我明白他说的每一个字也不一定理解他到底想要表达什么,另一方面,老爷子讲课的方式实在太跳跃了,几乎每一句话都压缩了相当多的信息量(也可能是因为内功太深厚,一般人难以消化,毕竟是大师...)既然课听不下去那就看教材吧,但买了国内影印的教材也是看得挺郁闷。

怎么办呢?毕竟这门课的证书非常有收藏价值,过了这个村可能就没这个店了,咬咬牙吧。于是做了一番调研,终于找到合适的资料了:这个领域有一本书很有名,是MIT的Introduction to the Theory of Computation,美国亚马逊上的评价比Jeffrey Ullman的Automata Theory要高,绝大部分学校教授计算理论用的就是这本教材,包括斯坦福(CS154),国内就有影印版。而且还在Youtube上找到了UC Davis – Theory of Computation(相当于MIT那本教材的配套视频课程),讲的非常棒,很Intuitive,据说UC Davis这门课的讲师和MIT那本教材的作者还有很密切的私人关系。总之,这两个资料帮了我很大的忙。如果你也和我一样不喜欢Jeffrey Ullman这样劈头盖脸都是干巴巴的证明的话,可以选择我说的资料。视频已经从Youtube上抓下来上传我的网盘了,课程图谱的博客也有整理:公开课可下载资源汇总

练习:
作业有两种,一个是选择题,另一个是编程题(两题PA,但仅占总分很小的比例,几乎可以认为是Optional)虽然其中选择题每周都有100次机会,但是因为每次题目都会变动,想要单纯依靠Rapid-Fire Guessing拿满分估计有难度,而且大部分题目徒手做估计要累死,不过这对于这门课有一个神器:杜克大学研发的软件JFLAP。因为是网络课程的缘故,很难考察证明题,所以很多题目都是构造自动机,于是JFLAP就成了解题神器(包括Final Exam)

社区:
其实没怎么太融入这门课的社区,不过讲师和助教确实非常敬业,常常会和学员互动(之前无意中在微博上看到有人因为Ullam回复他的留言而表达兴奋之情)

总结:
据说这门课一年以后(2014年底)会重新再开一轮,希望我的这些经验能够提供一些帮助。
前几天读到王垠的博文《我和权威的故事》忍不住要在这篇课程评论里分享一下: http://www.yinwang.org/blog-cn/2014/01/04/authority

0

要有光LTBL 2014-01-08 09:51 0 票支持; 0 票反对

老师似乎很牛逼,语速略快了点。
内容因为compiler接触过一点点所以前三周基本不难,NP也学过所以全新的内容就是PDA和Turing Machine那些了,当然还有language的特性啥的。。。
最后office hour讲如果你发明了P=NP的算法的话该如何利用,很好玩哈哈

1

课程图谱 2013-06-18 08:49 1 票支持; 0 票反对

课程图谱群里 @超級現實的超現實理想主義者 同学八卦了一下这门课程的老师:这位老师名叫jeffery ullman,几乎CS领域所有重要教科书都有他的身影;他是数据库专家,那本大数据(Mining of Massive Datasets)他是作者之一;龙书也是他参与写的; 他也是谷歌创始人布林的导师。

CSDN上有篇博文"一些牛人榜样,多看看他们写的东西",其中是这样介绍的计算机大师Jeffrey D. Ullman的:

数据库理论、自动机理论、编译原理大师。他的《Automata Theory, Languages, and Computation》让我真正的进入了计算机基础理论的世界。《Compilers: Principles, Techniques, and Tools 》让编译器不再神奇,让我也能写出自己的编译器。《A First Course in Database Systems》让我对数据库的了解从应用进入了理论的深度,可以说Ullman是我在计算机理论方面的启蒙老师,他的书教给了我计算机世界最奇妙最基础最有趣的东西。

课程详情

This course covers finite automata, context-free grammars, Turing machines, undecidable problems, and intractable problems (NP-completeness).

课程标签

自动机 有限状态自动机 正则表达式 上下文无关文法 图灵机 NP-complete Ullman automata automaton COMPUTATION FSM finite state turing自动机 计算理论 Turing JFLAP P=NP 斯坦福大学

110人关注该课程

主题相关的课程

Computational Investing, Part I 关注

Introduction to Mathematical Thinking 关注

关注

An Introduction to Financial Accounting 关注

Human-Computer Interaction 关注

English Composition I: Achieving Expertise 关注

Computer Science 101 关注

Internet History, Technology, and Security 关注

Neural Networks for Machine Learning 关注

VLSI CAD: Logic to Layout 关注