算法设计与分析第 郑宗汉 PPT课件

什么是算法？1o 算法组成n（1）问题n（2）规则n（3）结果o 算法是解某一问题的一组有穷规则的集合。o 算法是把输入转换成输出的一个计算序列。第1页/共24页课程概述 计算机系统中的任何软件，都是按一个个特定的算法来予以实现的。算法性能的好坏，直接决定了所实现软件性能的优劣。 如何判定一个算法的性能、用什么方法来设计算法、所设计的算法需要多少运行时间、多少存储空间，在实现一个软件时，这些都是必须要予以解决的。 因此，算法设计与分析是计算机科学与技术的一个核心问题，也是大学计算机专业本科生及研究生的一门重要的专业基础课程。2第2页/共24页课程内容 第一部分(1-2章)：基本概念和常用数学工具(6学时) 第二部分(3-11章)：基本理论和技术，包括排序、递归、分治、贪婪法、动态规划、回溯法、分支与限界、 随机算法、图和网络问题 (30学时) 第三部分：复习考试(4学时)3第3页/共24页教材与参考书 教材：郑宗汉、 郑晓明：算法设计与分析，清华大学出版社， 第2版，2011年7月 参考书：算法导论(原书第3版) ，Thomas H. Cormen，Charles E. Leiserson, Ronald L. Rivest, lifford Stein, 殷建平等译, 机械工业出版社, 第1版，2013年7月4第4页/共24页References5第5页/共24页Journals11.ACM Computing Surveys12.Mathematics of Computation13.Information Processing Letters14.Theoretical Computer Science6第6页/共24页Conferences7第7页/共24页学习要求 深刻理解每一类算法的思想及其实现 能熟练运用所学知识解决实际问题 培养提高计算思维能力8第8页/共24页考核方式9第9页/共24页10第1章 算法的基本概念o 1.1 引言n 1.1.1 算法的定义和特性n 1.1.2 算法的设计和复杂性分析第10页/共24页1.1.1 算法的定义和特性 定义：算法是把输入转换成输出的一个计算序列。 特性： （1）输入 （2）输出 （3）有限性 （4）确定性 （5）可行性11第11页/共24页 设计： 欧几里德算法12输入：输出：第一步: 第二步: 第三步:第四步:正整数m和nm和n的最大公约数求余数r m%n if r = 0? yes 终止(n为答案) no 执行第三步。 m n, n r, 返回第一步。 1.1.1 算法的定义和特性最大公约数问题：求两个正整数m和n的最大公约数输入输入：一个算法有一个算法有0 0个或多个输入，它个或多个输入，它是由外部提供的，作为算法开是由外部提供的，作为算法开始执行前的初始值，或初始状始执行前的初始值，或初始状态。态。算法的输入是从特定的对象集算法的输入是从特定的对象集合中抽取的。算法中有两个输合中抽取的。算法中有两个输入入m m、n n，就是从正整数集合中，就是从正整数集合中抽取的。抽取的。输出输出：一个算法有一个或多个输出，一个算法有一个或多个输出，这些输出与输入有特定的关系，这些输出与输入有特定的关系，实际上是输入的某种函数。不实际上是输入的某种函数。不同取值的输入，产生不同结果同取值的输入，产生不同结果的输出。的输出。算法中的输出是输入算法中的输出是输入m m、n n的最的最大公约数。大公约数。有限性有限性：算法在执行有限步之后必须终算法在执行有限步之后必须终止。止。算法（欧几里德算法）中，对算法（欧几里德算法）中，对输入的任意正整数输入的任意正整数m m、n n，将，将m m除除以以n n的余数赋予的余数赋予r r之后，再通过之后，再通过r r赋予赋予n n，从而使，从而使n n值变小。如此值变小。如此往复进行，最终或者使往复进行，最终或者使r r为为0 0，或者使或者使n n递减为递减为1 1。这两种情况，。这两种情况，都最终使都最终使r=0r=0，而使算法终止。，而使算法终止。确定性确定性：算法的每一个步骤，都有精确算法的每一个步骤，都有精确的定义。要执行的每一个动作的定义。要执行的每一个动作都是清晰的、无歧义的。都是清晰的、无歧义的。例如，在算法的第例如，在算法的第3 3行中，如果行中，如果m m、n n是无理数，那么，是无理数，那么，m m除以除以n n的余数就没有一个明确的界定。的余数就没有一个明确的界定。确定性的准则意味着必须确保确定性的准则意味着必须确保在执行第在执行第3 3行时，行时，m m和和n n的值都是的值都是正整数。正整数。算法规定了算法规定了m m、n n都是正整数，都是正整数，从而保证了后续各个步骤中都从而保证了后续各个步骤中都能确定地执行。能确定地执行。可行性可行性：算法中所有待实现的运算，都算法中所有待实现的运算，都是基本的运算。原则上可以由是基本的运算。原则上可以由人们用纸和笔，在有限的时间人们用纸和笔，在有限的时间里精确地完成。里精确地完成。算法算法中整除、判断、赋值等等中整除、判断、赋值等等运算都是可行的。因为整数可运算都是可行的。因为整数可以用有限的方式表示。以用有限的方式表示。如果所涉及的数值必须由展开如果所涉及的数值必须由展开成无穷小数的实数来精确地完成无穷小数的实数来精确地完成，则这些运算就不是可行的成，则这些运算就不是可行的了。了。注意：注意：有限性的限制是不够的。有限性的限制是不够的。一个实用的算法，不仅要求步骤一个实用的算法，不仅要求步骤有限，同时要求运行这些步骤所有限，同时要求运行这些步骤所花费的时间是人们可以接受的。花费的时间是人们可以接受的。特性：特性：（1）输入）输入（2）输出）输出（3）有限性）有限性（4）确定性）确定性（5）可行性）可行性第12页/共24页13o 1.1 引言n 1.1.1 算法的定义和特性n 1.1.2 算法的设计和复杂性分析第13页/共24页1.1.2 算法的设计和复杂性分析 过程14理解问题算法表示算法分析算法实现第14页/共24页 例1 百鸡问题： 公鸡每只5元、母鸡每只3元、小鸡3只1元，用100元钱买100只鸡，求公鸡、母鸡、小鸡的只数。 令a为公鸡数， 为b母鸡数，c 为小鸡数，则： （1.1.1） （1.1.2） （1.1.3）100abc53/ 3100abc%30c151.1.2 算法的设计和复杂性分析第15页/共24页1. void chicken_question(int n, int &k, int g, int m, int s)2. 3. int a,b,c;4. k = 0;5. for (a = 0; a = n; a+) 6. for ( b = 0; b = n; b+) 7. for (c = 0; c = n; c+) 8. if (a + b + c = n) & (5 * a + 3 * b + c / 3 = n) & (c%3 = 0) 9. gk = a;10. mk = b;11. sk = c;12. k+; 13. 14. 15. 16. 17. 百鸡问题的穷举法 输入：所购买的3种鸡的总数目n 输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g,m,s16分析发现：只能买到n/5只公鸡，n/3只母鸡，将算法进行改进。1.1.2 算法的设计和复杂性分析第16页/共24页 输入：所购买的3种鸡的总数目n 输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g,m,s1. void chicken_question_2(int n, int &k, int g, int m, int s)2. 3. int a,b,c;4. k = 0;5. i = n / 5;6. j = n / 3;7. for (a = 0; a = i; a+) 8. for ( b = 0; b = j; b+) 9. c = n a - b; / 原来为 for (c = 0; c = n; c+) 10. if (a + b + c = n) & (5 * a + 3 * b + c / 3 = n) & (c%3 = 0) 11. gk = a;12. mk = b;13. sk = c;14. k+; 15. 16. 百鸡问题的穷举法改进171.1.2 算法的设计和复杂性分析第17页/共24页 例2 货郎担问题： 售货员到若干个城市去售货，每个城市仅经过一次，最后回到出发点。已知各个城市之间的距离，求一个总路程最短的路线。18n最短路径的哈密尔顿回路问题，数据结构是无向加权图G = ，V是顶点集合，E是距离集合。1.1.2 算法的设计和复杂性分析第18页/共24页货郎担问题的穷举法算法 输入：城市个数n，费用(距离)矩阵c 输出：旅行路线t，最小费用min1. void salesman_problem(int n, float &min, int t, float c)2. 3. int pn, i = 1;4. float cost;5. min = MAX_FLOAT_NUM;6. while (i = n!) 7. 产生n个城市的第i个排列于p;8. cost = 路线p的费用；9. if (cost min) 10. 把数组p的内容复制到数组t；11. min = cost;12. 13. i+;14. 15. n!191.1.2 算法的设计和复杂性分析第19页/共24页货郎担问题的执行时间和问题规模的关系（假定循环体每执行一次，需要1s时间）201.1.2 算法的设计和复杂性分析第20页/共24页思考 从百鸡问题的穷举法改进，可以得到什么启示？ 从货郎担问题的穷举算法时间消耗和问题规模的关系，可以得到什么启示？ 什么是一个有效的算法？如何判断某个算法更加有效？21说明了改进算法的设计方法对提高算法性能是非常重要的。说明了穷举法对于一个不太大的（货郎担问题），都是行不通的。如果一个问题有2个算法，如何知道这一个算法比另一个算法更有效？涉及下次课的时间、空间复杂性分析。1.1.2 算法的设计和复杂性分析第21页/共24页小结算法的定义和特征算法的设计和复杂性分析22第22页/共24页作业 查阅有关算法的研究动态，了解本节所列出的部分参考书目、期刊和会议。23第23页/共24页24感谢您的观看！第24页/共24页