ComputerScienceAnOverview计算机科学课件-Chap-1305-ak

ComputerScienceAnOverview13thEditionChapter5AlgorithmsChapter5:Algorithms5.1TheConceptofanAlgorithm5.2AlgorithmRepresentation5.3AlgorithmDiscovery5.4IterativeStructures5.5RecursiveStructures5.6EfficiencyandCorrectness5.1TheConceptofanAlgorithmAlgorithmsfrompreviouschaptersConvertingfromonebasetoanotherCorrectingerrorsindataCompressionManyresearchersbelievethateveryactivityofthehumanmindistheresultofanalgorithmFormalDefinitionofAlgorithmAnalgorithmisanorderedsetofunambiguous,executablestepsthatdefinesaterminatingprocessThestepsofanalgorithmcanbesequencedindifferentwaysLinear(1,2,3,…)Parallel(multipleprocessors)CauseandEffect(circuits)FormalDefinitionofAlgorithmATerminatingProcessCulminateswitharesultCanincludesystemsthatruncontinuouslyHospitalsystemsLongDivisionAlgorithmANon-terminatingProcessDoesnotproduceananswerChapter12:“Non-deterministicAlgorithms”TheAbstractNatureofAlgorithmsThereisadifferencebetweenanalgorithmanditsrepresentation.Analogy:differencebetweenastoryandabookAProgramisarepresentationofanalgorithm.AProcessistheactivityofexecutinganalgorithm.5.2AlgorithmRepresentationIsdoneformallywithwell-definedPrimitivesAcollectionofprimitivesconstitutesaprogramminglanguage.IsdoneinformallywithPseudocodePseudocodeisbetweennaturallanguageandaprogramminglanguage.Figure5.2FoldingabirdfromasquarepieceofpaperFigure5.3OrigamiprimitivesDesigningaPseudocodeLanguageChooseacommonprogramminglanguageLoosensomeofthesyntaxrulesAllowforsomenaturallanguageUseconsistent,concisenotationWewilluseaPython-likePseudocodePseudocodePrimitivesAssignment

name

=expressionexample

RemainingFunds

=CheckingBalance+

SavingsBalancePseudocodePrimitives(continued)Conditionalselection

if(condition):

activityexample

if(saleshavedecreased):lowerthepriceby5%PseudocodePrimitives(continued)Conditionalselection

if(condition):

activity

else:activityexample

if(yearisleapyear):

dailytotal=total/366

else:

dailytotal=total/365PseudocodePrimitives(continued)Repeatedexecution

while(condition):

bodyexample

while(ticketsremaintobesold):sellaticketPseudocodePrimitives(continued)Indentationshowsnestedconditions

if(notraining):

if(temperature==hot):goswimming

else:playgolf

else:watchtelevisionPseudocodePrimitives(continued)Defineafunction

def

name():example

def

ProcessLoan():Executingafunction

if(...):

ProcessLoan()

else:

RejectApplication()Figure5.4TheprocedureGreetingsinpseudocodedef

Greetings():

Count=3

while(Count>0):

print('Hello')Count=Count-1

PseudocodePrimitives(continued)Usingparameters

def

Sort(List):

.

.ExecutingSortondifferentlists

Sort(themembershiplist)

Sort(theweddingguestlist)5.3AlgorithmDiscoveryThefirststepindevelopingaprogramMoreofanartthanaskillAchallengingtaskPolya’sProblemSolvingSteps1.Understandtheproblem.2.Deviseaplanforsolvingtheproblem.3.Carryouttheplan.4.Evaluatethesolutionforaccuracyanditspotentialasatoolforsolvingotherproblems.Polya’sStepsintheContextofProgramDevelopment1.Understandtheproblem.2.Getanideaofhowanalgorithmicfunctionmightsolvetheproblem.3.Formulatethealgorithmandrepresentitasaprogram.4.Evaluatethesolutionforaccuracyanditspotentialasatoolforsolvingotherproblems.GettingaFootintheDoorTryworkingtheproblembackwardsSolveaneasierrelatedproblemRelaxsomeoftheproblemconstraintsSolvepiecesoftheproblemfirst(bottomupmethodology)Stepwiserefinement:Dividetheproblemintosmallerproblems(top-downmethodology)AgesofChildrenProblemPersonAischargedwiththetaskofdeterminingtheagesofB’sthreechildren.BtellsAthattheproductofthechildren’sagesis36.Arepliesthatanotherclueisrequired.BtellsAthesumofthechildren’sages.Arepliesthatanotherclueisneeded.BtellsAthattheoldestchildplaysthepiano.AtellsBtheagesofthethreechildren.Howoldarethethreechildren?Figure5.55.4IterativeStructuresAcollectionofinstructionsrepeatedinaloopingmannerExamplesinclude:SequentialSearchAlgorithmInsertionSortAlgorithmFigure5.6Thesequentialsearchalgorithminpseudocodedef

