资源描述:
《离散数学北京邮电大学.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,aiN,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=