算法导论详解PPT课件

1、First Example: Identifying Genes in Human DNA (基因识别基因识别)lIdentifying all the 100,000 genes inhuman DNAudetermining the sequences of the3 billion(109) chemical base pairs that make up human DNA. （30亿组化学基对组成人类DNA，如何界定这些序列，从而进行基因识别）Computer: 3G Hz CPU, 3*109B/s, suppose that it executes one billion ins

2、tructions per second （设该计算机的运行速度为 10亿条基本指令/s ）Input size: n = 3*109Insertion sort: running time n2999993 103 10 instruc9 109 10 secondsy 31.71years10 instruc/s60 60 24 365 t = s/v :第1页/共25页2First Example: Identifying Genes in Human DNAlIdentifying all the 100,000 genes in human DNAudetermining the s

3、equences of the 3 billion(109) chemical base pairs that make up human DNA.Insertion sort: running time n2Merge sort: running time nlgn99993 10lg(3 10 )instruc3 lg(3 10 )seconds94.45seconds10 instruc/s 999993 103 10 instruc9 109 10 secondsy 31.71years10 instruc/s60 60 24 365 l全国居民身份证管理系统：全国居民身份证管理系统：

4、 n = 1.3109 人人l国家安全防护指纹识别系统：国家安全防护指纹识别系统：n = 1.3109 人人第2页/共25页3Algorithm Analysis and DesignlStudents：undergraduate, graduatelCourse property： base, core, . in computinglBibliographylIntroduction to Algorithms(Second Edition), T. H. Cormen, C. E. Leiserson, R. L. Rivest (2002, Turing Award), The MIT

5、 PresslThe Art of Computer Programming, Donald E, Knuth 1974, Turing Awardl算法设计与分析，吕国英编著，清华大学出版社，2005年。l算法设计与分析，王晓东编著，清华大学出版社l.“计算机算法的圣经”“计算机程序设计理论的荷马史诗”网友：“没有读过Intro，不能算是一个真正的程序员”Bill Gates: “如果你认为你是一名真正优秀的程序员，请读Knuth的计算机程序设计艺术，如果你能读懂整套书的话，请给我发一份你的简历。”第3页/共25页4Algorithm Design and Analysis l学习方式听课上

6、机实践（作业）考试15% 15% 70%l课堂要求学术很自由，课堂很严肃：不迟到、早退；不允许接听电话、大声聊天l考核形式u出勤率：about 15%u大作业（算法实现2-3个）：about 15%u期末闭卷考试： about 70%l课程安排u课堂讲解：基本理论讲解，基本方法的介绍分析u上机实践：基本习题和经典习题的上机实践第4页/共25页5主要内容介绍主要内容介绍 第1章 算法引论 第2章 算法基本设计技巧 第3章 分治策略 第4章 动态规划 第5章 贪心算法 第6章 回溯法 第7章 分支限界法第5页/共25页6第第1 1章章 算法引论算法引论 1.1 算法与程序 1.2 表达算法的抽象机

7、制 1.3 描述算法 1.4 算法复杂性分析本章主要知识点：第6页/共25页71.1算法与程序算法与程序 输 入：有零个或多个外部量作为算法的输入。 输 出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性。 是满足下述性质的指令序列。算法：程序：第7页/共25页81.从机器语言到高级语言的抽象1.2表达算法的抽象机制表达算法的抽象机制高级程序设计语言的主要好处是：（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程

8、序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；第8页/共25页92.抽象数据类型1.2表达算法的抽象机制表达算法的抽象机制 抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。 抽象数据类型带给算法设计的好处有： （1）算法顶层设计与底层实现分离；（2

9、）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。 第9页/共25页10在本书中，采用Java语言描述算法。1.1.JavaJava程序结构程序结构 1.3描述算法描述算法以下，对JavaJava语言的若干重要特性作简要概述。 （1）Java程序的两种类型：应用程序和appletapplet区别：应用程序的主方法为main，其可在

10、命令行中用命令语句 java 应用程序名 来执行；applet的主方法为init，其必须嵌入HTML文件，由Web浏览器或applet阅读器来执行。（2）包：java程序和类可以包(packages)的形式组织管理。 （3）import语句：在java程序中可用import语句加载所需的包。例如，import java.io.*;语句加载java.io包。 第10页/共25页111.3描述算法描述算法2.2.JavaJava数据类型数据类型数据类型 基本数据类型：详见下页表1-1 非基本数据类型：如 Byte, Integer, Boolean, String等。 Java对两种数据类型的不同

11、处理方式： 对基本数据类型：在声明一个具有基本数据类型的变量时，自动建立该数据类型的对象（或称实例）。如:int k;对非基本数据类型：语句 String s; 并不建立具有数据类型String的对象，而是建立一个类型String的引用对象，数据类型为String的对象可用下面的new语句建立。 s = new StringString(“Welcome”);StringString s = new StringString(“Welcome”);第11页/共25页121.3描述算法描述算法表格表格1-1 1-1 JavaJava基本数据类型基本数据类型类型缺省值分配空间（bits）取值范围b