Search(List,TargetValue):

if(Listisempty):Declaresearchafailure

else:SelectthefirstentryinListtobeTestEntry

while(TargetValue>TestEntryandentriesremain):

SelectthenextentryinListasTestEntry

if(TargetValue==TestEntry):Declaresearchasuccess

else:DeclaresearchafailureFigure5.7ComponentsofrepetitivecontrolIterativeStructuresPretestloop:

while(condition):

bodyPosttestloop:

repeat:

body

until(condition)Figure5.8ThewhileloopstructureFigure5.9TherepeatloopstructureFigure5.10SortingthelistFred,Alex,Diana,Byron,andCarolalphabeticallyFigure5.11TheinsertionsortalgorithmexpressedinpseudocodedefSort(List):

N=2

while(N<=lengthofList):

Pivot=NthentryinListRemoveNthentryleavingaholeinList

while(thereisanEntryabovetheholeandEntry>Pivot):MoveEntrydownintotheholeleavingaholeinthelistabovetheEntryMovePivotintotheholeN=N+15.5RecursiveStructuresRepeatingthesetofinstructionsasasubtaskofitself.Multipleactivationsoftheprocedureareformed,allbutoneofwhicharewaitingforotheractivationstocomplete.Example:TheBinarySearchAlgorithmFigure5.12ApplyingourstrategytosearchalistfortheentryJohnFigure5.13Afirstdraftofthebinarysearchtechniqueif(Listisempty):Reportthatthesearchfailedelse:

TestEntry=middleentryintheList

if(TargetValue==TestEntry):Reportthatthesearchsucceeded

if(TargetValue<TestEntry):SearchtheportionofListprecedingTestEntryforTargetValue,andreporttheresultofthatsearch

if(TargetValue>TestEntry):SearchtheportionofListfollowingTestEntryforTargetValue,andreporttheresultofthatsearchFigure5.14ThebinarysearchalgorithminpseudocodedefSearch(List,TargetValue):

if(Listisempty):Reportthatthesearchfailed

else:

TestEntry=middleentryintheList

if(TargetValue==TestEntry):Reportthatthesearchsucceeded

if(TargetValue<TestEntry):

Sublist=portionofListprecedingTestEntry

Search(Sublist,TargetValue)

if(TargetValue<TestEntry):

Sublist=portionofListfollowingTestEntry

Search(Sublist,TargetValue)Figure5.15RecursivelySearchingFigure5.16SecondRecursiveSearchFigure5.17SecondRecursiveSearch,SecondSnapshotRecursiveControlRequiresinitialization,modification,andatestfortermination(basecase)Providestheillusionofmultiplecopiesofthefunction,createddynamicallyinatelescopingmannerOnlyonecopyisactuallyrunningatagiventime,theothersarewaiting5.6EfficiencyandCorrectnessThechoicebetweenefficientandinefficientalgorithmscanmakethedifferencebetweenapracticalsolutionandanimpracticaloneThecorrectnessofanalgorithmisdeterminedbyreasoningformallyaboutthealgorithm,notbytestingitsimplementationEfficiencyMeasuredasnumberofinstructionsexecutedUsesbigthetanotation:Example:InsertionsortisinΘ(n2)Incorporatesbest,worst,andaveragecaseanalysisFigure5.18Applyingtheinsertionsortinaworst-casesituationFigure5.19Graphoftheworst-caseanalysisoftheinsertionsortalgorithmFigure5.20Graphoftheworst-caseanalysisofthebinarysearchalgorithmSoftwareVerificationProofofcorrectness(withformallogic)AssertionsPreconditionsLoopinvariantsTestingismorecommonlyusedtoverifysoftwareTestingonlyprovesthattheprogramiscorrectforthetestcasesusedChainSeparatingProblemAtravelerhasagoldchainofsevenlinks.Hemuststayatanisolatedhotelforsevennights.Therenteachnightconsistsofonelinkfromthechain.Whatisthefewestnumb