可计算理论是门修养课-研教散记11 （唐常杰）

    说明：十年前，开始学讲“可计算理论”这门课程，五年前和博士生一起开始翻译<<计算理论导引(第二版)>>。初讲时的生涩，仿佛还在昨天；弹指之间，两个五年计划就过去了。本想暗地自省十年得失，恰有署名fans的博友来邮件，希望看到新的、特别是和计算机专业相关的博文。明白这是对发文太少太慢的温馨敦促。无奈期末有两个课程考试阅卷，两个项目中期检查，事情太多；只好用五年前为计算理论导引写的译者序略加删改应急,试图以一举而应两求。    

    几年前为计算理论课程选择教材时，海外友人介绍了眼前这本“由MIT的名师Michael Sipser写的名著 Introduction to the Theory of Computation. PWS Publishing Company”。几年教学实践表明，此书前三章可供高年级本科生选修，后七章足够研究生钻研，是同类教材中，我教得最愉悦，学生学起来最有兴趣的一本教科书。

    可计算理论课程是计算机学人的修养课、内功课。很难断言某章某节能够立竿见影地用于读者的某项科研。我的学生（攻读数据库、数据挖掘和知识工程方向）学习此课一两年后，以过来人身份发出感慨，这门课使他们思路开阔、思维严密、观点提高、点子增多，从而终身受益。在他们的工程性论文中也不时出现关于可计算性和复杂度方面的亮点，提高了论文的深度和质量。

    1979年初入此门时，读过Ｊ.D.Ullman和J.E.Hopcroft的书以及S.Eilenberg的名著“语言，自动机和机器”，在S.Ginsburg门下研究数据库理论时，学过他的大师之作《前后文无关语言理论》。教学中也用过H. R. Lewis的《计算理论基础》。上述书籍都是好书，但对于非纯理论方向的初学者，还是觉得Michael Sipser的这本书更为合适。

    此书以注重思路、宽奠基础、深入引导为特色。全书勾画了理论计算机科学的知识框架，囊括了形式语言、自动机、图灵机、可计算性和计算复杂度等重要主题，试图为读者的计算机生涯奠定一个宽广坚实的理论基础。作者强调思想方法，难点均以思路先行；介绍背景如远山淡抹，化繁为简似近水浓描；释难以例，不拘泥于技术细节，铺垫伏笔，常迸发在数章之后。这些亮点表现了作者对问题的深刻理解和娴熟的教学艺术。每一主题的后部，给出精彩结果以作启发，展示待解问题以设悬念，引导读者向此领域中的高层次问题攀登。全书文笔流畅，读来亲切，开卷读之概念易懂，合书思之脉络不忘。

    在同类书被采用列表中，此书已列前茅。2005年12月，在Google中以作者名和书名搜索到相关项目8,420项。在http://www.amazon.com /gp/ product/ customer-reviews中有许多读者评论，称此书“best”，“one of the best” 的赞口不绝，也有人批评此书第一版无习题解答。所幸，第二版已弥补这一不足。新版修正了若干印刷错误，字句更加流畅，增加了部分内容、部分启发性习题、部分难题解答和教师教学辅助材料。一些重要内容，如Myhill-Nerode 定理和Rice 定理放到了专门的小节。…….

    此书依据英文第二版原文翻译。翻译团队成员在几年前读过由北京大学张立昂教授、王捍贫教授和王雄老师合作翻译的第一版，翻译中不可避免地受到他们准确的词汇，流畅的文风影响。在此意义上，新版译者不过是接过了先行者的接力棒，再把接力赛推进了一程。借此机会，对三位先行者表示衷心的感谢。

    在多年的教学实践中，积累了1600页PPT双语电子教案，一直放在出版社和个人网页上自由下载，奉献给我国的读者。

参见出版社主页http://www.hzbook.com/Books/2936.html或http://teacher.scu.edu.cn/~chjtang/teach/computation/ComputationCourceNotes.htm

  其它系列博文的入口      唐常杰博客主页       科学博客主页