《算法201301-引论》由会员分享，可在线阅读，更多相关《算法201301-引论（72页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计,马炳先 ise_ （O）82765957 12教-901房间 济南大学信息科学与工程学院计算机科学系,Design and Analysis of Algorithm,四个基本问题,1什么是算法？ 2什么是算法分析与设计？ 3为什么学习算法分析与设计？ 4如何学好算法分析与设计？,1什么是算法？,什么是程序？,计算机程序是一组指令(及指令参数)的组合，这组指令依据既定的逻辑控制计算机的运行。,程序设计方法,Q：你已学习过的程序设计语言有那些？ Q：你已掌握的程序设计语言是那些？,如何编写程序？,？什么是程序,计算机程序是一组指令(及指令参数)的组合，这组指令依据既定的逻辑控制计
2、算机的运行。,既定逻辑就是指令运行的规则,程序员处理该问题的思路,算法,？什么是程序,1什么是算法？,一个算法是求解某一类特定问题的一组有穷规则的集合。 1）一个算法是一组规则，通常称之为算法步骤；这组规则是有穷的，即能用有限的形式表示出来。 2）一个算法是针对一类问题而设计的。,一个问题？,实例化！,1什么是算法？,计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述。,通俗一点：,程序是算法用某种程序设计语言的具体实现,程序=算法+数据结构,1什么是算法？,1什么是算法？,算法的特征：,1 有限性 2 确定性 3
3、 可行性 4 输入 5 输出,算法中每条指令的执行次数有限，执行每条指令的时间也有限,组成算法的每条指令清晰、无歧义,组成算法的每条指令都是计算机可执行的,算法产生至少一个量作为输出,有零个或多个外部量作为算法的输入,高效性：执行速度快，占用资源少； 健壮性(Robustness) ： 对数据响应正确。,程序可以不满足算法的有限性,1 有限性 2 确定性 3 可行性 4 输入 5 输出,程序应该满足吗？,1什么是算法？,无限循环,四个基本问题,1什么是算法？ 2什么是算法分析与设计？ 3为什么学习算法分析与设计？ 4如何学好算法分析与设计？,2什么是算法分析与设计？,算法主要包含两个方面的内容
4、： 算法设计：主要研究怎样针对某一特定类型的问题设计出求解步骤。 算法分析：讨论所设计出来的算法步骤的正确性和复杂性。,2什么是算法分析与设计？,算法设计,研究怎样针对某一特定类型的问题设计出求解步骤。,同一问题有不同的求解方法，那个最好或比较好呢？,2什么是算法分析与设计？,算法分析,讨论所设计出来的算法步骤的正确性和复杂性。,正确性,解决问题，得到需要的结果,复杂性,算法分析工作可归结为两部分： 正确性证明：主要包括算法的可终止性（即对任意输入，算法的执行都可以在有限步内终止）和算法的执行结果（输出）与问题（问题类）的求解要求相符两方面的证明。 复杂性分析：指算法的执行所需要的时间量和空间
5、量的分析，其中对时间量的分析尤为重要。,2什么是算法分析与设计？,四个基本问题,1什么是算法？ 2什么是算法分析与设计？ 3为什么学习算法分析与设计？ 4如何学好算法分析与设计？,3 为什么学算法分析与设计？,1专业知识的基础 2 做编程的高手 3 做解决问题的高手 4 做发现问题的高手 5 成为业界专家的基础,计算机科学和计算机应用的核心，无论是计算机系统、系统软件的设计，还是为解决计算机的各种应用所作的设计都可归结到算法的设计。,1） 算法是计算机的灵魂 2）算法是数字机械化的一部分 3）锻炼思维 4）帮助理解什么是可行的，什么是不可行的,四个基本问题,1什么是算法？ 2什么是算法分析与设
6、计？ 3为什么学习算法分析与设计？ 4如何学好算法分析与设计？,4 如何学好算法分析与设计？,1 勤于思考,2 勤于动手,问题是多变的，透过问题看本质，算法基本的策略与思想也就集中而已，灵活的使用及组合就可以找到解决问题的有效算法，掌握的是思想和技巧，而不是固定的针对某个问题的算法。,一、四个基本问题,二、参考教材及教学计划,三、考核方式,算法分析与设计,四、算法描述方法,二、参考教材及教学计划,吴哲辉 崔焕庆 马炳先 吴振寰 编著 机械工业出版社,Introduction to Algorithms,【作 者】王晓东 【出 版 社】清华大学出版社,二、参考教材及教学计划,算法之道 邹恒明 机
7、械工业出版社 2010.2,考 核,学术： 考核形式：写读书报告 考核具体要求： 针对某一具体问题，通过对该问题不同求解方法的研究，分析问题求解的具体算法思想和设计思路，要求如下： 对涉及问题的理论意义或实用价值和研究现状进行完整的理 解与归纳； 对涉及问题的求解方法进行系统的归纳和评述； 对涉及问题的具体应用或求解方法提出自己的理解与思路； 按照科研论文的基本格式进行书写。,专业学位： 考核形式：闭卷考试 考核具体要求： 通过课堂学习及课下自学等方式，掌握算法的基本概念，基本的算法设计策略，复杂度分析的基本方法，了解图灵机及NP问题的基本内容，课程讲解其他基本内容，如Petri网，服务计算，
8、智能算法等。 考核成绩：百分制，以期末考试为主,教学内容,一、 算法设计与分析概论 二、算法设计基本方法 三、具体问题的算法设计 四、相关领域研究问题算法概述及讨论,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 m
9、ore 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
10、 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”,算法描述方法,对于设计出来的一类问题的求解步骤，需要一种表达方式，即算
11、法描述。,描述算法最合适的语言是介于自然语言和程序语言之间的伪语言（伪代码） 。,类PASCAL，类C，类JAVA,可使用任何表达能力强的方法使算法表达更加清晰和简洁，而不至于陷入具体的程序语言的某些细节。,算法描述方法-自然语言,1)起床。 2)吃早点。 3)上早自习。 4)上课 5) 吃午饭。 6)上课。 7)吃晚饭。 8)上晚自习。 9)睡觉。,学生一天的作息,算法描述方法-例子,Exp1 冒泡排序算法,算法的基本思想：轻者（小的元素）像气泡那样从水底往上浮。在排序过程中，从后面（理解为底部）开始，每次把相邻的两个元素作比较，当前面的元素大于后面的元素时，就交换它们的位置。这样，所有相邻
12、的元素比较一遍以后最小的元素就被交换到了最前面（浮到上面）。,下一轮？,算法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 求最大公约数的辗转相除算法。 基本思想：用小的数作除数，大的数作
13、为被除数，做除法求余，如果余数等于零，那么小的数就是两个数的最大公约数。,否则？,用小的数做被除数，余数作为除数，再做除法求余，如此辗转相除下去，直到余数等于零。,最后除数就是要求的原本两个数的最大公约数。,算法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的最大公约数。,in
14、t 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 re
15、al-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)
16、为某算法的计算时间，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)的一个下界函数也是一个上界函数。,时间复杂度计算表示,两个函
