算法201301-引论.ppt

算法分析与设计,马炳先 ise_ （O）82765957 12教-901房间 济南大学信息科学与工程学院计算机科学系,Design and Analysis of Algorithm,四个基本问题,1什么是算法？ 2什么是算法分析与设计？ 3为什么学习算法分析与设计？ 4如何学好算法分析与设计？,1什么是算法？,什么是程序？,计算机程序是一组指令(及指令参数)的组合，这组指令依据既定的逻辑控制计算机的运行。,程序设计方法,Q：你已学习过的程序设计语言有那些？ Q：你已掌握的程序设计语言是那些？,如何编写程序？,？什么是程序,计算机程序是一组指令(及指令参数)的组合，这组指令依据既定的逻辑控制计算机的运行。,既定逻辑就是指令运行的规则,程序员处理该问题的思路,算法,？什么是程序,1什么是算法？,一个算法是求解某一类特定问题的一组有穷规则的集合。 1）一个算法是一组规则，通常称之为算法步骤；这组规则是有穷的，即能用有限的形式表示出来。 2）一个算法是针对一类问题而设计的。,一个问题？,实例化！,1什么是算法？,计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述。,通俗一点：,程序是算法用某种程序设计语言的具体实现,程序=算法+数据结构,1什么是算法？,1什么是算法？,算法的特征：,1 有限性 2 确定性 3 可行性 4 输入 5 输出,算法中每条指令的执行次数有限，执行每条指令的时间也有限,组成算法的每条指令清晰、无歧义,组成算法的每条指令都是计算机可执行的,算法产生至少一个量作为输出,有零个或多个外部量作为算法的输入,高效性：执行速度快，占用资源少； 健壮性(Robustness) ： 对数据响应正确。,程序可以不满足算法的有限性,1 有限性 2 确定性 3 可行性 4 输入 5 输出,程序应该满足吗？,1什么是算法？,无限循环,四个基本问题,1什么是算法？ 2什么是算法分析与设计？ 3为什么学习算法分析与设计？ 4如何学好算法分析与设计？,2什么是算法分析与设计？,算法主要包含两个方面的内容： 算法设计：主要研究怎样针对某一特定类型的问题设计出求解步骤。 算法分析：讨论所设计出来的算法步骤的正确性和复杂性。,2什么是算法分析与设计？,算法设计,研究怎样针对某一特定类型的问题设计出求解步骤。,同一问题有不同的求解方法，那个最好或比较好呢？,2什么是算法分析与设计？,算法分析,讨论所设计出来的算法步骤的正确性和复杂性。,正确性,解决问题，得到需要的结果,复杂性,算法分析工作可归结为两部分： 正确性证明：主要包括算法的可终止性（即对任意输入，算法的执行都可以在有限步内终止）和算法的执行结果（输出）与问题（问题类）的求解要求相符两方面的证明。 复杂性分析：指算法的执行所需要的时间量和空间量的分析，其中对时间量的分析尤为重要。,2什么是算法分析与设计？,四个基本问题,1什么是算法？ 2什么是算法分析与设计？ 3为什么学习算法分析与设计？ 4如何学好算法分析与设计？,3 为什么学算法分析与设计？,1专业知识的基础 2 做编程的高手 3 做解决问题的高手 4 做发现问题的高手 5 成为业界专家的基础,计算机科学和计算机应用的核心，无论是计算机系统、系统软件的设计，还是为解决计算机的各种应用所作的设计都可归结到算法的设计。,1） 算法是计算机的灵魂 2）算法是数字机械化的一部分 3）锻炼思维 4）帮助理解什么是可行的，什么是不可行的,四个基本问题,1什么是算法？ 2什么是算法分析与设计？ 3为什么学习算法分析与设计？ 4如何学好算法分析与设计？,4 如何学好算法分析与设计？,1 勤于思考,2 勤于动手,问题是多变的，透过问题看本质，算法基本的策略与思想也就集中而已，灵活的使用及组合就可以找到解决问题的有效算法，掌握的是思想和技巧，而不是固定的针对某个问题的算法。,一、四个基本问题,二、参考教材及教学计划,三、考核方式,算法分析与设计,四、算法描述方法,二、参考教材及教学计划,吴哲辉 崔焕庆 马炳先 吴振寰 编著 机械工业出版社,Introduction to Algorithms,【作 者】王晓东 【出 版 社】清华大学出版社,二、参考教材及教学计划,算法之道 邹恒明 机械工业出版社 2010.2,考 核,学术： 考核形式：写读书报告 考核具体要求： 针对某一具体问题，通过对该问题不同求解方法的研究，分析问题求解的具体算法思想和设计思路，要求如下： 对涉及问题的理论意义或实用价值和研究现状进行完整的理 解与归纳； 对涉及问题的求解方法进行系统的归纳和评述； 对涉及问题的具体应用或求解方法提出自己的理解与思路； 按照科研论文的基本格式进行书写。,专业学位： 考核形式：闭卷考试 考核具体要求： 通过课堂学习及课下自学等方式，掌握算法的基本概念，基本的算法设计策略，复杂度分析的基本方法，了解图灵机及NP问题的基本内容，课程讲解其他基本内容，如Petri网，服务计算，智能算法等。 考核成绩：百分制，以期末考试为主,教学内容,一、 算法设计与分析概论 二、算法设计基本方法 三、具体问题的算法设计 四、相关领域研究问题算法概述及讨论,Algorithm vs. Computer Science,Sometimes people ask: “What really is computer science? Why dont we have telephone science? Telephone, it might be argued, are as important to modern life as computer are, perhaps even more so. A slightly more focused question is whether computer science is not covered by such classical disciplines as mathematics, physics, electrical engineering, linguistics, logic and philosophy. We would do best not to pretend that we can answer these questions here and now. The hope, however, is that the course will implicitly convey something of the uniqueness and universality of the study of algorithm, and hence something of the importance of computer science as an autonomous field of study. - adapted from Harel: “Algorithmics, the Spirit of Computing”,算法描述方法,对于设计出来的一类问题的求解步骤，需要一种表达方式，即算法描述。,描述算法最合适的语言是介于自然语言和程序语言之间的伪语言（伪代码） 。,类PASCAL，类C，类JAVA,可使用任何表达能力强的方法使算法表达更加清晰和简洁，而不至于陷入具体的程序语言的某些细节。,算法描述方法-自然语言,1)起床。 2)吃早点。 3)上早自习。 4)上课 5) 吃午饭。 6)上课。 7)吃晚饭。 8)上晚自习。 9)睡觉。,学生一天的作息,算法描述方法-例子,Exp1 冒泡排序算法,算法的基本思想：轻者（小的元素）像气泡那样从水底往上浮。在排序过程中，从后面（理解为底部）开始，每次把相邻的两个元素作比较，当前面的元素大于后面的元素时，就交换它们的位置。这样，所有相邻的元素比较一遍以后最小的元素就被交换到了最前面（浮到上面）。,下一轮？,算法1.1 冒泡排序 输入：待排序数组A，其中有n个元素； 输出：排好序的数组A。 bubblesort(float A, int n) int i,j; for (i=0; ii; j-) if (AjAj-1) swap(Aj, Aj-1); ,算法1.2 元素交换 输入：待交换元素的位置x和y； 输出：交换后的结果仍存于x和y中。 swap(float *x, float *y) float u = *x; *x = *y; *y = u; ,例1.2 求最大公约数的辗转相除算法。 基本思想：用小的数作除数，大的数作为被除数，做除法求余，如果余数等于零，那么小的数就是两个数的最大公约数。,否则？,用小的数做被除数，余数作为除数，再做除法求余，如此辗转相除下去，直到余数等于零。,最后除数就是要求的原本两个数的最大公约数。,算法1.3 求最大公约数的辗转相除法 输入：两整数m和n； 输出：m和n的最大公约数。,int gcd(int m, int n) int a=maxm,n; int b=minm,n; int c;,while (b!=0) c=a mod b;,a=b; b=c; ,return ( ); ,a,算法1.4 求最大公约数的递归算法 输入：两整数m和n； 输出：m和n的最大公约数。,int gcd(int m, int n) int a=maxm,n; int b=minm,n; int c; if (b = 0) return (a); else c=a mod b; return( gcd(b,c) ); ,gcd(a,b)= gcd(b,a mod b),算法复杂度分析,Q1：如何评价一个算法的优劣？,Q2：算法转化为程序运行后，影响程序运行的因素有哪些？,Q3：如何避免客观因素的影响呢？,Q4：为什么渐进时间复杂度？,正确性,时空特性,时空效率,算法稳定性、健壮性、实现难度,算法分析,1）能够终结；2）得到合理结果,速度是算法的灵魂,Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is “approximately” the best is good enough.,时间复杂度概念,时间频度T(n),一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。 一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。 一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。,时间复杂度计算表示,假设f(n)为某算法的计算时间，n是问题的大小，g(n)是事先确定的简单函数，如：nm， 2n， n!。 定义1-1 如果存在两个正常数c和n0，对所有nn0，有 |f(n)|c|g(n)| 则记作：f(n)=O(g(n), O为数量级（阶数）， g(n)是计算时间f(n)的一个上界函数， f(n)的数量级是g(n) 。,定理1-1 若 是一个m次多项式，则 证明：（？） 说明：变量n的阶数为m的多项式与其最高阶同阶。,时间复杂度计算表示,定义1（2）（下界函数）如果存在两个正常数c和n0，对所有nn0，有 |f(n)|c|g(n)| 则记作：f(n)= (g(n)， g(n)是计算时间f(n)的一个下界函数。,定义1（3）（双界函数）如果存在两个正常数c1，c2和n0，对所有nn0，有 则： 说明： g(n)既是计算时间f(n)的一个下界函数也是一个上界函数。,时间复杂度计算表示,两个函数阶数的比较方法有如下结论： 假设 有下列情况： （1）如果L=a，a是有限正常数，则 ； （2）如果L=0，则 f(n)的阶数比g(n)低（)；,由此可以得到数量级的大小比较： （多项式时间算法与指数时间算法）,紧凑上、下界,洛必达法则,时间复杂度的几个相关问题,问题1 算法耗费的时间和语句频度 一个算法耗费的时间=算法中每条语句的执行时间之和 每条语句的执行时间=语句的执行次数（frequency count）语句执行一次所需时间,算法转化为程序后，每条语句的执行时间取决于：机器的指令性能，速度以及编译所产生的代码质量等难以确定的因素,一般分析时是独立于机器的软硬件系统分析算法的复杂性，即设每条语句执行一次的时间均为单位时间,一个算法的时间耗费就是该算法中所有语句的频度和,例1-1 （矩阵乘法）求两个n阶方阵A，B的乘积C Void MatrixMultiply(int Ann, int Bnn, int Cnn) int i,j,k; For (i=0;in;i+) for (j=0;jn;j+) Cij=0; for (k=0;kn;k+) Cij=cij+Aik Bkj ,其渐近时间复杂度： ，T(n)的数量级是n3，即T(n)=O(n3)。,频度：n+1，循环执行n次,n(n+1),n2,n2(n+1),n3,频度和=n+1+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1=T(n),问题2 用渐近时间复杂度评价算法的时间性能,例1-2 设有算法A1和A2求解同一问题，时间复杂度分别为 。,容易看出它们的渐近时间复杂度为O(n2)与O(n3)，宏观地评价了这两个算法在时间方面的质量。约定不区分时间复杂度和渐近时间复杂度，常用渐近时间复杂度评价算法的时间性能。,（2）随着问题规模n的增大，两个算法的时间开销比为： 亦随之增大，,（1）当输入量n20时，有,说明当问题规模比较大的时候， A1比A2有效的多。,问题3 算法的时间复杂度不仅仅依赖于问题的规模，还要与输入实例的初始状态有关（算法工作量）,例1-3 对于在数组 中查找给定值k的算法，大致如下： （1）i=n-1; (2)while(i0 ,语句（3）的频度不仅与问题规模n有关，而且与输入实例中A的各元素取值及k的取值有关,(1)若A中没有与k相等元素，则语句(3)的频度f(n)=n;,(2)若A中最后一个元素等于k,则语句(3)的频度f(n)=0；,问题4 最坏时间复杂度与平均时间复杂度,最坏情况下的时间复杂度是：算法在任何输入实例上的运行时间上的上界，保证了算法运行时间不会比任何更长； 平均情况下的时间复杂度是：所有可能的输入实例均以等概率的出现的情况下，算法的期望运行时间。 时间复杂度和空间复杂度统称为算法的复杂度。,是要快的计算机还是要快的算法？,“天河一号”为我国首台千万亿次超级计算机,每秒钟1206万亿次的峰值速度和每秒563.1万亿次的Linpack实测性能，使这台名为“天河一号”的计算机位居同日公布的中国超级计算机前100强之首，也使中国成为继美国之后世界上第二个能够自主研制千万亿次超级计算机的国家。 这个速度意味着，如果用“天河一号”计算一秒，则相当于全国13亿人连续计算88年。如果用“天河一号”计算一天，一台当前主流微机得算160年。“天河一号”的存储量，则相当于4个国家图书馆藏书量之和。,天河二号？,2 算法终止性证明-良序原则,利用良序原则证明依赖于可数集合的命题P(x)。 良序关系 设是集合S上的一个良序关系，如果满足以下性质： （1）给定集合S中元素x,y,z，如果xy，yz，则xz。 （2）给定集合S中元素x,y，以下三种可能性恰有一种为真： xy，x=y，yx （3）如果A是S的任何非空子集，则A中必有一个元素x，使得对于A中所有的y，有xy。,例如：自然数集合对于小于（）关系良序。,性质（3）说明：任何一个非空的良序集合都有一个最小元素。（整数，实数集合？）,良序原则,命题1 是集合S的一个良序，当且仅当它满足性质（1）和（2），并且对于所有的j1，不存在具有xj+1xj的无限序列 证明：,（ ）设是集合S的良序，如果存在这样的一个序列，则由该序列成员组成的集合A是集合S的一个非空子集，A不满足性质（3），与是集合S的良序矛盾。,这样就可以在A中找到存在具有xj+1xj的无限序列 。与给定条件矛盾，故假设错误， 是集合S的一个良序。证毕。,（ ）若满足（1），（2）但不满足（3）。设A是S一个没有最小元素的非空子集。由于A非空，所以可以找到 ,由于A中无最小元素，故有 ，由于x2也不是最小元素，可以同样找到,算法终止性证明,说明：命题1可以用来证明算法的终止性：如果能够把一个计算的各个状态映射到一个良序集S，使得计算的每一个步骤总是从一个状态x进入到另一个状态y，并且有f(y)f(x)，则此算法必定终止。GRID格,良序原则,命题2 设是集合S的一个良序，并且设p(x)是关于S元素x的一个命题。如果p(x)能在p(y)对于所有的yx为真的假定下得证，则p(x)对S中所有的x为真。,理论上说明算法终止性是可以证明的。,命题2是数学归纳法的推广，若S为自然数，则就是一般的简单的数学归纳法。,证明：命A是使得p(x)为假的所有x的集合。如果A非空，A对于为良序，则A含有一个最小元素x0，因此p(y)对于所有y x0为真。但这说明p(x0)为真，所以x0不在A中（因为A是使得p(x)为假的所有x的集合），与假设矛盾，因此A必须为空，即p(x)总是为真。,Lattice 格,对任意一个偏序集来说, 其中每一对元素不一定都有最大下界或最小上界。 设是一个偏序集, 如果A中任意两个元素均有最小上界和最大下界, 那么就说A关于偏序“”作成一个格(Lattice), 或直接称A为格。,递归算法,递归算法，就是把一个输入规模较大的问题转化为一个输入规模较小的同类问题，并反复进行这种转化，直到输入规模小到可以直接求解为止。,递归算法的时间复杂度对应为相应的递归关系式,3 递归关系式的求解,例：梵塔问题,A,B,C,递归关系：h(n)=2h(n-1)+1 初始条件：h(1)=1,据说在东方的古国印度土地上，有一座印度教的神庙，这庙有一块黄铜板，板上插著三根细细的、镶上宝石的细针，细针像菜叶般粗，而高就像成人由手腕到肘关节的长。 当印度教的主神梵天在创造地球这个世界时，就在其中的一根针上从下到上放了半径由大到小的六十四片圆金片环，这就是有名的梵塔或称汉内塔（Towers of Hanoi）。 天神梵天要这庙的僧侣，把这些金片全部由一根针移到另外一根指定的针上，一次只能移一片，不管在什么情况下，金片环的大小次序不能变更，小金片环永远只能放在大金片环上面。 只要有一天这六十四片的金环能从指定的针上完全转移到另外指定的针上，世界末日就来到，芸芸众生、神庙一切都将消灭，万物尽入极乐世界去。,递归关系的求解-生