12、ooleanfalse1true,falsebyte08-128,127charu000016u0000,uFFFFdouble0.0644.9*10-324 1.8*10308float0.0321.4*10-45 3.4*1038int032-2147483648,2147483647long0649.2*1017short016-32768,32767第12页/共25页131.3描述算法描述算法3.3.方法方法在Java中，执行特定任务的函数或过程统称为方法(methods) 。例如，java的MathMath类类给出的常见数学计算的方法如下表所示：方法方法功能功能方法方法功能功能abs

13、(x)x的绝对值max(x,y)x和y中较大者ceil(x)不小于x的最小整数min(x,y)x和y中较小者cos(x)x的余弦pow(x,y)xyexp(x)exsin(x)x的正弦floor(x)不大于x的最大整数sqrt(x)x的平方根log(x)x的自然对数tan(x)x的正切第13页/共25页141.3描述算法描述算法3.3.方法方法 2baba计算表达式 值的自定义方法ab描述如下： public static int ab(int a, int b) return (a+b+Math.abs(a-b)/2; （1）方法参数：Java中所有方法的参数均为值参数。上述方法ab中，a和

14、b是形式参数，在调用方法时通过实际参数赋值。 （2）方法重载：Java允许方法重载，即允许定义有不同签名的同名方法。上述方法ab可重载为： public static double ab(double a, double b) return (a+b+Math.abs(a-b)/2.0; 第14页/共25页151.3描述算法描述算法4.4.异常异常 Java的异常提供了一种处理错误的方法。当程序发现一个错误，就引发一个异常，以便在合适地方捕获异常并进行处理。 通常用trytry块来定义异常处理。每个异常处理由一个catchcatch语句组成。 public static void main(S

15、tring args) try f ( ); catch (exception1) 异常处理; catch (exception2) 异常处理; finally finally块; 第15页/共25页161.3描述算法描述算法5.5.JavaJava的类的类(4)访问修饰访问修饰公有(public) 私有(private)保护(protected) Java的类一般由4个部分组成：(1)类名类名(2)数据成员数据成员(3)方法方法第16页/共25页171.3描述算法描述算法6.6.通用方法通用方法 下面的方法swapswap用于交换一维整型数组a的位置i和位置j处的值。 public stat

16、ic void swap(int a, int i, int j) int temp = ai; ai = aj; aj = temp; public static void swap(object a, int i, int j) object temp = ai; ai = aj; aj = temp; 该方法只适用于该方法只适用于整型数组整型数组该方法具有通用性，适用于该方法具有通用性，适用于ObjectObject类型及其所有子类类型及其所有子类 以上方法修改如下：以上方法修改如下：第17页/共25页181.3描述算法描述算法6.6.通用方法通用方法 （1 1）ComputableCo

17、mputable界面界面 public static Computable sum(Computable a, int n) if (a.length = 0) return null; Computable sum = (Computable) a0.zero(); for (int i = 0; i n; i+) sum.increment(ai); return sum;利用此界面使利用此界面使方法方法sumsum通用化通用化 第18页/共25页191.3描述算法描述算法6.6.通用方法通用方法 （2 2）java.lang.Comparable java.lang.Comparable

18、 界面界面 Java的Comparable 界面中惟一的方法头compareTo用于比较2个元素的大小。例如java.lang.CpareTo(y)返回x-y的符号，当xy时返回正数。（3 3）OperableOperable 界面界面 有些通用方法同时需要Computable界面和Comparable 界面的支持。为此可定义Operable界面如下:public interface Operable extends Computable, Comparable （4 4）自定义包装类）自定义包装类 由于Java的包装类如Integer等已定义为final型，因此无法定义其子类，作进一步扩充。

19、为了需要可自定义包装类。 第19页/共25页201.3描述算法描述算法7.7.垃圾收集垃圾收集8.8.递归递归Java的newnew运算用于分配所需的内存空间。例如， int a = new int500000; 分配2000000字节空间给整型数组a。频繁用new分配空间可能会耗尽内存。Java的垃垃圾收集器圾收集器会适时扫描内存，回收不用的空间（垃圾）给new重新分配。 Java允许方法调用其自身。这类方法称为递归方法。public static int sum(int a, int n) if (n=0) return 0; else return an-1+sum(a,n-1); 计算

20、一维整型数组前计算一维整型数组前n n个元个元素之和的递归方法素之和的递归方法 第20页/共25页211.4算法复杂性分析算法复杂性分析 算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性时间复杂性，需要的空间资源的量称为空间复杂性空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有： T=T(N,I)和S=S(N,I) 。（通常，让A隐含在复杂性函数名当中） 第21页/共25页221.4算法复杂性分析算法复杂性分析最坏情况下的时间复杂性：),(maxmaxINT(N)TNDI),(max1INetkiiiDIN),(*1INetkiii),(*INT最好情况下的时间复杂性：),(minminINT(N)TNDI),(min1INetkiiiDIN),(1INetkiii),(INT平均情况下的时间复杂性：NDIINTIP(N)T),()(avgNDIkiiiINetIP),()(1 其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I*)达到Tmax(N)的合法输入； 是中使T(N, )达到Tmin(N)的合法输入；而P(I)是在