2015唐常杰翻译的计算理论导引.ppt

四川大学计算机学院可计算理论 课程说明和教学计划（2006.2-7） 学分3 周学时 4 任课教师 唐常杰 时间 每周三 8:00-11:35 地点 研 3-301 教材 Material: Michael Sipser (MIT) [Required] Sipser, Michael, Introduction to the Theory of Computation. PWS Publishing Company, 1997. (Both first and second printing are okay. ISBN 0-619-21674-2) 中译本，计算理论导引(第二版), (美)Michael Sipser 著(麻省理工学院) 唐常杰 陈鹏 向勇 刘齐宏 译，机械工业出版社出版，２００６.7 ISBN 7-111-19028-9) [Additional] Lewis, Harry R., and Papadimitriou, Christos H., Elements of the Theory of Computation, 2nd ed. Prentice-Hall, 1997. 内容 Chapters 0 - 8.3 (up to the PSPACE-completeness of TQBF) 关于选择教材的体会 2001-2002 我们采用教材为： Lewis, Harry R., and Papadimitriou, Christos H., Elements of the Theory of Computation, 2nd ed. Prentice-Hall, 1997. 2003-2006 采用 Sipser, Michael, Introduction to the Theory of Computation. PWS Publishing Company, 1997. (Both first and second printing are okay.) 这两本书 是目前世界上主要大学采用最多的教材。 经验表明，如果学生数学基础好，用前者较好，如学生计算机基础好，用后者更受学生欢迎。 目前欧美大学中计算机专业 用后者的大学越来越多。网上赞誉甚多 电子教案下载 电子教案可在下面三个网址 下载： Http:// (机械工业出版社） 川大计算机学院： /~tangchangjie/teach/tang_teaching.htm 川大教师主页： /waim03/scu_cs/teach/tang_teching.htm 后两各地址 可能更新 及时一些。 本电子教案由机械工业出版社出版 请提改进意见 任课教师 ： 唐常杰 联系信息 四川大学计算机科学与技术系 主任。 博士生导师 中国计算机学会数据库专业委员会副主任 下载教案网址 机械工业出版社网址 或 下列网址 /~chjtang/teach/tang_teching.htm /~tangchangjie/teach/tang_teching.htm 联系email: tangchangjie@ 028-8546 6105 经验表明，教案年年改，年年都有需改处。 请提出改进意见。 可计算理论 课程说明和教学计划 ＰPT文件名称说明： 01_1d2_概念_自动机语ppt 可计算理论 课程说明和教学计划 教材详略处理 讲要点，前后次序有少数调整， 教学计划，大致16—18周 最后两章不讲或用讨论班形式讨论，有了基础，如果需要，已经能自学。 参考国内外同行（如Berkeley, MIT等）对这门课程教材的 处理经验，准备：? 略讲或自学的部分 ，要求了解主要思想 Section 2.2(中文3.2节）?: the proof that CFL = pushdown automata Section 5.1., linear bounded automata?????? Section 5.2?? Post correspondence problem 快讲的部分， 要求一般了解的章节，要求了解主要方法和演绎框架 Section 6.2 decidability of logical theories (Section 6.2), Section 6.3 Turing reducibility (), Chapter 8 space complexity (). 其余未列出的部分要求深入掌