中南大学算法设计郑谨.

DesignandAnalysisofAlgorithms（算法分析与设计）Zhengjin2020/1/8CentralSouthUniversity22020/1/8CentralSouthUniversity2课程基本信息主讲：郑瑾办公室：升华后楼406-1e-mail:[e-mail];[e-mail]电话：[phone]教材：IntroductiontoTheDesign&AnalysisofAlgorithms(ISBN01-2003-2170)算法设计与分析基础（第二版）AnanyLevitin著，潘彦译，清华大学出版社（中文版）参考书：算法导论，潘金贵等译，机械工业出版社算法导论，王晓东，清华大学出版社课件邮箱：[e-mail]:computer11DesignandAnalysisofAlgorithmsJinZhengAnalysisandDesignofComputerAlgorithms2020/1/8CentralSouthUniversity42020/1/8CentralSouthUniversity5科技殿堂里的两颗宝石科技殿堂里的两颗熠熠生辉的宝石：一颗是微积分，另一颗就是算法。微积分以及在微积分的基础上建立起来的数学分析体系成就了现代科学，而算法则成就了现代世界。2020/1/8CentralSouthUniversity6人类社会发展的三个阶段第一阶段，以锄头为代表的农业文明。第二阶段，以大机械流水线作业为代表的工业文明。牛顿、莱布尼兹发明微积分以后，人们才有能力把握运动和过程。有了微积分，就有了工业革命，就有了大工业生产，也就有了现代化的社会。航天飞机、宇宙飞船等现代化交通工具都是在微积分的帮助下制造出来的。经济领域中无论是纳什均衡，还是期权定价公式，都是通过建立数学模型、运用数学方法，并借助于数学语言来实现的。经济社会中的微积分在人类社会从农业文明跨入工业文明的过程中起到了决定性的作用。人类社会发展的三个阶段第三阶段，以计算机为代表的网络文明。随着计算机的开发、运用和发展，正逐渐改变着人们的工作方式、学习方式、生活方式，乃至思维方式，这标志着网络文明已经向我们走来。而计算机科学的基石则是算法（学）。2020/1/8CentralSouthUniversity72020/1/8CentralSouthUniversity8数学思维与计算思维数学训练数学思维：最深刻的东西：极限理论，微分，积分理论数学一般只满足于证明某个问题是否有解，或者对解的性质进行研究。算法（学）训练计算思维：计算机最深刻的东西：计算思维算法是问题的程序化解决方案，这些解决方案本身并不是答案，而是获得答案的精确指令。正是对于精确定义的结构化过程的强调，才使计算机科学有别于其他学科，特别是有别于理论数学。计算思维很多都体现在算法分析与设计课程中。2020/1/8CentralSouthUniversity9为什么要学习算法？实践角度：（必须）了解计算领域中不同种类问题的一系列标准（经典）算法；作为一个好的软件设计师，就要学会用已学知识来处理未知问题，碰到新问题时，你应该想想它和什么最像？哪种算法可以应用到这类问题上？从这些可能有用的算法中，选用什么算法最为合适？这门课将会给大家讲一系列的（经典）算法。具备设计新算法和分析其效率的能力。为什么要学习算法？理论角度(分析能力）：算法就是解决问题的一类特殊方法-它不是问题的答案，而是经过精确定义以获得答案的过程。---DonaldKnuth对算法精确定义的理解：一个人只有把知识教给别人，才能真正掌握它。实际上，一个人只有把知识教给“计算机”，才能“真正”掌握它，也就是说，将知识表述为一种算法（比起简单地按照常规去理解事物，用算法将其形式化会使我们理解更加深刻。）---2020/1/8CentralSouthUniversity102020/1/8CentralSouthUniversity112020/1/8CentralSouthUniversity11Algorithms（算法）Algorithmisthesoulofcomputer.Algorithmiseverywhere.Algorithmcantrainourwayofthinking（计算思维）Thiscoursewillmakeyoudifferent.如果你想成为一个牛人-----三年如一日地坚持每天编程！如果你想成为一个世界级的牛人：十年如一日地编程！！三年如一日+学好算法这门课！！2020/1/8CentralSouthUniversity12学习方法学而时习之（习：练习，演练）开车：练中学：作业计算机：？？技巧：1.writtingcode2.readingcode读的技能价值是无限的，看别人写的程序，理解其内容，看其是否能运行，如何为我所用，学习别人的的技能，来创造自己的东西，这没什么不好！3.一个关键的理念：写代码时，要考虑算法效率的优化！2020/1/8CentralSouthUniversity132020/1/8CentralSouthUniversity13AlgorithmsWhatisalgorithm?2020/1/8CentralSouthUniversity14假设有一1000页的电话号码本，要你从中找到一个人的名字，折半查找:500，250，125，63，31，15，7，3，2，1。10次，你就可以找到！从计算机看，这就是算法。这个算法是对数级的，想想高中学过的对数。这就给计算机科学家一些启示，即这种算法更智能，更迅速。现在假设不是1000页的电话本，而是一个搜索引擎上的索引，它包含100W更至更多如40亿网页，比实际还要多，如果一本电话本有40亿页，折半查找要多少次，才能找到你要找的人？（32次）。你可以算，数学算法的力量是无穷的，这就是科学家所谓的计算机思维。你可以把一个问题用比较直观的方法解决，但如果你把此类问题的数量（规模）增大，正如越来越多的互联网，和大规模数据系统中出现的问题，你应该怎样才能更高效？这就是算法分析与设计涉及的问题。假设现在又多了40亿个网页，（有80亿个），用同样的算法需要多几个步骤？只需1步，这就是效率！这就开始有意思了，这仅仅是我们从计算机科学领域获得的一些思维方法与启示，这种思维方法与启示不仅仅适用于计算机科学本身，同样也可以应用于其他的学科领域，那么这些技巧有什么实际用途呢？2020/1/8CentralSouthUniversity15众所周知，计算机的发明为许多必须进行大量数字计算的问题提供了一条捷径。计算机的计算能力是一般的人工计算无法比拟的。一个超级计算机可以以每秒钟进行亿万次运算的速度连续不停地进行运算。一般来说，需要进行数字计算的问题的运算量的大小与表征这个问题大小的变量数目N有关。变量数N越大，解决问题所需的计算时间T也越长。当然，计算时间T也取决于所使用的计算方法。计算机算法就是研究各种计算方法的学问。2020/1/8CentralSouthUniversity162020/1/8CentralSouthUniversity16Algorithms（算法）算法是一系列解决问题（可计算问题）的清晰指令，也就是说，对于符合一定规范的输入，能够在有限时间内获得所要求的输出。“computer”problemalgorithminputoutput指令：人或物能理解和执行的命令，这种人或物称为“computer”,在电子计算机发明以前，它的含义是指那些从事数学计算的人。现在一般是指电子计算设备。2020/1/8CentralSouthUniversity17“可计算问题”实例列举Sorting（排序）AReal-TimeDriver’sDirectionSystem（电子导航系统）最短路径个人体会：百度导航非常好！TheHumanGenomeProject（人类基因工程）Internet（计算机网络）路由问题Electroniccommerce（电子商务）公约加密与数字签名Inmanufacturingandothercommercialsettings（制造业等其它）资源分配及调度2020/1/8CentralSouthUniversity18算法的属性Finiteness（有穷性）：算法必须是有限步骤的。计算机程序是否有这个要求？（操作系统有这个要求吗？服务程序有这个要求吗？）Definiteness（确切性）算法的每一步都必须没有歧义，不能有半点含糊。InputOutputEffectiveness（可行性）每一步必须是可执行的（不能太粗，也不能太细），一般来说，如果一句话可用3句程序语言表示出，就可以了。2020/1/8CentralSouthUniversity19Correctness（正确性）Correctness(正确性）1.Proof:用某些模型去证明，但还没有成熟的理论去做这个事（程序证明）2.Test:（测试）nosyntaxerrorForsameinput:expectedresultsFortestcase:对测试用例都有预期的输出Forallinputs:Impossible!(因为输入有无穷种！）我们至少要达到第三层次！2020/1/8CentralSouthUniversity20Robustness（鲁棒性，稳定性）PreconditionOutput(range,type),boundaryProcessi=n;While(A[i]≠x)i--;i=n;While(i0)if(A[i]≠x)i--;还有何问题？当一个A[i]=x时，i永远大于0,i可能会小于0，出错有何问题？2020/1/8CentralSouthUniversity21Legibility(易读性）1.Comments(注释）每个模块/函数前进行注释，说明功能是什么，输入是什么，输出是什么，以说明模块/函数之间的调用接口（团队中分工协作），以用更新时间，作者等。对每个语句块（block)添加注释对不太能理解的语句加注释：如if语句，}等2.Identifiernaming(标志符变量有意义）（如i++;但写成counter,就明显是计数器了）3.Emptystring用空串或空行：模块间加空行，语句块间加空行4.Stucturalcontrol缩进式5.File/documentPs:请阅读《编程规范》，建议在写算法以及编程时，要求自己尽量这样做，以培养自己的专业素养！我们在上课所讲的算法中，由于篇幅所限，同时要详细讲解，而没使用注释，但自己在写时，一定要养成写注释的习惯。平2020/1/8CentralSouthUniversity22Gcd(m,n)：（求两个数的最大公约数）Firsttry--Euclid’salgorithm:gcd(m,n)=gcd(n,mmodn)第一步：如果n=0,返回m的值作为结果，同时过程结束；否则，进入第二步。第二步：m除以n，将余数赋给r。第三步：将n的值赋给m，将r的值赋给n,返回第一步。或者这样描述这个算法：AlgorithmEuclid(m,n)whilen≠0dormmodnmnnrreturnm(PS：这个算法会结束吗？）2020/1/8CentralSouthUniversity23SecondTryforgcd(m,n)：连续整数检测算法：第一步：将min{m,n}的值赋给t;第二步：m除以t,如果余数为0，进入第三步，否则，进入第四步。第三步：n除以t,如果余数为0,返回t的值作为结果；否则，进入第四步。第四步：把t的值减1，返回第二步。QuestionsWhichalgori