唐常杰翻译的计算理论导引02

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,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),中译本，,计算理论导引(第二版),唐常杰 陈鹏 向勇 刘齐宏 译，机械工业出版社出版，.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),9/20/2024,1,关于选择教材的体会,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.),这两本书 是目前世界上主要大学采用最多的教材。,经验表明，如果学生数学基础好，用前者较好，如学生计算机基础好，用后者更受学生欢迎。,目前欧美大学中计算机专业 用后者的大学越来越多。网上赞誉甚多,9/20/2024,2,电子教案下载,电子教案可在下面三个网址 下载：,(机械工业出版社,）,川大计算机学院,：,川大教师主页,：,后两各地址 可能更新 及时一些。,9/20/2024,3,本电子教案由机械工业出版社出版,9/20/2024,4,请提改进意见,任课教师,： 唐常杰,联系信息,四川大学计算机科学与技术系 主任。 博士生导师,中国计算机学会数据库专业委员会副主任,下载教案网址 机械工业出版社网址 或 下列网址,联系email:,028-8546 6105,经验表明，教案年年改，年年都有需改处。,请提出改进意见。,9/20/2024,5,可计算理论 课程说明和教学计划,PT文件名称说明：,01_1d2_概念_自动机语言06021220.ppt,第一周 ，,1.2,节开始,主要内容,最后修改时间,9/20/2024,6,可计算理论 课程说明和教学计划,教材详略处理,讲要点，前后次序有少数调整，,教学计划，大致1618周 最后两章不讲或用讨论班形式讨论，有了基础，如果需要，已经能自学。,参考国内外同行（如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 ().,其余未列出的部分要求深入掌握（能作题目 或作难题，通过考试）,9/20/2024,7,可计算理论 课程说明和教学计划,考查方式(暂定):,30% - Homework (one will be dropped),20% - Midterm,50% - Final,9/20/2024,8,可计算理论 课程说明和教学计划,Homework : 参见 ”作业.PPT”,要求用一个比较好的本子（如硬面，B5以上），作布置和自选题目，记录研究与思考，作业本在检查后归还，作为学生自己的永久的纪念（上课时参见示范实例）。（亦可能复印部分）,作业 参见,Lecture Slides / Tentative Schedule,草案，将在实施中调整进度，遇节假日，运动会，重要会议 则顺延,在每次课前1-2周发布最后修改的PPT，可按PPT 预习）,9/20/2024,9,可计算理论目录,Lecture Slides / Tentative Schedule,（草案）,将在实施中调整进度,每次课程结束时预报下两次进度,在每次课前1-2周发布相应的电子教案最后修改版本,遇节假日，运动会，重要会议 则顺延）,参见,http,:/ 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 pages,4周Chapte r 2: Pushdown automata (PDA), Non-CF languages/CFL pumpin lemma 73 pages,9/20/2024,11,可计算理论目录,5,周 51 pages,Chapter 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 周 专题讨论补充材料 半期考试,9/20/2024,12,可计算理论目录,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,9/20/2024,13,可计算理论目录,13 , NP-completeness of SAT and 3SAT, proving NP- completeness,.,14 周 Chapter 7: NP-completeness of HAMPATH, SUBSET SUM,Chapter 8: Space complexity, Savitchs theorem, PSPACE, PSPACE completeness, TQBF,9/20/2024,14,关于同学讨论发言,研究生的课程应该有同学的发言讨论。-三章的部分可作为讨论内容。 在教师讲解下，学完前面章后， 已经有了很好的基础。,我们提供了同学作报告PPT的部分素材。,这是作为教学科研的基本训练的一个重要环节，学生应该能根据教材，作出有自己特色的PPT发言稿. 这里提供一些素材，试图减小难度。,PPT不能仅仅是剪报,。一份好的讨论班PPT 应该有同学的理解和创新.,(素材节选自教材， 但不能代替教材),从素材作PPT一般 需要用 读 -减 -加 三个过程。,先充分阅读理解 教材，,从此素材中删去次要语句，,增加自己的心得，理解方法，解释和图形。,PPT应该突出思路，突出要点, 适当的比喻可以帮助理解。,9/20/2024,15,可计算理论目录,15周 讨论 第9章 3人,9.1-9.3.1 9.3.29.3.3 9.49.6,16周 讨论 第10章 3人,10.1， 10.2 ， 10.3,17 周 讨论 第10章 4人,11.1-11.2， 11.3, 11.4, 11.5-11.6,18- 19 周 复习,20 周 Final exam, Chapters 0-8. Open book open notes.,中间可能有节假日，运动会或会议的耽误，相应时间安排为自习，作业，或网上答疑，全课程可能需要21周,9/20/2024,16,关于引用和标注,1 本电子教案以 Sipser, Michael, 等著的Introduction to the Theory of Computation（ PWS Publishing Company, 1997）. 为基本教材 ，结合了教案作者在科研和教学中的心得体会（,用五角星 符号 标出）,，教案中引用了原著作中大量材料、图表，这是教案中必须的引用，,在此对原著作者致谢,。电子教案中也引用了在国内外会议、课堂，网络上学习到的一些资料。有些资料是人们,共创、共享和共传的知识财富,，一时难以查出资料的最先出处。一并,在此向 所引用内容的作者们致谢。,2 PowerPoint 页面 共计 800 多页， 随时修改增减,3 有些页面是多页连续的动感页面，一些淡色字句留下的悬念，会在下页用增强色调突出。,9/20/2024,17,关于引用和标注,4 本电子教案以在 第一周内容 0_0可计算理论教学计划060724.ppt列出了四川大学计算机学院2002-2006年度的教学计划。实践表明，深度难度基本合适,5 本教案作为教学方法探索的结果，奉献给相关的师生使用。使用者可以根据实际情况修改，加进进自己的创新。教案的编写也是创作，可以比喻为把小说改编为电视剧的工作。这一工作在学术思想上不是原创，但在教学艺术、教学方法上有改编者的工作。因此，希望再次改编者标注 “,在四川大学唐常杰教授可计算理论电子教案基础上改编” 或 “参照了或引用了.的电子教案”或类似的字样,。,PPT文件名称的意义：,01_1d2_概念自动机语言060712.ppt,01 - week 1 , 第一周,1d2 -1.2 节开始,概念自动机语言章节内容,060712最后修改时间,9/20/2024,18,