CS_Dept.Sichaun Univ.可计算理论四川大学计算机学院 可计算理论 课程说明和教学计划（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 著(麻省理工学院) 唐常杰 陈鹏 向勇 刘齐宏 译，机械工业出版社出版，.7ISBN 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) Date1CS_Dept.Sichaun Univ.可计算理论关于选择教材的体会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.)这两本书 是目前世界上主要大学采用最多的教材。经验表明，如果学生数学基础好，用前者较好，如学生计算机 基础好，用后者更受学生欢迎。目前欧美大学中计算机专业 用后者的大学越来越多。网上赞誉 甚多Date2CS_Dept.Sichaun Univ.可计算理论电子教案下载n电子教案可在下面三个网址 下载：nHttp:/www.hzbook.com (机械工业出版社）n川大计算机学院：nhttp:/cs.scu.edu.cn/tangchangjie/teach/tang_teaching.htm n川大教师主页：nhttp:/www.scu.edu.cn/waim03/scu_cs/teach/tang_teching.htm n后两各地址 可能更新 及时一些。Date3CS_Dept.Sichaun Univ.可计算理论本电子教案由机械工业出版社出版Date4CS_Dept.Sichaun Univ.可计算理论请提改进意见任课教师 ： 唐常杰联系信息 四川大学计算机科学与技术系 主任。 博士生导师 中国计算机学会数据库专业委员会副主任 下载教案网址 机械工业出版社网址 或 下列网址http:/teacher.scu.edu.cn/cang/teach/tang_teching.htmhttp:/211.83.120.2/tangchangjie/teach/tang_teching.htm 联系email: tangchangjiecs.scu.edu.cn 028-8546 6105经验表明，教案年年改，年年都有需改处。请提出改进意见。Date5CS_Dept.Sichaun Univ.可计算理论可计算理论 课程说明和教学计划PT文件名称说明： 01_1d2_概念_自动机语言06021220.ppt第一周 ，1.2节开始主要内容最后修改 时间Date6CS_Dept.Sichaun Univ.可计算理论可计算理论 课程说明和教学计划n 教材详略处理 H讲要点，前后次序有少数调整， H教学计划，大致1618周 最后两章不讲或用讨论班形式讨论，有了基础， 如果需要，已经能自学。 n参考国内外同行（如Berkeley, MIT等）对这门课程教材的 处理经验，准备： n略讲或自学的部分 ，要求了解主要思想 HSection 2.2(中文3.2节） : the proof that CFL = pushdown automata HSection 5.1., linear bounded automata HSection 5.2 Post correspondence problem n快讲的部分， 要求一般了解的章节，要求了解主要方法和演绎框架 HSection 6.2 decidability of logical theories (Section 6.2), HSection 6.3 Turing reducibility (), HChapter 8 space complexity ().n其余未列出的部分要求深入掌握（能作题目 或作难题，通过考试）Date7CS_Dept.Sichaun Univ.可计算理论可计算理论 课程说明和教学计划n 考查方式(暂定):n30% - Homework (one will be dropped) n20% - Midterm n50% - Final Date8CS_Dept.Sichaun Univ.可计算理论可计算理论 课程说明和教学计划nHomework : 参见 ”作业.PPT”n要求用一个比较好的本子（如硬面，B5以上），作布置和自 选题目，记录研究与思考，作业本在检查后归还，作为学生 自己的永久的纪念（上课时参见示范实例）。（亦可能复印 部分）n作业 参见 http:/cs.scu.edu.cn/tangchangjie/tang_teching.htmnLecture Slides / Tentative Schedule n草案，将在实施中调整进度，遇节假日，运动会，重要会议 则顺延,n在每次课前1-2周发布最后修改的PPT，可按PPT 预习）Date9CS_Dept.Sichaun Univ.可计算理论可计算理论目录Lecture Slides / Tentative Schedule （草案）将在实施中调整进度,每次课程结束时预报下两次进度在每次课前1-2周发布相应的电子教案最后修改版本遇节假日，运动会，重要会议 则顺延）参见 http:/cs.scu.edu.cn/tangchangjie/tang_teching.ht mDate10CS_Dept.Sichaun Univ.可计算理论可计算理论目录Lecture Slides / Tentative Schedule 草案，将在实施中调整进度，遇节假日，运动会，重要会议 则顺延,在每次课前1-2周发布最后修改的PDF， 下载和阅读 iamscucsphd 可按PDF 预习）1周 Chapter 0: Introduction, mathematical notation, proof techniques Chapter 1: Deterministic finite automata (DFA), nondeterministic finite automata (NFA), 84 pages 2周 Chapter 1:DFA=NFA, regular expression (RE), 46 pages 2周 Chapter 1: RE=NFA, nonregular languages/RE pumping lemma 39 page 3周Chapter 2: Context-free grammars (CFG), Chomsky normal form, all RL are CFG 59 pages4周Chapte r 2: Pushdown automata (PDA), Non-CF languages/CFL pumpin lemma 73 pagesDate11CS_Dept.Sichaun Univ.可计算理论可计算理论目录5周 51 pagesChapter 3: Turing machines (TMs), TM decidable languages, TM recognizable languages, Equivalence between multitape TMs Chapter 4: Equivalence between nondeterministic TMs and other models, Church-Turing thesis, Decidable languages, decidability RL/PDAs/RE 6 周 Chapter 4: Decidability CFLs/CFGs, Halting problem, counting/diagonalization, Chapter 4: Undecidability of the Halting problem, TM unrecognizable languages 52pages 6 周 Chapter 5: Computation histories, examples of undecidable languages Chapter 5: TM computable functions, mapping reducibility 50pages 7 周 Chapters 0-5: Review session 66 pages 8 周 专题讨论补充材料 半期考试 Date12CS_Dept.Sichaun Univ.可计算理论可计算理论目录8 周 Chapter 6: Recursion theorem, undecidability by self- reference, undecidability of mathematical theories 45 pages 10 周 Chapter 6 + handout: Kolmogorov complexity/minimal length descriptions, randomness, arguments by incompressibility 69 pages 11 周 Chapter 7: Time-complexity, polynomial time (P), languages in P, Strong Church-Turing thesis Chapter 7: Nondeterministic polynomial time (NP), SAT 47 12周 Chapter 7: Polynomial time reductions, NP- completeness, 3SAT versus CLIQUE, Cook-Levin Theorem Date13CS_Dept.Sichaun Univ.可计算理论可计算理论目录13 , NP-completeness of SAT and 3SAT, proving NP- completeness . 14 周 Chapter 7: