通信网络理论基础-关于算法.pptx

通信网理论基础,虞红芳 教授 博导,Part 02: 关于算法(Intro to Algorithm),2013年春季,2 / 30,关于算法,1,2,3,4,算法的基本概念,算法的设计方法,算法的分析方法,算法的应用与实现,Algorithms are the “stuff” of computer science: they are central objects of study in many, if not most, areas of the field. - ROBERT SEDGEWICK “Algorithms”,3 / 30,算法的基本概念,名称的来历,1,2,3,算法是什么,算法的分类,2013年春季,2013年春季,4 / 30,Algorithm的由来,5 / 30,算法是什么？,2013年春季,6 / 30,历史上三大算法,1、求最大公约数的欧几里得算法,2、求素数的埃拉托塞尼筛法,3、求方根的开方算法,X_(n+1)=X_n+【A/(X_n（k-1）)-X_n】1/k,算法的分类,应用,2013年春季,8 / 30,关于算法,2,3,4,算法的设计方法,算法的分析方法,算法的应用与实现,算法的应用是如此广泛，面对的问题千奇百怪，那么，算法岂不是只能case-by-case地设计？难道其中还有些什么共同的，统一的设计方法么？,2013年春季,9 / 30,算法的设计方法,4,Divide and Conquer,1,2,3,5,Dynamic Programming,Greedy Algorithm,Exhaustive Search,Local Search/Metaheuristic,2013年春季,10 / 30,Divide and Conquer,2013年春季,11 / 30,折半查找 请查错，并修改 Hint : 以A = 2,5,9 x = 5为例来思考。,伪码及实例,2013年春季,12 / 30,算法的设计方法,4,Divide and Conquar,1,2,3,5,Dynamic Programming,Greedy Algorithm,Exhaustive Search,Local Search/Metaheuristic,2013年春季,13 / 30,Dynamic Programming,Dynamic Programming is a fancy name for Divide and Conquer with a TABLE.,2013年春季,14 / 30,0-1背包问题的DP算法,2013年春季,15 / 30,0-1背包问题的DP算法,X,X,X,X,O,X,X,X,X,X,X,O,O,O,O,O,O,O,O,X,X,X,X,X,X,X,X,X,X,O,O,O,X,X,O,O,O,O,O,O,2013年春季,16 / 30,算法的设计方法,4,Divide and Conquar,1,2,3,5,Dynamic Programming,Greedy Algorithm,Exhaustive Search,Local Search/Metaheuristic,2013年春季,17 / 30,Greedy Algorithm,2013年春季,18 / 30,贪婪算法的例子,2013年春季,19 / 30,算法的设计方法,4,Divide and Conquar,1,2,3,5,Dynamic Programming,Greedy Algorithm,Exhaustive Search,Local Search/Metaheuristic,2013年春季,20 / 30,Exhaustive Search,2013年春季,21 / 30,算法的设计方法,4,Divide and Conquar,1,2,3,5,Dynamic Programming,Greedy Algorithm,Exhaustive Search,Local Search/Metaheuristic,2013年春季,22 / 30,Local Search/Metaheuristics,2013年春季,23 / 30,小结纯属个人观点,2013年春季,24 / 30,关于算法,3,4,算法的分析方法,算法的应用与实现,我们将学习很多算法，也将会去设计自己的算法。但是，我怎么知道这些算法真的能达到目标？另外，同样能达到相同目标的多个算法，我应该怎么选择？,2013年春季,25 / 30,算法的分析,2013年春季,26 / 30,Complexity,2013年春季,27 / 30,复杂度分析实例,2013年春季,28 / 30,关于算法,4,算法的应用与实现,我们已经学习了算法的设计和分析，那么，在实现算法的时候，有没有什么需要注意的呢？,2013年春季,29 / 30,算法的应用与实现,3个忠告：关于如何使用/设计/挑选算法来解决实际问题。,2013年春季,30 / 30,小结(Part 02),D&C, DP, Greedy Exhaustive Search Metaheuristics,三个忠告,求解问题的过程,正确性 复杂度,希望大家通过上述内容的学习，对于算法有一个全景式的了解。并懂