Automata

 所在平台: CourseraArchive 课程类别: 计算机科学 授课老师： Jeff Ullman

课程详情

I am pleased to be able to offer free over the Internet a course on Automata Theory, based on the material I have taught periodically at Stanford in the course CS154. Students have access to screencast lecture videos, are given quiz questions, assignments and exams, receive regular feedback on progress, and can participate in a discussion forum. Those who successfully complete the course will receive a statement of accomplishment. You will need a decent Internet connection for accessing course materials, but should be able to watch the videos on your smartphone.

The course covers four broad areas: (1) Finite automata and regular expressions, (2) Context-free grammars, (3) Turing machines and decidability, and (4) the theory of intractability, or NP-complete problems.

Why Study Automata Theory?

This subject is not just for those planning to enter the field of complexity theory, although it is a good place to start if that is your goal. Rather, the course will emphasize those aspects of the theory that people really use in practice. Finite automata, regular expressions, and context-free grammars are ideas that have stood the test of time. They are essential tools for compilers. But more importantly, they are used in many systems that require input that is less general than a full programming language yet more complex than "push this button."

The concepts of undecidable problems and intractable problems serve a different purpose. Undecidable problems are those for which no computer solution can ever exist, while intractable problems are those for which there is strong evidence that, although they can be solved by a computer, they cannot be solved sufficiently fast that the solution is truly useful in practice. Understanding this theory, and in particular being able to prove that a problem you are facing belongs to one of these classes, allows you to justify taking another approach — simplifying the problem or writing code to approximate the solution, for example.

During the course, I'm going to prove a number of things. The purpose of these proofs is not to torture you or confuse you. Neither are the proofs there because I doubt you would believe me were I merely to state some well-known fact. Rather, understanding how these proofs, especially inductive proofs, work, lets you think more clearly about your own work. I do not advocate proofs that programs are correct, but whenever you attempt something a bit complex, it is good to have in mind the inductive proofs that would be needed to guarantee that what you are doing really works in all cases.

课程评论(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).