《算法设计与分析第2版第1章课件.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析第2版第1章课件.ppt（24页珍藏版）》请在三一文库上搜索。
1、算法设计与分析,1,算法设计与分析第2版第1章,什么是算法？,算法组成 （1）问题 （2）规则 （3）结果,算法是解某一问题的一组有穷规则的集合。 算法是把输入转换成输出的一个计算序列。,2,算法设计与分析第2版第1章,课程概述,计算机系统中的任何软件，都是按一个个特定的算法来予以实现的。算法性能的好坏，直接决定了所实现软件性能的优劣。 如何判定一个算法的性能、用什么方法来设计算法、所设计的算法需要多少运行时间、多少存储空间，在实现一个软件时，这些都是必须要予以解决的。 因此，算法设计与分析是计算机科学与技术的一个核心问题，也是大学计算机专业本科生及研究生的一门重要的专业基础课程。,3,算法设
2、计与分析第2版第1章,课程内容,第一部分(1-2章)：基本概念和常用数学工具(6学时) 第二部分(3-11章)：基本理论和技术，包括排序、递归、分治、贪婪法、动态规划、回溯法、分支与限界、 随机算法、图和网络问题 (30学时) 第三部分：复习考试(4学时),4,算法设计与分析第2版第1章,教材与参考书,教材：郑宗汉、 郑晓明：算法设计与分析，清华大学出版社， 第2版，2011年7月 参考书：算法导论(原书第3版) ，Thomas H. Cormen，Charles E. Leiserson, Ronald L. Rivest, lifford Stein, 殷建平等译, 机械工业出版社, 第1
3、版，2013年7月,5,算法设计与分析第2版第1章,References,Thomas H. Cormen, Charles E. Leiserson, andRonald L. Rivest. Introduction to Algorithms, The MIT Press, 第二版, 2002. 卢开澄. 计算机算法导引（第二版）。清华大学出版社，2006. 王晓东. 计算机算法设计与分析，电子工业出版社，2001。 D. E. Knuth等. Art of the Computer Programming, Vol. 3, Addison-Wesley, 1973. A. V. Aho
4、, J. D. Ullman等. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. A. V. Aho, J. D. Ullman等. Data Structures and Algorithms. Addison-Wesley, 1983.4. S. Baase. Computer Algorithms: Introduction to Design and Analysis. Addison-Wesley, second edition, 1988. E. Horowitz and Sartaj Sa
5、hni. Fundamentals of Computer Algorithms. Computer Science Press, 1978,6,算法设计与分析第2版第1章,Journals,IEEE Transactions on Electronic Computers IEEE Transactions on Software Engineering IEEE Transactions on Data and Knowledge Engineering Acta Informatica SIAM Journal on Computing Journal of Computer and S
6、ystem Sciences Communication of the ACM Journal of the ACM BIT Information and Control ACM Computing Surveys Mathematics of Computation Information Processing Letters Theoretical Computer Science,7,算法设计与分析第2版第1章,Conferences,Annual ACM Symposium on Theory of Computing Annual IEEE Symposium on Foundat
7、ions of Computer Science ACM Annual Computer Science Conference Annual Symposium on Computational Geometry ACM Symposium on Parallel Algorithms and Architectures,8,算法设计与分析第2版第1章,学习要求,深刻理解每一类算法的思想及其实现 能熟练运用所学知识解决实际问题 培养提高计算思维能力,9,算法设计与分析第2版第1章,考核方式,Homework and Reading: 20% Final Exam (Written Test):
8、 80%,10,算法设计与分析第2版第1章,第1章 算法的基本概念 1.1 引言 1.1.1 算法的定义和特性 1.1.2 算法的设计和复杂性分析,11,算法设计与分析第2版第1章,1.1.1 算法的定义和特性,定义：算法是把输入转换成输出的一个计算序列。 特性： （1）输入 （2）输出 （3）有限性 （4）确定性 （5）可行性,12,算法设计与分析第2版第1章,1.1.1 算法的定义和特性,设计： 欧几里德算法,输入： 输出： 第一步: 第二步: 第三步: 第四步:,正整数m和n m和n的最大公约数 求余数r m%n if r = 0? yes 终止(n为答案) no 执行第三步。 m n,
9、 n r, 返回第一步。,最大公约数问题：求两个正整数m和n的最大公约数,输入： 一个算法有0个或多个输入，它是由外部提供的，作为算法开始执行前的初始值，或初始状态。 算法的输入是从特定的对象集合中抽取的。算法中有两个输入m、n，就是从正整数集合中抽取的。,输出： 一个算法有一个或多个输出，这些输出与输入有特定的关系，实际上是输入的某种函数。不同取值的输入，产生不同结果的输出。 算法中的输出是输入m、n的最大公约数。,有限性： 算法在执行有限步之后必须终止。 算法（欧几里德算法）中，对输入的任意正整数m、n，将m除以n的余数赋予r之后，再通过r赋予n，从而使n值变小。如此往复进行，最终或者使r
10、为0，或者使n递减为1。这两种情况，都最终使r=0，而使算法终止。,确定性： 算法的每一个步骤，都有精确的定义。要执行的每一个动作都是清晰的、无歧义的。 例如，在算法的第3行中，如果m、n是无理数，那么，m除以n的余数就没有一个明确的界定。确定性的准则意味着必须确保在执行第3行时，m和n的值都是正整数。 算法规定了m、n都是正整数，从而保证了后续各个步骤中都能确定地执行。,可行性： 算法中所有待实现的运算，都是基本的运算。原则上可以由人们用纸和笔，在有限的时间里精确地完成。 算法中整除、判断、赋值等等运算都是可行的。因为整数可以用有限的方式表示。 如果所涉及的数值必须由展开成无穷小数的实数来精
11、确地完成，则这些运算就不是可行的了。,注意： 有限性的限制是不够的。 一个实用的算法，不仅要求步骤有限，同时要求运行这些步骤所花费的时间是人们可以接受的。,特性： （1）输入 （2）输出 （3）有限性 （4）确定性 （5）可行性,13,算法设计与分析第2版第1章,1.1 引言 1.1.1 算法的定义和特性 1.1.2 算法的设计和复杂性分析,14,算法设计与分析第2版第1章,1.1.2 算法的设计和复杂性分析,过程,15,算法设计与分析第2版第1章,1.1.2 算法的设计和复杂性分析,例1 百鸡问题： 公鸡每只5元、母鸡每只3元、小鸡3只1元，用100元钱买100只鸡，求公鸡、母鸡、小鸡的只数
12、。 令a为公鸡数， 为b母鸡数，c 为小鸡数，则： （1.1.1） （1.1.2） （1.1.3）,16,算法设计与分析第2版第1章,1. void chicken_question(int n, int 13. 14. 15. 16. 17. ,百鸡问题的穷举法,输入：所购买的3种鸡的总数目n 输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g,m,s,分析发现：只能买到n/5只公鸡，n/3只母鸡，将算法进行改进。,1.1.2 算法的设计和复杂性分析,17,算法设计与分析第2版第1章,百鸡问题的穷举法改进,输入：所购买的3种鸡的总数目n 输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g
13、,m,s,1. void chicken_question_2(int n, int 15. 16. ,1.1.2 算法的设计和复杂性分析,18,算法设计与分析第2版第1章,1.1.2 算法的设计和复杂性分析,例2 货郎担问题： 售货员到若干个城市去售货，每个城市仅经过一次，最后回到出发点。已知各个城市之间的距离，求一个总路程最短的路线。,最短路径的哈密尔顿回路问题，数据结构是无向加权图G = ，V是顶点集合，E是距离集合。,19,算法设计与分析第2版第1章,货郎担问题的穷举法算法,输入：城市个数n，费用(距离)矩阵c 输出：旅行路线t，最小费用min,1. void salesman_pro
14、blem(int n, float 14. 15. ,n!,1.1.2 算法的设计和复杂性分析,20,算法设计与分析第2版第1章,货郎担问题的执行时间和问题规模的关系,（假定循环体每执行一次，需要1s时间）,1.1.2 算法的设计和复杂性分析,21,算法设计与分析第2版第1章,思考,从百鸡问题的穷举法改进，可以得到什么启示？ 从货郎担问题的穷举算法时间消耗和问题规模的关系，可以得到什么启示？ 什么是一个有效的算法？如何判断某个算法更加有效？,说明了改进算法的设计方法对提高算法性能是非常重要的。,说明了穷举法对于一个不太大的（货郎担问题），都是行不通的。,如果一个问题有2个算法，如何知道这一个算法比另一个算法更有效？涉及下次课的时间、空间复杂性分析。,1.1.2 算法的设计和复杂性分析,22,算法设计与分析第2版第1章,小结,算法的定义和特征 算法的设计和复杂性分析,23,算法设计与分析第2版第1章,作业,查阅有关算法的研究动态，了解本节所列出的部分参考书目、期刊和会议。,24,算法设计与分析第2版第1章,