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

CS_Dept.SichaunUniv.可计算理论2020/1/41/15四川大学计算机学院可计算理论课程说明和教学计划（2006.2-7）学分3周学时4任课教师唐常杰时间每周三8:00-11:35地点研3-301教材Material:MichaelSipser(MIT)[Required]Sipser,Michael,IntroductiontotheTheoryofComputation.PWSPublishingCompany,1997.(Bothfirstandsecondprintingareokay.ISBN0-619-21674-2)中译本，计算理论导引(第二版),(美)MichaelSipser著(麻省理工学院)唐常杰陈鹏向勇刘齐宏译，机械工业出版社出版，２００６.7ISBN7-111-19028-9)[Additional]Lewis,HarryR.,andPapadimitriou,ChristosH.,ElementsoftheTheoryofComputation,2nded.Prentice-Hall,1997.内容Chapters0-8.3(uptothePSPACE-completenessofTQBF)CS_Dept.SichaunUniv.可计算理论2020/1/42/15关于选择教材的体会2001-2002我们采用教材为：Lewis,HarryR.,andPapadimitriou,ChristosH.,ElementsoftheTheoryofComputation,2nded.Prentice-Hall,1997.2003-2006采用Sipser,Michael,IntroductiontotheTheoryofComputation.PWSPublishingCompany,1997.(Bothfirstandsecondprintingareokay.)这两本书是目前世界上主要大学采用最多的教材。经验表明，如果学生数学基础好，用前者较好，如学生计算机基础好，用后者更受学生欢迎。目前欧美大学中计算机专业用后者的大学越来越多。网上赞誉甚多CS_Dept.SichaunUniv.可计算理论2020/1/43/15电子教案下载电子教案可在下面三个网址下载：(机械工业出版社）川大计算机学院：~tangchangjie/teach/tang_teaching.htm川大教师主页：后两各地址可能更新及时一些。CS_Dept.SichaunUniv.可计算理论2020/1/44/15本电子教案由机械工业出版社出版CS_Dept.SichaunUniv.可计算理论2020/1/45/15请提改进意见任课教师：唐常杰联系信息四川大学计算机科学与技术系主任。博士生导师中国计算机学会数据库专业委员会副主任下载教案网址机械工业出版社网址或下列网址~chjtang/teach/tang_teching.htm~tangchangjie/teach/tang_teching.htm联系email:[e-mail]028-85466105经验表明，教案年年改，年年都有需改处。请提出改进意见。CS_Dept.SichaunUniv.可计算理论2020/1/46/15可计算理论课程说明和教学计划ＰPT文件名称说明：01_1d2_概念_自动机语言06021220.ppt•第一周，1.2节开始•主要内容•最后修改时间CS_Dept.SichaunUniv.可计算理论2020/1/47/15可计算理论课程说明和教学计划教材详略处理讲要点，前后次序有少数调整，教学计划，大致16—18周最后两章不讲或用讨论班形式讨论，有了基础，如果需要，已经能自学。参考国内外同行（如Berkeley,MIT等）对这门课程教材的处理经验，准备：略讲或自学的部分，要求了解主要思想Section2.2(中文3.2节）:theproofthatCFL=pushdownautomataSection5.1.,linearboundedautomataSection5.2Postcorrespondenceproblem快讲的部分，要求一般了解的章节，要求了解主要方法和演绎框架Section6.2decidabilityoflogicaltheories(Section6.2),Section6.3Turingreducibility(),Chapter8spacecomplexity().其余未列出的部分要求深入掌握（能作题目或作难题，通过考试）CS_Dept.SichaunUniv.可计算理论2020/1/48/15可计算理论课程说明和教学计划考查方式(暂定):30%-Homework(onewillbedropped)20%-Midterm50%-FinalCS_Dept.SichaunUniv.可计算理论2020/1/49/15可计算理论课程说明和教学计划Homework:参见”作业.PPT”要求用一个比较好的本子（如硬面，B5以上），作布置和自选题目，记录研究与思考，作业本在检查后归还，作为学生自己的永久的纪念（上课时参见示范实例）。（亦可能复印部分）作业参见~tangchangjie/tang_teching.htmLectureSlides/TentativeSchedule草案，将在实施中调整进度，遇节假日，运动会，重要会议则顺延,在每次课前1-2周发布最后修改的PPT，可按PPT预习）CS_Dept.SichaunUniv.可计算理论2020/1/410/15可计算理论目录LectureSlides/TentativeSchedule（草案）将在实施中调整进度,每次课程结束时预报下两次进度在每次课前1-2周发布相应的电子教案最后修改版本遇节假日，运动会，重要会议则顺延）参见~tangchangjie/tang_teching.htmCS_Dept.SichaunUniv.可计算理论2020/1/411/15可计算理论目录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/CFLpumpinlemma73pagesCS_Dept.SichaunUniv.可计算理论2020/1/412/15可计算理论目录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周专题讨论补充材料半期考试CS_Dept.SichaunUniv.可计算理论2020/1/413/15可计算理论目录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-LevinTheoremCS_Dept.SichaunUniv.可计算理论2020/1/414/15可计算理论目录13,NP-completenessofSATand3SAT,provingNP-completeness.14周Chapter7:NP-completenessofHAMPATH,SUBSETSUMChapter8:Spacecomplexity,Savitch'stheorem,PSPACE,PSPACEcompleteness,TQBFCS_Dept.SichaunUniv.可计算理论2020/1/415/15关于同学讨论发言研究生的课程应该有同学的发言讨论。８-９-１０三章的部分可作为讨论内容。在教师讲解下，学完前面７章后，已经有了很好的基础。我们提供了同学作报告PPT的部分素材。这是作为教学科研的基本训练的一个重要环节，学生应该能根据教材，作出有自己特色的PPT发言稿.这里提供一些素材，试图减小难度。PPT不能仅仅是剪报。一份好的讨论班PPT应该有同学的理解和创新.(素材节选自教材，但不能代替教材)从素材作PPT一般需要用读--减---加三个过程。先充分阅读理解教材，从此素材中删去次要语句，增加自己的心得，理解方法，解释和图形。PPT应该突出思路，突出要点,适当的比喻可以帮助理解。CS_Dept.SichaunUniv.可计算理论2020/1/416/15可计算理论目录15周讨论第9章3人9.1--9.3.19.3.2—9.3.39.4—9.616周讨论第10章3人10.1，10.2，10.317周讨论第10章4人11.1--11.2，11.3,11.4,