Limits of Computation 2013外文电子版

《Limits of Computation 2013外文电子版》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、LIMITSOFCOMPUTATIONComputerScienceLIMITSOFCOMPUTATIONLimitsofComputation:AnIntroductiontotheUndecidableandtheAnIntroductiontotheIntractableoffersagentleintroductiontothetheoryofcomputationalcomplexity.Itexplainsthedifficultiesofcomputation,addressingproblemsUndecidableandtheIntract

2、ablethathavenoalgorithmatallandproblemsthatcannotbesolvedefficiently.Thebookenablesreaderstounderstand:•WhatdoesitmeanforaproblemtobeunsolvableortobeNP-complete?•Whatismeantbyacomputationandwhatisageneralmodelofacomputer?•Whatdoesitmeanforanalgorithmtoexistandwhatkindsofproblemshav

3、enoalgorithm?•Whatproblemshavealgorithmsbutthealgorithmmaytakecenturiestofinish?Developedfromtheauthors’courseoncomputationalcomplexitytheory,thetextissuitableforadvancedundergraduateandbeginninggraduatestudentswithoutastrongbackgroundintheoreticalcomputerscience.Eachchapterpresent

4、sthefundamentals,examples,completeproofsoftheorems,andawiderangeofexercises.Features•Helpsreadersunderstandthenatureofcomputation•Focusesonthetwomainquestionsoftheoreticalcomputerscience•PresentscompleteproofsofmanyNP-completeproblems•Providesin-depthdiscussionsofdifficulttopics,su

5、chasdifferentsizesofinfinity,reducibility,andself-reference•DescribesTuringmachinesfromstatediagramstoencodings•Assumesnopriorknowledgeofautomata,advancedalgorithmicJohnsonReiteranalysis,andformallanguagesEdnaE.ReiterK13878ClaytonMatthewJohnsonK13878_Cover.indd18/21/1212:46PMLIMITS

6、OFCOMPUTATIONAnIntroductiontotheUndecidableandtheIntractableLIMITSOFCOMPUTATIONAnIntroductiontotheUndecidableandtheIntractableEdnaE.ReiterClaytonMatthewJohnsonCRCPressTaylor&FrancisGroup6000BrokenSoundParkwayNW,Suite300BocaRaton,FL33487-2742©2013byTaylor&FrancisGroup,LLCCRCPressisa

7、nimprintofTaylor&FrancisGroup,anInformabusinessNoclaimtooriginalU.S.GovernmentworksVersionDate:20120808InternationalStandardBookNumber-13:978-1-4398-8207-8(eBook-PDF)Thisbookcontainsinformationobtainedfromauthenticandhighlyregardedsources.Reasonableeffortshavebeenmadetopublishrelia

8、bledataandinformation,butt