算法201001-引论.ppt

《算法201001-引论.ppt》由会员分享，可在线阅读，更多相关《算法201001-引论.ppt（43页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、算法分析与设计算法分析与设计马炳先马炳先ise_（O）8276595712教教-906房间房间济南大学信息科学与工程学院计算机科学系济南大学信息科学与工程学院计算机科学系一、四个基本问题一、四个基本问题二、参考教材及教学计划二、参考教材及教学计划三、考核方式三、考核方式算法分析与设计算法分析与设计四、算法描述方法四、算法描述方法一、四个基本问题一、四个基本问题二、参考教材及教学计划二、参考教材及教学计划三、考核方式三、考核方式算法分析与设计算法分析与设计四、算法描述方法四、算法描述方法四个基本问题四个基本问题1什么是算法？什么是算法？2什么是算法分析与设计？什么是算法分析与设计？3为什么学习算

2、法分析与设计？为什么学习算法分析与设计？4如何学好算法分析与设计？如何学好算法分析与设计？1什么是算法？什么是算法？什么是程序？什么是程序？计算机计算机程序程序是一组指令是一组指令(及指令参数及指令参数)的组合，这的组合，这组指令依据既定的逻辑控制计算机的运行。组指令依据既定的逻辑控制计算机的运行。程序设计方法程序设计方法Q：你已学习过的程序设计语言有那些？：你已学习过的程序设计语言有那些？Q：你已掌握的程序设计语言是那些？你已掌握的程序设计语言是那些？如何编写程序？如何编写程序？1什么是算法？什么是算法？本科阶段至少本科阶段至少4 4万行代码万行代码计算机计算机程序程序是一组指令是一组指令(

3、及指令参数及指令参数)的组合，这的组合，这组指令依据组指令依据既定的逻辑既定的逻辑控制计算机的运行。控制计算机的运行。既定逻辑就是指令运行的规则既定逻辑就是指令运行的规则程序员处理该问题的思路程序员处理该问题的思路算法算法1什么是算法？什么是算法？1什么是算法？什么是算法？一个算法是求解某一类特定问题的一组一个算法是求解某一类特定问题的一组有穷规则有穷规则的的集合。集合。1）一个算法是一组规则，通常称之为算法步骤；）一个算法是一组规则，通常称之为算法步骤；这组规则是有穷的，即能用有限的形式表示出来。这组规则是有穷的，即能用有限的形式表示出来。2）一个算法是针对）一个算法是针对一类问题一类问题而

4、设计的。而设计的。一个问题？一个问题？程序程序inputoutput实例化！实例化！1什么是算法？什么是算法？计算机算法是以一步接一步的方式来详细描述计计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体者说，算法是对计算机上执行的计算过程的具体描述。描述。通俗一点：通俗一点：程序是算法用某种程序设计语言的具体实现程序是算法用某种程序设计语言的具体实现程序程序=算法算法+数据结构数据结构1什么是算法？什么是算法？算法的特征算法的特征：1有限性有限性2确定性确定性3可行性可行性4输

5、入输入5输出输出算法中每条指令的执行次数有限，执算法中每条指令的执行次数有限，执行每条指令的时间也有限行每条指令的时间也有限组成算法的每条指令清晰、无歧义组成算法的每条指令清晰、无歧义组成算法的每条指令都是计算机可执组成算法的每条指令都是计算机可执行的行的算法产生至少一个量作为输出算法产生至少一个量作为输出有零个或多个外部量作为算法的输入有零个或多个外部量作为算法的输入程序可以不满足算法的有限性程序可以不满足算法的有限性1有限性有限性2确定性确定性3可行性可行性4输入输入5输出输出程序应该满足吗？程序应该满足吗？1什么是算法？什么是算法？死循环死循环四个基本问题四个基本问题1什么是算法？什么是

6、算法？2什么是算法分析与设计？什么是算法分析与设计？3为什么学习算法分析与设计？为什么学习算法分析与设计？4如何学好算法分析与设计？如何学好算法分析与设计？2什么是算法分析与设计？什么是算法分析与设计？算法主要包含两个方面的内容：算法主要包含两个方面的内容：算法设计算法设计：主要研究怎样针对某一特定类型的：主要研究怎样针对某一特定类型的问题设计出求解步骤。问题设计出求解步骤。算法分析算法分析：讨论所设计出来的算法步骤的正确：讨论所设计出来的算法步骤的正确性和复杂性。性和复杂性。2什么是算法分析与设计？什么是算法分析与设计？算法设计算法设计研究怎样针对某一特定类型的问题设计出求解步骤。研究怎样针

7、对某一特定类型的问题设计出求解步骤。同一问题有不同的求解方法，同一问题有不同的求解方法，那个最好或比较好呢？那个最好或比较好呢？2什么是算法分析与设计？什么是算法分析与设计？算法分析算法分析讨论所设计出来的算法步骤的正确性和复杂性。讨论所设计出来的算法步骤的正确性和复杂性。正确性正确性解决问题，得到需要的结果解决问题，得到需要的结果复杂性复杂性n算法分析工作可归结为两部分算法分析工作可归结为两部分：n正确性证明正确性证明：主要包括算法的可终止性（即对：主要包括算法的可终止性（即对任意输入，算法的执行都可以在有限步内终止）任意输入，算法的执行都可以在有限步内终止）和算法的执行结果（输出）与问题（

