离散数学北京邮电大学.ppt

《离散数学北京邮电大学.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、AlgorithmsRosen6thed.,§3.1Abual-Khowarizmi(ca.780-850)Chapter3:MoreFundamentals§3.1:AlgorithmsFormalprocedures§3.2:GrowthofFunctions§3.3:ComplexityofalgorithmsAnalysisusingorder-of-growthnotation.§3.4:TheIntegers&DivisionSomebasicnumbertheory.§3.5:PrimesandGre

2、atestCommonDivisors§3.6:Integers&AlgorithmsAlternatebases,algorithmsforbasicarithmetic§3.7:ApplicationsofNumbertheoryPublic-KeyCryptography§3.8:MatricesSomebasiclinearalgebra.§3.1:AlgorithmsThefoundationofcomputerprogramming.Mostgenerally,analgorithmjustmeansad

3、efiniteprocedureforperformingsomesortoftask.Acomputerprogramissimplyadescriptionofanalgorithm,inalanguagepreciseenoughforacomputertounderstand,requiringonlyoperationsthatthecomputeralreadyknowshowtodo.Wesaythataprogramimplements(or“isanimplementationof”)itsalgo

4、rithm.AlgorithmsYouAlreadyKnowGrade-schoolarithmeticalgorithms:Howtoaddanytwonaturalnumberswrittenindecimalonpaper,usingcarries.Similar:Subtractionusingborrowing.Multiplication&longdivision.Yourfavoritecookingrecipe.HowtoregisterforclassesatBUPT.ProgrammingLang

5、uagesSomecommonprogramminglanguages:Newer:Java,C,C++,C#,VisualBasic,JavaScript,Perl,Tcl,Pascal,manyothers…Older:Fortran,Cobol,Lisp,BasicAssemblylanguages,forlow-levelcoding.Inthisclasswewilluseaninformal,Pascal-like“pseudo-code”language.Youshouldknowatleast1rea

6、llanguage!AlgorithmExample(English)Task:Givenasequence{ai}=a1,…,an,aiN,saywhatitslargestelementis.Onealgorithmfordoingthis,inEnglish:Setthevalueofatemporaryvariablev(largestelementseensofar)toa1’svalue.Lookatthenextelementaiinthesequence.Ifai>v,thenre-assignvt

7、othenumberai.Repeatthenprevious2stepsuntiltherearenomoreelementsinthesequence,&returnv.ExecutinganAlgorithmWhenyoustartupapieceofsoftware,wesaytheprogramoritsalgorithmarebeingrunorexecutedbythecomputer.Givenadescriptionofanalgorithm,youcanalsoexecuteitbyhand,by

8、workingthroughallofitsstepswithpencil&paper.Before~1940,“computer”meantapersonwhosejobwastoexecutealgorithms!ExecutingtheMaxalgorithmLet{ai}=7,12,3,15,8.Finditsmaximum…Setv=