计算机算法概论优秀PPT

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,9,）,概率算法,10,）,近似算法,8,）,NP,完全性,6,）,回溯法,7,）,分支,-,限界法,学习要点:,理解算法的概念。,理解什么是程序，程序与算法的区分和内在联系。,驾驭算法的计算困难性概念。,驾驭算法渐近困难性的数学表述。,驾驭用C/C+语言描述算法的方法。,第一讲 算法概述,20世纪50年头，西方著名的词典中还未曾收录过算法(Algorithm)一词，据西方数学史家考证，Algorithm取自于古代阿拉伯学者的名著复原和化简的规则一书的作者的署名中的al-Khwarizmi，而从作品名字中的al-jabr派生出了Algebra(代数)一词。,随着时间的推移，Algorithm这个词的含义，已经完全不同于它原来的含义了。,一、什么是算法？,一个算法是一个有穷规则的集合。这些规则规定了解决某一问题的一个运算序列。同时，一个算法应当具有五个特性：有穷性、可行性、确定性、输入、输出。,1.有穷性：规则的有限性。或者说，求解问题的运算序列，必需在有限的计算步后停止。,2.,可行性：每一计算步都是基本的、可实现的。,3.,确定性：每一条规则都是明确、无二义的。,算法定义：,5.,输出（,1,）：算法产生与输入相关的量。,4.输入（0）：算法起先执行之前指定初始值。,二、算法的又一描述方式,设：四元组（Q,I,f ).,其中：Q:,状态集合,；,I,：Q,的子集，分别代表输入和输出,f:,定义在,Q之上的一个映射,。,且有：若q ，则：f(q)=q。,1.,描述,计算序列,：,若对于,I,的每一个输入,x,由,f,定义一个计算序列：,y,0,y,1,y,2,。,其中：,y,0,=x;y,k+1,=,f,(y,k,)(k 0),。,若一个计算序列在第,k,步终止，且,k,是使,y,K,的最小整数，则称,y,k,是由,x,产生的输出。,2.描述算法：,一个算法是对于I 中全部输入x,都能在有穷步内终止的一个计算序列。,f,0,y,1,Q,f,1,y,2,x ,I,y,k,f,k-1,三、程序,(Program),程序是算法用某种程序设计语言的具体实现。,程序可以不满足算法的性质(1)。,例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。,操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。,四、算法困难性分析,算法困难性=算法所须要的计算机资源,算法的时间困难性T(n)；,算法的空间困难性S(n)。,其中n是问题的规模（输入大小）。,算法的时间困难性,（1）最坏状况下的时间困难性,Tmax(n)=max T(I)|size(I)=n,（2）最好状况下的时间困难性,Tmin(n)=min T(I)|size(I)=n,（3）平均状况下的时间困难性,Tavg(n)=,其中I是问题的规模为n的实例，p(I)是实 例I出现的概率。,假设某算法的计算时间是f(n)，其中变量n可以是输入或输出量，也可以是两者之和，还可以是它们之一的某种测度(例如，数组的维数，图的边数等)。g(n)是在事前分析中确定的某个形式很简洁的函数，它是独立于机器和语言的函数，而f(n)则与机器和语言有关。,定义1.1 假如存在两个正常数c和n0,对于全部的n n0，有,|f(n)|c|g(n)|,记作f(n)=O(g(n),算法时间的渐近表示,当说一个算法具有O(g(n)的计算时间时，指的是假如此算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个上界函数，f(n)的数量级就是g(n)。当然，在确定f(n)的数量级时总是试图求出最小的g(n)，使得f(n)=O(g(n)。,证明：取n0=1,当n n0时，利用A(n)的定义和一个简洁的不等式，有,|A(n)|am|nm+|a1|n+|a0|,(|am|+|am-1|/n+|a0|/nm)nm,(|am|+|a0|)nm,选取c=|am|+|a0|，定理马上得证。,定理,1.1,若,A(n)=a,m,n,m,+a,1,n+a,0,是一个,m,次多项式，则,A(n)=O(n,m,),。,这个定理表明，变量,n,的固定阶数为,m,的任一多项式，与此多项式的最高阶,n,m,同阶。因此计算时间为,m,阶的多项式的算法，其时间都可用,O(n,m,),来表示。,事实上，只要将n0取得足够大，可以证明只要c是比|am|大的随意一个常数，此定理都成立。,从计算时间上可以把算法分成两类，凡可用多项式来对其计算时间限界的算法，称为,多项式时间算法,(polynomial time algorithm),；而计算时间用指数函数限界的算法称为,指数时间算法,(exponential time algorithm),。,指数时间算法一般有以下几种，它们关系为：,O(2,n,),O(n!),O(n,n,),以下六种计算时间的多项式时间算法是最为常见的，其关系为：,O(1),O(longn),O(n),O(nlongn),O(n,2,),O(n,3,),因此，只要有人能将现在指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个宏大的成就!,算法分析中常见的困难性函数,算法分析的基本法则,非递归算法：,（1）for/while 循环,循环体内计算时间*循环次数；,（2）嵌套循环,循环体内计算时间*全部循环次数；,（3）依次语句,各语句计算时间相加；,（4）if-else语句,if语句计算时间和else语句计算时间的较大者。,问题求解,(Problem Solving),证明正确性,分析算法,设计程序,理解问题,精确解或近似解,选择数据结构,算法设计策略,设计算法,五,、,算法设计的例子,穷举法,例,1.1,百鸡问题,公元,5,世纪末，数学家张丘建在,算经,中，提出这样一个问题：“鸡翁一，值钱五；鸡母一，值钱一；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何”。,令a为公鸡只数，b为母鸡只数，c为小鸡只数,a+b+c=100 (1),5a+3b+c/3=100 (2),c%3=0 (3),上述百鸡问题中，a、b、c的可能取值范围为0-100，对在此范围内的a、b、c的全部组合进行测试，凡是满足上述3个约束方程的组合，都是问题的解。,输入：所购买的3种鸡的总数目n,输出：满足问题的解的数目k，公鸡，母鸡，小鸡的只数g，m，s,void chicken_question(int n,int&k,int g,int m,int s),int a,b,c;,k=0;,for(a=0;a=n;a+),for(b=0;b=n;b+),for(c=0;c=n;c+)if(a+b+c=n)&(5*a+3*b+c/3=n)&(c%3=0),gk=a;,mk=b;,sk=c;,k+;,当n=100时，内循环体执行次数大于100万次,考虑到n元钱只可以买到n/5只公鸡，或n/3只母鸡，有些组合可以不必考虑。而小鸡的只数又与公鸡及母鸡的只数相关，内循环可以省去。,这样，算法1.1中可以改为：,void chicken_problem(int n,int&k,int g,int m,int s),int i,j,a,b,c;,k=0;,i=n/5;,j=n/3;,for(a=0;a=i;a+),for(b=0;b=j;b+),c=n-a-b;,if(5*a+3*b+c/3=n)&(c%3=0),gk=a;,mk=b;,sk=c;,k+,例,1.2,货郎担问题,某售货员要到若干个城市销售货物，已知各城市之间的距离，要求售货员选择动身的城市及旅行路途，使每一个城市仅经过一次，最终回到原动身城市，而总路程最短。,假如对随意数目的n个城市，分别用1-n的数字编号，这个问题归结为带权有向图中，找寻一条路径最短 的哈密尔顿回路问题。,思索：存储的实现方法,售货员的每一条路途，对应于城市编号1,2,n的一个排列。用一个数组来存放这个排列中的数据，数组中的元素依次存放旅行路途中的城市编号。,n个城市具有n!个排列，售货员共有n!条路途可供选择。接受穷举法逐一计算每一条路途的费用，从中找出费用最小的路途，便可求出问题的解。,算法1.3 穷举法版本的货郎担问题,输入：城市个数n，费用矩阵c,输出：旅行路途t，最小费用min,void salesman_problem(int n,float&min,int t,float c),int pn,i=1;,float cost;,min=MAx_FLoat_NUM;,while(i=n!),产生n个城市的第i个排列于p;,cost=路途p的费用；,if(cost0;i=1,2,n）。判定：是否存在一种装包方法，使装入背包物品的总效益大于K？,（,1,）计算机算法设计与分析 王晓东,电子工业出版社,2001,年,1,月第,1,版,（2）算法设计与分析 王晓东,清华高校出版社 2003年1月第1版,（3）计算机算法基础（其次版）余祥宣 等,华中理工高校出版社 2000年1月第1版,（,4,）算法导论 （,英文,，影印版）,参考书,*计算理论导引,Introduction to the Theory of Computation,（美）,Michael Sipser,著 麻省理工学院,张立昂等译 机械工业出版社,2000,年第一版,