资源描述：
《清华大学计算导论英文版introduction to the theory of computation》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、IntroductiontotheTheoryofComputation,MichaelSipserChapter0:IntroductionAutomata,ComputabilityandComplexity:·Theyarelinkedbythequestion:o“Whatarethefundamentalcapabilitiesandlimitationsofcomputers?”·Thetheoriesofcomputabilityandcomplexityarecloselyrelated.Incomplexitytheory,the
2、objectiveistoclassifyproblemsaseasyonesandhardones,whereasincomputabilitytheoryheclassificationofproblemsisbythosethataresolvableandthosethatarenot.Computabilitytheoryintroducesseveraloftheconceptsusedincomplexitytheory.·Automatatheorydealswiththedefinitionsandpropertiesofmath
3、ematicalmodelsofcomputation.·Onemodel,calledthefiniteautomaton,isusedintextprocessing,compilers,andhardwaredesign.Anothermodel,calledthecontext–freegrammar,isusedinprogramminglanguagesandartificialintelligence.StringsandLanguages:·Thestringofthelengthzeroiscalledtheemptystring
4、andiswrittenase.·Alanguageisasetofstrings.Definitions,TheoremsandProofs:·Definitionsdescribetheobjectsandnotionsthatweuse.·Aproofisaconvincinglogicalargumentthatastatementistrue.·Atheoremisamathematicalstatementprovedtrue.·Occasionallyweprovestatementsthatareinterestingonlybec
5、ausetheyassistintheproofofanother,moresignificantstatement.Suchstatementsarecalledlemmas.·Occasionallyatheoremoritsproofmayallowustoconcludeeasilythatother,relatedstatementsaretrue.Thesestatementsarecalledcorollariesofthetheorem.Chapter1:RegularLanguagesIntroduction:·Anidealiz
6、edcomputeriscalleda“computationalmodel”whichallowsustosetupamanageablemathematicaltheoryofitdirectly.·Aswithanymodelinscience,acomputationalmodelmaybeaccurateinsomewaysbutperhapsnotinothers.·Thesimplestmodeliscalled“finitestatemachine”or“finiteautomaton”.FiniteAutomata:·Finite
7、Automataaregoodmodelsforcomputerswithanextremelylimitedamountofmemory,likeforexampleanautomaticdoor,elevatorordigitalwatches.·Finiteautomataandtheirprobabilisticcounterpart“Markovchains”areusefultoolswhenweareattemptingtorecognizepatternsindata.Thesedevicesareusedinspeechproce
8、ssingandinopticalcharacterrecognition.Markovchainshaveevenbee