8、问题类）和算法的执行结果（输出）与问题（问题类）的求解要求相符两方面的证明。的求解要求相符两方面的证明。n复杂性分析复杂性分析：指算法的执行所需要的时间量和：指算法的执行所需要的时间量和空间量的分析，其中对时间量的分析尤为重要空间量的分析，其中对时间量的分析尤为重要。2什么是算法分析与设计？什么是算法分析与设计？四个基本问题四个基本问题1什么是算法？什么是算法？2什么是算法分析与设计？什么是算法分析与设计？3为什么学习算法分析与设计？为什么学习算法分析与设计？4如何学好算法分析与设计？如何学好算法分析与设计？3为什么学算法分析与设计？为什么学算法分析与设计？1专业知识的基础专业知识的基础2做编

9、程的高手做编程的高手3做解决问题的高手做解决问题的高手4做发现问题的高手做发现问题的高手5成为业界专家的基础成为业界专家的基础计算机科学和计算机应用的核计算机科学和计算机应用的核心，无论是计算机系统、系统心，无论是计算机系统、系统软件的设计，还是为解决计算软件的设计，还是为解决计算机的各种应用所作的设计都可机的各种应用所作的设计都可归结到算法的设计。归结到算法的设计。四个基本问题四个基本问题1什么是算法？什么是算法？2什么是算法分析与设计？什么是算法分析与设计？3为什么学习算法分析与设计？为什么学习算法分析与设计？4如何学好算法分析与设计？如何学好算法分析与设计？4如何学好算法分析与设计？如何

10、学好算法分析与设计？1勤于思考勤于思考2勤于动手勤于动手一、四个基本问题一、四个基本问题二、参考教材及教学计划二、参考教材及教学计划三、考核方式三、考核方式算法分析与设计算法分析与设计四、算法描述方法四、算法描述方法二、参考教材及教学计划二、参考教材及教学计划吴哲辉 崔焕庆 马炳先 吴振寰 编著机械工业出版社按需按需印刷印刷【作者作者】王晓东王晓东【出出版版社社】清华大学出版社清华大学出版社二、参考教材及教学计划二、参考教材及教学计划教学内容教学内容 第第1章章 算法设计与分析概论算法设计与分析概论第第2章章 分治与递归算法分治与递归算法第第3章章 散列与凝聚算法散列与凝聚算法第第4章章 贪心

11、算法贪心算法第第5章章 动态规划算法动态规划算法第第6章章 回溯算法回溯算法第第7章章 分支限界算法分支限界算法第第8章章 NP-完全问题完全问题教学计划教学计划(课堂，34 学时)第第1章章 算法设计与分析概论（算法设计与分析概论（4学时）学时）第第2章章 分治与递归算法（分治与递归算法（6学时）学时）第第3章章 散列与凝聚算法散列与凝聚算法 第第4章章 贪心算法（贪心算法（6学时）学时）第第5章章 动态规划算法（动态规划算法（6学时）学时）第第6章章 回溯算法（回溯算法（6学时）学时）第第7章章 分支限界算法（分支限界算法（4学时）学时）第第8章章 NP-完全问题（完全问题（2学时）学时）

12、教学计划教学计划(实验，实验，14学时学时)第第1章章 算法设计与分析概论算法设计与分析概论第第2章章 分治与递归算法（分治与递归算法（2学时）学时）第第3章章 散列与凝聚算法散列与凝聚算法 第第4章章 贪心算法（贪心算法（2学时）学时）第第5章章 动态规划算法（动态规划算法（4学时）学时）第第6章章 回溯算法（回溯算法（4学时）学时）第第7章章 分支限界算法（分支限界算法（2学时）学时）第第8章章 NP-完全问题完全问题一、四个基本问题一、四个基本问题二、参考教材及教学计划二、参考教材及教学计划三、考核方式三、考核方式算法分析与设计算法分析与设计四、算法描述方法四、算法描述方法三、考核方式三

13、、考核方式总评总评=期末考试期末考试+平时成绩平时成绩其中：期末试卷成绩其中：期末试卷成绩70%；平时成绩；平时成绩30%。平时成绩平时成绩=作业作业+实验报告实验报告+课堂考勤课堂考勤其中：作业其中：作业10分，实验报告分，实验报告10分，课堂考勤分，课堂考勤10分。分。一、四个基本问题一、四个基本问题二、参考教材及教学计划二、参考教材及教学计划三、考核方式三、考核方式算法分析与设计算法分析与设计四、算法描述方法四、算法描述方法四、算法描述方法四、算法描述方法对于设计出来的一类问题的求解步骤，需要一种对于设计出来的一类问题的求解步骤，需要一种表达方式，即表达方式，即算法描述算法描述。描述算法

