清华大学出版社 TSINGHUA UNIVERSITY PRESS 中国计算机学会 “21世纪大学本科计算机专业系列教 材 算法设计与分析 王晓东编著
1 中国计算机学会 “21世纪大学本科计算机专业系列教 材” 算法设计与分析 王晓东 编著
清华大学出版社 TSINGHUA UNIVERSITY PRESS 主要内容介绍 第1章算法引论 第2章递归与分治策略 第3章动态规划 第4章贪心算法 第5章回溯法 第6章分支限界法 2
2 主要内容介绍 • 第1章 算法引论 • 第2章 递归与分治策略 • 第3章 动态规划 • 第4章 贪心算法 • 第5章 回溯法 • 第6章 分支限界法
清华大学出版社 TSINGHUA UNIVERSITY PRESS 主要内容介绍(续) 第7章概率算法 第8章N完全性理论 第9章近似算法 第10章算法优化策略
3 主要内容介绍（续） • 第7章 概率算法 • 第8章 NP完全性理论 • 第9章 近似算法 • 第10章 算法优化策略
清华大学出版社 TSINGHUA UNIVERSITY PRESS 第1章算法引论 本章主要知识点: ·1.1算法与程序 ·1.2表达算法的抽象机制 ·1.3描述算法 ·1.4算法复杂性分析 4
4 第1章 算法引论 • 1.1 算法与程序 • 1.2 表达算法的抽象机制 • 1.3 描述算法 • 1.4 算法复杂性分析 本章主要知识点：
清华大学出版社 TSINGHUA UNIVERSITY PRESS 11算法与程序 算法:是满足下述性质的指令序列 输入:有零个或多个外部量作为算法的输入。 输出:算法产生至少一个量作为输出。 确定性:组成算法的每条指令清晰、无歧乂。 有限性:算法中每条指令的执行次数有限,执行 每条指令的时间也有限。 程序:是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性
5 1.1 算法与程序 • 输 入：有零个或多个外部量作为算法的输入。 • 输 出：算法产生至少一个量作为输出。 • 确定性：组成算法的每条指令清晰、无歧义。 • 有限性：算法中每条指令的执行次数有限，执行 每条指令的时间也有限。 是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性。 算法：是满足下述性质的指令序列。 程序：
清华大学出版社 TSINGHUA UNIVERSITY PRESS 1.2表达算法的抽象机制 1从机器语言到高级语言的抽象 高级程序设计语言的主要好处是 1)高级语言更接近算法语言,易学、易掌握,一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作; (2)高级语言为程序员提供了结构化程序设计的环境和工具,使得设计 出来的程序可读性好,可维护性强,可靠性高; 3)高级语言不依赖于机器语言,与具体的计算机硬件关系不大,因而 所写出来的程序可植性好、重用率高; (4)把繁杂琐碎的事务交给编译程序,所以自动化程度高,开发周期短, 程序员可以集中时间和精力从事更重要的创造性劳动,提高程序质量
6 1.从机器语言到高级语言的抽象 1.2 表达算法的抽象机制 高级程序设计语言的主要好处是： （4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短， 程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 （1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作； （2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计 出来的程序可读性好，可维护性强，可靠性高； （3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而 所写出来的程序可植性好、重用率高；
清华大学出版社 TSINGHUA UNIVERSITY PRESS 1.2表达算法的抽象机制 2抽象数据类型 抽象数据类型是算法的一个数据模型连同定乂在该模型上 并作为算法构件的一组运算。 抽象数据类型带给算法设计的好处有: (1)算法顶层设计与底层实现分离; (2)算法设计与数据结构设计隔开,允许数据结构自由选择 (3)数据模型和该模型上的运算统在ADT中,便于空间和时间耗费的折衷; (4)用抽象数据类型表述的算法具有很好的可维护性; 5)算法自然呈现模块化; 6)为自顶向下逐步求精和模块化提供有效途径和工具; 7)算法结构清晰,层次分明,便于算法正确性的证明和复杂性的分析
7 2.抽象数据类型 1.2 表达算法的抽象机制 抽象数据类型是算法的一个数据模型连同定义在该模型上 并作为算法构件的一组运算。 抽象数据类型带给算法设计的好处有： （1）算法顶层设计与底层实现分离； （2）算法设计与数据结构设计隔开，允许数据结构自由选择； （3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷； （4）用抽象数据类型表述的算法具有很好的可维护性； （5）算法自然呈现模块化； （6）为自顶向下逐步求精和模块化提供有效途径和工具； （7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析
清华大学出版社 TSINGHUA UNIVERSITY PRESS 1.3描述算法 在本书中,采用Java语言描述算法。 以下,对Java语言的若干重要特性作简要概述。 1.Java程序结构 (1)Java程序的两种类型:应用程序和 applet 区别:应用程序的主方法为main,其可在命令行中用命令 语句java应用程序名来执行; aplt的主方法为int,其必须嵌入HTML文件,由 Web浏览器或 applet阅读器来执行 (2)包:ja程序和类可以包( packages)的形式组织管理。 (3) import语句:在java程序中可用 Impor语句加载所需的包。 例如, Import Java.Io.*;语句加载avao包
8 在本书中，采用Java语言描述算法。 1.Java程序结构 1.3 描述算法 以下，对Java语言的若干重要特性作简要概述。 （1）Java程序的两种类型：应用程序和applet 区别：应用程序的主方法为main，其可在命令行中用命令 语句 java 应用程序名 来执行； applet的主方法为init，其必须嵌入HTML文件，由 Web浏览器或applet阅读器来执行。 （2）包：java程序和类可以包(packages)的形式组织管理。 （3）import语句：在java程序中可用import语句加载所需的包。 例如，import java.io.*;语句加载java.io包
清华大学出版社 TSINGHUA UNIVERSITY PRESS 1.3描述算法 2.Java数据类型 基本数据类型:详见下页表1-1 数据类型 非基本数据类型:如Byte, Integer, Boolean, String等。 Java对两种数据类型的不同处理方式: 动建立该数据类型的对象(或称实例)。如int·令 对基本数据类型:在声明一个具有基本数据类型的变量时 对非基本数据类型:语句 String s;并不建立具有数据类型 String的对象,而是建立一个类型 String的引用对象, 数据类型为 Stringl的对象可用下面的new语句建立。 s= new Str ing( Welcome) Strings=new String( Welcome")
9 1.3 描述算法 2.Java数据类型 数据类型 基本数据类型：详见下页表1-1 非基本数据类型：如 Byte, Integer, Boolean, String等。 Java对两种数据类型的不同处理方式： 对基本数据类型：在声明一个具有基本数据类型的变量时，自 动建立该数据类型的对象（或称实例）。如:int k; 对非基本数据类型：语句 String s; 并不建立具有数据类型 String的对象，而是建立一个类型String的引用对象， 数据类型为String的对象可用下面的new语句建立。 s = new String(“Welcome”); String s = new String(“Welcome”);
清华大学出版社 TSINGHUA UNIVERSITY PRESS 1.3描述算法 表格1-1Java基本数据类型 类型缺省值分配空间(bs5) 取值范围 boolean fal true, false bvte -128,127] char uO000 16 Nuoooo, luFFFFI double 0.0 64 ±4.9*10-324~±1.8*10308 0.0 32 ±14*10-45~±34*1038 32 -2147483648,2147483647 long 000 64 ±9.2*1017 short 16 -32768,32767]
10 1.3 描述算法 表格1-1 Java基本数据类型 类型 缺省值 分配空间（bits） 取值范围 boolean false 1 [true,false] byte 0 8 [-128,127] char \u0000 16 [\u0000,\uFFFF] double 0.0 64 ±4.9*10-324~ ±1.8*10308 float 0.0 32 ±1.4*10-45~±3.4*1038 int 0 32 [-2147483648,2147483647] long 0 64 ±9.2*1017 short 0 16 [-32768,32767]