CS_Dept.SichaunUniv.可计算理论可计算理论可计算理论可计算理论可计算理论 课程说明和教学计划（课程说明和教学计划（课程说明和教学计划（课程说明和教学计划（2006.2-72006.2-7）学分学分3周学时周学时4任课教师任课教师唐常杰唐常杰每周三8:00-11:35地点地点研研3-301教材教材Material:MichaelSipser(MIT)RequiredSipser,Michael,Introduction to the Theory of Computation.PWSPublishingCompany,1997.(Bothfirstandsecondprintingareokay.ISBN0-619-21674-2)中译本，计算理论导引计算理论导引(第二版第二版),唐常杰陈鹏向勇刘齐宏译，机械工业出版社出版，.7ISBN7-111-19028-9)AdditionalLewis,HarryR.,andPapadimitriou,ChristosH.,Elements of the Theory of Computation,2nded.Prentice-Hall,1997.内容内容Chapters0-8.3(uptothePSPACE-completenessofTQBF)7/29/20241CS_Dept.SichaunUniv.可计算理论关于选择教材的体会关于选择教材的体会关于选择教材的体会关于选择教材的体会2001-2002我们采用教材为：Lewis,HarryR.,andPapadimitriou,ChristosH.,Elements of the Theory of Computation,2nded.Prentice-Hall,1997.2003-2006采用Sipser,Michael,Introduction to the Theory of Computation.PWSPublishingCompany,1997.(Bothfirstandsecondprintingareokay.)这两本书是目前世界上主要大学采用最多的教材。经验表明，如果学生数学基础好，用前者较好，如学生计算机基础好，用后者更受学生欢迎。目前欧美大学中计算机专业用后者的大学越来越多。网上赞誉甚多7/29/20242CS_Dept.SichaunUniv.可计算理论电子教案下载n电子教案可在下面三个网址下载：n(机械工业出版社）n川大计算机学院：nn川大教师主页：nn后两各地址可能更新及时一些。7/29/20243CS_Dept.SichaunUniv.可计算理论本电子教案由机械工业出版社出版7/29/20244CS_Dept.SichaunUniv.可计算理论请提改进意见请提改进意见任课教师任课教师：唐常杰唐常杰联系信息联系信息四川大学计算机科学与技术系四川大学计算机科学与技术系主任。主任。博士生导师博士生导师中国计算机学会数据库专业委员会副主任中国计算机学会数据库专业委员会副主任下载教案网址下载教案网址机械工业出版社网址机械工业出版社网址或或下列网址下列网址联系联系email:028-85466105经验表明，教案年年改，年年都有需改处。经验表明，教案年年改，年年都有需改处。请提出改进意见。请提出改进意见。7/29/20245CS_Dept.SichaunUniv.可计算理论可计算理论可计算理论课程说明和教学计划课程说明和教学计划PT文件名称说明：文件名称说明：01_1d2_概念概念_自动机语言自动机语言06021220.ppt第一周 ，1.2节开始主要内容最后修改时间7/29/20246CS_Dept.SichaunUniv.可计算理论可计算理论可计算理论课程说明和教学计划课程说明和教学计划n教材详略处理教材详略处理H讲要点，前后次序有少数调整，H教学计划，大致1618周最后两章不讲或用讨论班形式讨论，有了基础，如果需要，已经能自学。n参考国内外同行（如参考国内外同行（如Berkeley,MIT等）对这门课程教材的等）对这门课程教材的处理经验，准备：处理经验，准备：n略讲或自学的部分略讲或自学的部分，要求了解主要思想，要求了解主要思想HSection2.2(中文中文3.2节）节）:theproofthatCFL=pushdownautomataHSection5.1.,linearboundedautomataHSection5.2Postcorrespondenceproblemn快讲的部分，快讲的部分，要求一般了解的章节，要求了解主要方法和演绎框架要求一般了解的章节，要求了解主要方法和演绎框架HSection6.2decidabilityoflogicaltheories(Section6.2),HSection6.3Turingreducibility(),HChapter8spacecomplexity().n其余未列出的部分要求深入掌握（能作题目其余未列出的部分要求深入掌握（能作题目或作难题，通过考试）或作难题，通过考试）7/29/20247CS_Dept.SichaunUniv.可计算理论可计算理论可计算理论课程说明和教学计划课程说明和教学计划n考查方式考查方式(暂定暂定):n30%-Homework(onewillbedropped)n20%-Midtermn50%-Final7/29/20248CS_Dept.SichaunUniv.可计算理论可计算理论可计算理论课程说明和教学计划课程说明和教学计划nHomework:参见参见”作业作业.PPT”n要求用一个比较好的本子（如硬面，B5以上），作布置和自选题目，记录研究与思考，作业本在检查后归还，作为学生自己的永久的纪念（上课时参见示范实例）。（亦可能复印部分）n作业作业参见参见nLectureSlides/TentativeSchedulen草案，将在实施中调整进度，遇节假日，运动会，重要会议草案，将在实施中调整进度，遇节假日，运动会，重要会议则顺延则顺延,n在每次课前在每次课前1-2周发布最后修改的周发布最后修改的PPT，可按，可按PPT预习）预习）7/29/20249CS_Dept.SichaunUniv.可计算理论可计算理论目录LectureSlides/TentativeSchedule（草案）（草案）将在实施中调整进度将在实施中调整进度,每次课程结束时预报下两次进度每次课程结束时预报下两次进度在每次课前在每次课前1-2周发布相应的电子教案最后修改版本周发布相应的电子教案最后修改版本遇节假日，运动会，重要会议遇节假日，运动会，重要会议则顺延）则顺延）参见参见http:/cs.scu.edu.cn/tangchangjie/tang_teching.htm7/29/202410CS_Dept.SichaunUniv.可计算理论可计算理论目录LectureSlides/TentativeSchedule草案，将在实施中调整进度，遇节假日，运动会，重要会议草案，将在实施中调整进度，遇节假日，运动会，重要会议则顺延则顺延,在每次课前在每次课前1-2周发布最后修改的周发布最后修改的PDF，下载和阅读下载和阅读iamscucsphd可按可按PDF预习）预习）1周周Chapter0:Introduction,mathematicalnotation,prooftechniquesChapter1:Deterministicfiniteautomata(DFA),nondeterministicfiniteautomata(NFA),84pages2周周Chapter1:DFA=NFA,regularexpression(RE),46pages2周周Chapter1:RE=NFA,nonregularlanguages/REpumpinglemma39page3周周Chapter2:Context-freegrammars(CFG),Chomskynormalform,allRLareCFG59pages4周周Chapter2:Pushdownautomata(PDA),Non-CFlanguages/CFLpumpinlemma73pages7/29/202411CS_Dept.SichaunUniv.可计算理论可计算理论目录5周周51pagesChapter3:Turingmachines(TMs),TMdecidablelanguages,TMrecognizablelanguages,EquivalencebetweenmultitapeTMsChapter4:EquivalencebetweennondeterministicTMsandothermodels,Church-Turingthesis,Decidablelanguages,decidabilityRL/PDAs/RE6周周Chapter4:DecidabilityCFLs/CFGs,Haltingproblem,counting/diagonalization,Chapter4:UndecidabilityoftheHaltingproblem,TMunrecognizablelanguages52pages6周周Chapter5:Computationhistories,examplesofundecidablelanguagesChapter5:TMcomputablefunctions,mappingreducibility50pages7周周Chapters0-5:Reviewsession66pages8周周专题讨论补充材料专题讨论补充材料半期考试半期考试7/29/202412CS_Dept.SichaunUniv.可计算理论可计算理论目录8周周Chapter6:Recursiontheorem,undecidabilitybyself-reference,undecidabilityofmathematicaltheories45pages10周周Chapter6+handout:Kolmogorovcomplexity/minimallengthdescriptions,randomness,argumentsbyincompressibility69pages11周周Chapter7:Time-complexity,polynomialtime(P),languagesinP,StrongChurch-TuringthesisChapter7:Nondeterministicpolynomialtime(NP),SAT4712周周Chapter7:Polynomialtimereductions,NP-completeness,3SATversusCLIQUE,Cook-LevinTheorem7/29/202413CS_Dept.SichaunUniv.可计算理论可计算理论目录13,NP-completenessofSATand3SAT,provingNP-completeness.14周周Chapter7:NP-completenessofHAMPATH,SUBSETSUMChapter8:Spacecomplexity,Savitchstheorem,PSPACE,PSPACEcompleteness,TQBF7/29/202414CS_Dept.SichaunUniv.可计算理论关于同学讨论发言研究生的课程应该有同学的发言讨论。-三章的部分可作为讨论内容。在教师讲解下，学完前面章后，已经有了很好的基础。我们提供了同学作报告PPT的部分素材。这是作为教学科研的基本训练的一个重要环节，学生应该能根据教材，作出有自己特色的PPT发言稿.这里提供一些素材，试图减小难度。PPT不能仅仅是剪报。一份好的讨论班PPT应该有同学的理解和创新.(素材节选自教材，但不能代替教材)从素材作PPT一般需要用读-减-加三个过程。先充分阅读理解教材，从此素材中删去次要语句，增加自己的心得，理解方法，解释和图形。PPT应该突出思路，突出要点,适当的比喻可以帮助理解。7/29/202415CS_Dept.SichaunUniv.可计算理论可计算理论目录15周周讨论讨论第第9章章3人人9.1-9.3.19.3.29.3.39.49.616周周讨论讨论第第10章章3人人10.1，10.2，10.317周周讨论讨论第第10章章4人人11.1-11.2，11.3,11.4,11.5-11.618-19周周复习复习20周周Finalexam,Chapters0-8.Openbookopennotes.中间可能有节假日，运动会或会议的耽误，相应时间安中间可能有节假日，运动会或会议的耽误，相应时间安排为自习，作业，或网上答疑，全课程可能需要排为自习，作业，或网上答疑，全课程可能需要21周周7/29/202416CS_Dept.SichaunUniv.可计算理论关于引用和标注n1 本电子教案以 Sipser, Michael, 等著的Introduction to the Theory of Computation（ PWS Publishing Company, 1997）. 为基本教材 ，结合了教案作者在科研和教学中的心得体会（用五角星 符号 标出），教案中引用了原著作中大量材料、图表，这是教案中必须的引用，在此对原著作者致谢。电子教案中也引用了在国内外会议、课堂，网络上学习到的一些资料。有些资料是人们共创、共享和共传的知识财富，一时难以查出资料的最先出处。一并在此向 所引用内容的作者们致谢。n2 PowerPoint 页面 共计 800 多页， 随时修改增减n3 有些页面是多页连续的动感页面，一些淡色字句留下的悬念，会在下页用增强色调突出。7/29/202417CS_Dept.SichaunUniv.可计算理论关于引用和标注n4 本电子教案以在 第一周内容 0_0可计算理论教学计划060724.ppt列出了四川大学计算机学院2002-2006年度的教学计划。实践表明，深度难度基本合适n5 本教案作为教学方法探索的结果，奉献给相关的师生使用。使用者可以根据实际情况修改，加进进自己的创新。教案的编写也是创作，可以比喻为把小说改编为电视剧的工作。这一工作在学术思想上不是原创，但在教学艺术、教学方法上有改编者的工作。因此，希望再次改编者标注 “在四川大学唐常杰教授可计算理论电子教案基础上改编” 或 “参照了或引用了.的电子教案”或类似的字样 。nPPT文件名称的意义：文件名称的意义：01_1d2_概念自动机语言060712.ppt01-week1,第一周1d2-1.2节开始概念自动机语言章节内容060712最后修改时间7/29/202418