Code Sea

这学期让我最怨念痛苦的课就是《计算理论》了，本来我读研的初衷就是在TL里面浸淫了许久感觉到自己做为SE的学生在CS这门学科里面基础知识十分的匮乏，读了研就有一些时间补充基础，提高能力。而看到选课单的时候发现有“计算理论”这门课，我不是特别了解这个课程，只是大概知道与自动机有关。接触自动机是在大三的编译原理课上，觉得编译器是一个很神秘很powerful的“机器”，而且计算理论一听这名字就与计算机的基础似乎有着或多或少的联系，所以还是很期待的。可是……上了课之后真是觉得大失所望，一名口齿特别不清的老师，第二次课我坐在第一排，听着他讲了1个半小时，仍然有些不知所云，而且虽然他的PPT做的还是不错的，具体而不过于详细，可是他的讲课方式让人昏昏欲睡，从此我就失去了听他上课的兴趣。而考试需要复习的资料何其多，让我更加厌烦，都有种考好试就把这本借来为了复习的教材还掉的冲动。可是在复习的时候，还是感受到了这本书的价值的，而且后面的P与NP又是我在学习算法的时候很想了解一下的东西，于是就打算在回家前把它阅读完。下面来说说这本书 本书名为Introduction to Theory of Computation，顾名思义应该是一本普及入计算理论门的书籍，作者Michael Sipser，乃著名的麻省理工大学应用数学系计算理论小组的教授。全书分为三部分，涵盖了计算理论的三个方面——自动机，可计算性，复杂性，深入浅出，语言明快轻松，确实是了解计算理论的一本好教材。对于每一个引理、定理、推论，作者均会事先以非正式的语言描述证明的思路，然后再以正式的数学语言对其进行证明，这样可以更好的帮助读者了解证明的思路而不是一开始就给出证明方法令读者丈二和尚摸不着头脑。本书共11章： 第0章，介绍了计算理论的三个方向，给出了简要的数学知识 第1、2章介绍了自动机和语言，包括了正则语言类——有限自动机（确定型和非确定型），上下文无关语言类——下推有限自动机（重点叙述非确定型） 第3、4、5、6章介绍了可计算性理论。第3章承上启下，先是介绍了图灵可识别语言类——图灵机，并且简单介绍了图灵机的变种和其与标准单带图灵机的等价性及其证明。然后介绍了确定性、可约性，第6章介绍了可计算理论中的高级主题。 第7、8、9、10章介绍了复杂性理论，包括了时间复杂度、空间复杂度、难解性和复杂性理论中的高级主题。 因为考试，所以我特别认真的阅读了0~3章，然后自己阅读了4、5、7章，第6章看的有点晕头晕脑且该章相对于全书来说比较独立，跳过不会影响到其他知识的阅读，所以我选择了跳过，而后面四章与算法的设计和分析较为相关，本来我是计划阅读全部4章，后来因为放假了心有点散了，又想在回家前把书还掉，于是就没有继续阅读了。 这本书的优点前面已经说过了，缺点就是有些概念已经比较过时，比如下推自动机和图灵机的定义，就与孙另外推荐的一本参考书：Introduction to Automata Theory, Languages, and Computation (3rd Edition) 和wiki上面的定义有些差别，但是不妨碍这本书成为一本经典的计算理论入门书。