离散数学北京邮电大学

AlgorithmsRosen6thed.,§3.1Abual-Khowarizmi(ca.780-850)Chapter3:MoreFundamentals•§3.1:Algorithms–Formalprocedures•§3.2:GrowthofFunctions•§3.3:Complexityofalgorithms–Analysisusingorder-of-growthnotation.•§3.4:TheIntegers&Division–Somebasicnumbertheory.•§3.5:PrimesandGreatestCommonDivisors•§3.6:Integers&Algorithms–Alternatebases,algorithmsforbasicarithmetic•§3.7:ApplicationsofNumbertheory–Public-KeyCryptography•§3.8:Matrices–Somebasiclinearalgebra.§3.1:Algorithms•Thefoundationofcomputerprogramming.•Mostgenerally,analgorithmjustmeansadefiniteprocedureforperformingsomesortoftask.•Acomputerprogramissimplyadescriptionofanalgorithm,inalanguagepreciseenoughforacomputertounderstand,requiringonlyoperationsthatthecomputeralreadyknowshowtodo.•Wesaythataprogramimplements(or“isanimplementationof”)itsalgorithm.ProgrammingLanguages•Somecommonprogramminglanguages:–Newer:Java,C,C++,C#,VisualBasic,JavaScript,Perl,Tcl,Pascal,manyothers…–Older:Fortran,Cobol,Lisp,Basic–Assemblylanguages,forlow-levelcoding.•Inthisclasswewilluseaninformal,Pascal-like“pseudo-code”language.•Youshouldknowatleast1reallanguage!AlgorithmExample(English)•Task:Givenasequence{ai}=a1,…,an,aiN,saywhatitslargestelementis.•Onealgorithmfordoingthis,inEnglish:–Setthevalueofatemporaryvariablev(largestelementseensofar)toa1’svalue.–Lookatthenextelementaiinthesequence.–Ifaiv,thenre-assignvtothenumberai.–Repeatthenprevious2stepsuntiltherearenomoreelementsinthesequence,&returnv.ExecutinganAlgorithm•Whenyoustartupapieceofsoftware,wesaytheprogramoritsalgorithmarebeingrunorexecutedbythecomputer.•Givenadescriptionofanalgorithm,youcanalsoexecuteitbyhand,byworkingthroughallofitsstepswithpencil&paper.•Before~1940,“computer”meantapersonwhosejobwastoexecutealgorithms!ExecutingtheMaxalgorithm•Let{ai}=7,12,3,15,8.Finditsmaximum…•Setv=a1=7.•Lookatnextelement:a2=12.•Isa2v?Yes,sochangevto12.•Lookatnextelement:a2=3.•Is312?No,leavevalone….•Is1512?Yes,v=15…AlgorithmCharacteristicsSomeimportantgeneralfeaturesofalgorithms:•Input.Informationordatathatcomesin.•Output.Informationordatathatgoesout.•Definiteness.Algorithmispreciselydefined.•Correctness.Outputscorrectlyrelatetoinputs.•Finiteness.Won’ttakeforevertodescribeorrun.•Effectiveness.Individualstepsarealldo-able.•Generality.Worksformanypossibleinputs.•Efficiency.Takeslittletime&memorytorun.PseudocodeLanguage:§A3procedurename(argument:type)variable:=expressioninformalstatementbeginstatementsend{comment}ifconditionthenstatement[elsestatement]forvariable:=initialvaluetofinalvaluestatementwhileconditionstatementprocname(arguments)Notdefinedinbook:returnexpressionprocedureprocname(arg:type)•Declaresthatthefollowingtextdefinesaprocedurenamedprocnamethattakesinputs(arguments)namedargwhicharedataobjectsofthetypetype.–Example:proceduremaximum(L:listofintegers)[statementsdefiningmaximum…]variable:=expression•Anassignmentstatementevaluatestheexpressionexpression,thenreassignsthevariablevariabletothevaluethatresults.–Exampleassignmentstatement:v:=3x+7(Ifxis2,changesvto13.)•Inpseudocode(butnotrealcode),theexpressionmightbeinformallystated:–x:=thelargestintegerinthelistLInformalstatement•SometimeswemaywriteastatementasaninformalEnglishimperative,ifthemeaningisstillclearandprecise:e.g.,“swapxandy”•Keepinmindthatrealprogramminglanguagesneverallowthis.•Whenweaskforanalgorithmtodoso-and-so,writing“Doso-and-so”isn’tenough!–Breakdownalgorithmintodetailedsteps.beginstatementsend•Groupsasequenceofstatementstogether:beginstatement1statement2…statementnend•Allowsthesequencetobeusedjustlikeasinglestatement.•Mightbeused:–Afteraproceduredeclaration.–Inanifstatementafterthenorelse.–Inthebodyofafororwhileloop.Curlybraces{}areusedinsteadinmanylanguages.{comment}•Notexecuted(doesnothing).•Natural-languagetextexplainingsomeaspectoftheproceduretohumanreaders.•Alsocalledaremarkinsomerealprogramminglanguages,e.g.BASIC.•Example,mightappearinamaxprogram:–{Notethatvisthelargestintegerseensofar.}ifconditionthenstatement•Evaluatethepropositionalexpressioncondition.–IftheresultingtruthvalueisTrue,thenexecutethestatementstatement;–otherwise,justskiponaheadtothenextstatementaftertheifstatement.•Variant:ifcondthenstmt1elsestmt2–Likebefore,butifftruthvalueisFalse,executesstmt2.whileconditionstatement•Evaluatethepropositional(Boolean)expressioncondition.•IftheresultingvalueisTrue,thenexecutestatement.•ContinuerepeatingtheabovetwoactionsoverandoveruntilfinallytheconditionevaluatestoFalse;thenproceedtothenextstatement.whileconditionstatement•Alsoequivalenttoinfinitenestedifs,likeso:ifconditionbeginstatementifconditionbeginstatement…(continueinfinitenestedif’s)endendforvar:=initialtofinalstmt•Initialisanintegerexpression.•Finalisanotherintegerexpression.•Semantics:Repeatedlyexecutestmt,firstwithvariablevar:=initial,thenwithvar:=initial+1,thenwithvar:=initial+2,etc.,thenfinallywithvar:=final.•Question:Whathappensifstmtchangesthevalueofvar,orthevaluethatinitialorfinalevaluatesto?forvar:=initialtofinalstmt•Forcanbeexactlydefinedintermsofwhile,likeso:beginvar:=initialwhilevarfinalb