AnIntroduction

toComputerScience計算機科學引論XIANG，Hui向輝

ShandongUniversity1.Chapter12:TheoryofComputation12.1FunctionsandTheirComputation12.2TuringMachines12.3UniversalProgrammingLanguages12.4ANoncomputableFunction12.5ComplexityofProblems12.6Public-KeyCryptography2.FunctionsFunction:Acorrespondencebetweenacollectionofpossibleinputvaluesandacollectionofpossibleoutputvaluessothateachpossibleinputisassignedasingleoutput3.Functions(continued)Computingafunction:

DeterminingtheoutputvalueassociatedwithagivensetofinputvaluesNoncomputablefunction:

Afunctionthatcannotbecomputedbyanyalgorithm4.Figure12.1Anattempttodisplaythefunctionthatconvertsmeasurementsinyardsintometers5.Figure12.2ThecomponentsofaTuringmachine6.TuringMachineOperationInputsateachstepStateValueatcurrenttapepositionActionsateachstepWriteavalueatcurrenttapepositionMoveread/writeheadChangestate7.Figure12.3ATuringmachineforincrementingavalue8.Church-TuringThesisThefunctionsthatarecomputablebyaTuringmachineareexactlythefunctionsthatcanbecomputedbyanyalgorithmicmeans.9.UniversalProgrammingLanguageAlanguagewithwhichasolutiontoanycomputablefunctioncanbeexpressedExamples:“BareBones”andmostpopularprogramminglanguages10.TheBareBonesLanguageBareBonesisasimple,yetuniversallanguage.Statementsclearname;incrname;decrname;whilenamenot0do;…end;11.Figure12.4ABareBonesprogramforcomputingXxY12.Figure12.5ABareBonesimplementationoftheinstruction“copyTodaytoTomorrow”13.TheHaltingProblemGiventheencodedversionofanyprogram,return1iftheprogramisself-terminating,or0iftheprogramisnot.14.Figure12.6Testingaprogramforself-termination15.Figure12.7Provingtheunsolvabilityofthehaltingprogram16.ComplexityofProblemsTimeComplexity:ThenumberofinstructionexecutionsrequiredUnlessotherwisenoted,“complexity”means“timecomplexity.”AproblemisinclassO(f(n))ifitcanbesolvedbyanalgorithminQ(f(n)).AproblemisinclassQ(f(n))ifthebestalgorithmtosolveitisinclassQ(f(n)).17.Figure12.8AprocedureMergeListsformergingtwolists18.Figure12.9ThemergesortalgorithmimplementedasaprocedureMergeSort19.Figure12.10Thehierarchyofproblemsgeneratedbythemergesortalgorithm20.Figure12.11Graphsofthemathematicalexpressionsn,lgn,nlgn,andn221.PversusNPClassP:AllproblemsinanyclassQ(f(n)),wheref(n)isapolynomialClassNP:Allproblemsthatcanbesolvedbyanondeterministicalgorithminpolynomialtime

Nondeterministicalgorithm=an“algorithm”whosestepsmaynotbeuniquelyandcompletelydeterminedbytheprocessstateWhethertheclassNPisbiggerthanclassPiscurrentlyunknown.22.Figure12.12Agraphicsummationoftheproblemclassification23.Public-KeyCryptographyKey:AvalueusedtoencryptordecryptamessagePublickey:UsedtoencryptmessagesPrivatekey:UsedtodecryptmessagesRSA:ApopularpublickeycryptographicalgorithmReliesonthe(presumed)intractabilityoftheproblemoffactoringlargenumbers24.EncryptingtheMessage10111Encryptingkeys:n=91ande=510111two=23ten23e=235=6,436,3436,436,343÷91hasaremainderof44ten=100twoTherefore,encryptedversionof10111is100.25.DecryptingtheMessage100Decryptingkeys:d=29,n=91100two=4ten4d=429