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是我在计算机理论方面的启蒙老师，他的书教给了我计算机世界最奇妙最基础最有趣的东西。