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

《通信网络理论基础-关于算法-2013》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、通信网理论基础虞红芳教授博导Part02:关于算法(IntrotoAlgorithm)2013年春季2/30关于算法1234算法的基本概念算法的设计方法算法的分析方法算法的应用与实现Algorithmsarethe“stuff”ofcomputerscience:theyarecentralobjectsofstudyinmany,ifnotmost,areasofthefield.--------------ROBERTSEDGEWICK“Algorithms”3/30算法的基本概念名称的来历123算法是什么算法的分类2013年春季2013年

2、春季4/30Algorithm的由来Why?因为：一个使得定量分析大众化了，另一个使得知识大众化了。1448=MCDXLVIIIAlgorithmTohonorthewiseArabian:AlKhwarizmiAD600十进制计数法及其符号在印度(注意，不是阿拉伯)被发明。DecimalNineCenturyAlKhwarizmi(Baghdad)写了一本介绍十进制以及相应的四则运算(甚至还包括求平方根和求PIE)方法的阿拉伯文教材。并在很多个世纪之后被介绍到了西方。Algorithm1448一个Mainz(德国城市)的金匠，JohannGu

3、tenberg，发明了金属活字印刷。TypographyTheDarkAgesended,thehumanintellectwasliberated,scienceandtechnologytriumphed,theIndustrialRevolutionhappened.Twoideaschangedtheworld因为那些计算方法具有“算法”的一切特征：Precise/Unambiguous/Mechanical/Efficient/CorrectWhy?5/30算法是什么？求解问题的一个过程(Procedure)。算法过程由一系列步骤构成

4、，其中每个步骤都是简单的，无歧义的，容易实现的。给定任意实例，都能给出所要求的结果。求解对一系列(甚至无穷多个)实例的统一/无歧义的描述。由输入(给定条件)和输出(待求结果)组成。对一系列(甚至无穷多个)实例的统一/无歧义的描述。由输入(给定条件)和输出(待求结果)组成。问题问题给定一组整数，求其中最大值。过程比较前2个数的大小，较大者与第3个比；…例子2013年春季6/30历史上三大算法1、求最大公约数的欧几里得算法2、求素数的埃拉托塞尼筛法3、求方根的开方算法X_(n+1)={X_n+【A/(X_n^（k-1）)-X_n】1/k}7/30算

5、法的分类串处理(String)数学：算术；随机数；高斯消元；几何；求积分；曲线拟合。排序(Sorting)图(Graph)其他：FFT；线性规划；等等。查找(Searching)应用2013年春季8/30关于算法2341算法的基本概念算法的设计方法算法的分析方法算法的应用与实现算法的应用是如此广泛，面对的问题千奇百怪，那么，算法岂不是只能case-by-case地设计？难道其中还有些什么共同的，统一的设计方法么？2013年春季9/30算法的设计方法4DivideandConquer1235DynamicProgrammingGreedyAlgo

6、rithmExhaustiveSearchLocalSearch/Metaheuristic2013年春季10/30DivideandConquer将原问题分解为规模较小的子问题由于所有拆分出来的子问题都是相同性质的，因此可以方便地用递归(Recursion)方式来实现。Divide如果子问题仍然困难，就继续对子问题进行分解。直到最终分解得到的子问题变得容易“征服”(trivial)。Conquer将子问题的结果合并成原问题的解Combine例1求最大值在一组整数中求最大值。分成两组，分别求最大值，然后比较这两个值，较大者作为原问题的解。递归。

7、例2查找在一组升序整数中，查找某个特定的整数。折半查找。例3遍历在图中遍历所有的节点。深度优先遍历(DFS)2013年春季11/30折半查找请查错，并修改Hint:以A={2,5,9}x=5为例来思考。伪码及实例Functionsearch(A,x,k,r)//findxinA[k...r]IFk=rTHENRETURN(k)ELSEm=(k+r)/2IFxA[m]THENRETURN(search(A,x,k,m))ELSERETURN(search(A,x,m,r))基于DC的求最大值Functionmaximum(S,x,y)//r

8、eturnmaximuminS[x...y]IFy–x1THENRETURN(max(S[x],S[y])ELSEm1=maximum(x,(x+