14、最合适的语言是介于自然语言和程描述算法最合适的语言是介于自然语言和程序语言之间的伪语言序语言之间的伪语言（伪代码）（伪代码）。类类PASCAL，类，类C，类，类JAVA可使用任何表达能力强的方法使算法表达更加清可使用任何表达能力强的方法使算法表达更加清晰和简洁，而不至于陷入具体的程序语言的某些晰和简洁，而不至于陷入具体的程序语言的某些细节。细节。何为形式化？何为形式化？四、算法描述方法四、算法描述方法-例子例子例例1 冒泡排序算法冒泡排序算法n算法的基本思想：轻者（小的元素）像气泡那算法的基本思想：轻者（小的元素）像气泡那样从水底往上浮。在排序过程中，从后面（理解样从水底往上浮。在排序过程中，

15、从后面（理解为底部）开始，每次把相邻的两个元素作比较，为底部）开始，每次把相邻的两个元素作比较，当前面的元素大于后面的元素时，就交换它们的当前面的元素大于后面的元素时，就交换它们的位置。这样，所有相邻的元素比较位置。这样，所有相邻的元素比较一一遍以后最小遍以后最小的元素就被交换到了最前面（浮到上面）。的元素就被交换到了最前面（浮到上面）。下一轮？下一轮？算法算法1.1 冒泡排序冒泡排序输入：待排序数组输入：待排序数组A，其中有，其中有n个元素；个元素；输出：排好序的数组输出：排好序的数组A。bubblesort(float A,int n)int i,j;for(i=0;ii;j-)if(Aj

16、Aj-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.2 求最大公约数的辗转相除算法。求最大公约数的辗转相除算法。n基本思想：用小的数作除数，大的数作为被除数，基本思想：用小的数作除数，大的数作为被除数，做除法求余，如果余数等于零，那么小的数就是做除法求余，如果余数等于零，那么小的数就是两个数的最大公约数。两个数的最大公约数。否则？否则？用小的数做被除数，余数作

17、为除数，再做除法用小的数做被除数，余数作为除数，再做除法求余，如此辗转相除下去，直到余数等于零。求余，如此辗转相除下去，直到余数等于零。最后除数就是要求的原本两个数的最大公约数。最后除数就是要求的原本两个数的最大公约数。gcd(21,9)=?21=2 9+3gcd(21,9)=gcd(9,3)9=3 3+0gcd(9,3)=3gcd(21,9)=3gcd(a,b)=gcd(b,a mod b)证明！证明！算法算法1.3求最大公约数的辗转相除法求最大公约数的辗转相除法输入：两整数输入：两整数m和和n；输出：输出：m和和n的最大公约数。的最大公约数。int gcd(int m,int n)int

18、a=maxm,n;int b=minm,n;int c;while(b!=0)c=a mod b;a=b;b=c;return();agcd(a,b)=?算法算法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：如何评价一个算法的优劣？：

19、如何评价一个算法的优劣？Q2：算法转化为程序运行后，影响程序运行的：算法转化为程序运行后，影响程序运行的因素有哪些？因素有哪些？Q3：如何避免客观因素的影响呢？：如何避免客观因素的影响呢？Q4：为什么渐进时间复杂度？：为什么渐进时间复杂度？两个概念两个概念时间频度时间频度T(n)一个算法执行所耗费的时间，从理论上是不能算一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。出来的，必须上机运行测试才能知道。一个算法花费的时间与算法中语句的执行次数成一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时正比例，哪个算法中语句执行次数多，它花费时

20、间就多。间就多。一个算法中的语句执行次数称为语句频度或时间一个算法中的语句执行次数称为语句频度或时间频度。记为频度。记为T(n)。两个概念两个概念时间复杂度时间复杂度情况下，算法中基本操作重复执行的次数是问题情况下，算法中基本操作重复执行的次数是问题规模规模n的某个函数，用的某个函数，用T(n)表示，表示，若有某个辅助函数若有某个辅助函数f(n),使得当使得当n趋近于无穷大时，趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称的极限值为不等于零的常数，则称f(n)是是T(n)的同数量级函数。记作的同数量级函数。记作T(n)=(f(n),称称(f(n)为算法的渐进时间复杂度，简为算

21、法的渐进时间复杂度，简称时间复杂度。称时间复杂度。例例 有两个算法有两个算法A1和和A2求解同一问题，时间复杂度分别是求解同一问题，时间复杂度分别是T1(n)=100n2，T2(n)=5n3。（1）当输入量）当输入量n20时，有时，有T1(n)T2(n)，后者，后者花费的时间较少。花费的时间较少。（2）随着问题规模）随着问题规模n的增大，两个算法的时的增大，两个算法的时间开销之比间开销之比5n3/100n2=n/20亦随着增大。亦随着增大。渐近时间复杂度渐近时间复杂度O(n2)和和O(n3)从宏观上评价了这从宏观上评价了这两个算法在时间方面的质量。两个算法在时间方面的质量。Q1：如何得到时间复杂度的表达式？：如何得到时间复杂度的表达式？Q2：如何比较两个时间复杂度的级别：如何比较两个时间复杂度的级别?