第1章 算法概述 计算机算法设计与分析教学课件.pptVIP

计算机算法设计与分析 中国科技大学 肖明军 xiaomj@ustc.edu.cn 教材与参考书 教材 《计算机算法设计与分析》（第3版），王晓东编，电子工业出版社。 参考书 《算法导论/Introduction to Algorithms》（第2版），Thomas H. Cormen等著，潘金贵等译，机械工业出版社。 《算法设计与分析导论》，R.C.T. Lee等著，王卫东译，机械工业出版社。 主要内容介绍 第1章 算法概述 第2章 递归与分治策略 第3章 动态规划 第4章 贪心算法 第5章 回溯法 第6章 分支限界法 主要内容介绍（续） 第7章 随机化算法 第8章 线性规划与网络流 第9章 NP完全性理论与近似算法 第1章 算法概述 本章主要知识点： §1.1 算法的基本概念 §1.2 算法描述 §1.3 算法分析 §1.4 算法复杂性的表示法 §1.5 算法分析的计算基础 §1.1 算法的基本概念 定义 一个算法是任何一个良定义（well-defined）的计算过程，它接收某个值或值的集合作为输入，产生某个值或值的集合作为输出。因此，一个算法是一个计算步骤的序列，这些步骤将输入转化为输出。 §1.1 算法的基本概念（续） 算法可以看作是一种工具，用来解决一个具有良好规格说明的计算问题。 例：排序问题 ?问题描述： ?Input： 具有n个数的数列a1,a2,…,an ?Output： 上述序列的一个排列a1’,a2’,…,an’满 足关系：a1’≤a2’≤…≤an’ ?计算步骤： ? 如何达到上述关系 §1.1 算法的基本概念（续） 性质 算法是由若干条指令组成的有穷序列，满足以下4条性质： 输 入：有零个或多个外部量作为算法的输入。 输 出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 程序是算法用某种程序设计语言的具体实现， 程序可以不满足算法的性质(4)即有限性。 §1.1 算法的基本概念（续） 应用 人类基因数据库分析 因特网信息管理 电子商务：加密/解密，保护隐私 火车、航班调度 大科学计算 应用软件 实际应用 。。。 §1.1 算法的基本概念（续） 算法可以看作是一项技术 例 对于排序问题（问题规模：n=106） 插入排序算法：复杂度c1n2 合并排序算法：复杂度c2nlog2n 计算机A每秒能执行10亿条指令 计算机B每秒能执行1000万条指令 计算机A+插入排序算法（c1=2），则计算机A花的时间为： 计算机B+合并排序算法（c2=50），则计算机B花的时间为： §1.1 算法的基本概念（续） 基本概念 Instance：一个问题的实例由计算该问题的一个解所需要的所有输入所组成。 正确性：若对每个输入实例，算法均终止于正确的输出，则称算法是正确的。 不正确算法：对某些输入实例不停机，或虽然停机，但不是所期望的答案。 Note：一个不正确的算法，若其错误的概率是可控制的，有时也是有用的。 §1.2 算法描述 表达算法的抽象机制 采用高级程序设计语言，主要好处是： 高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 §1.2 算法描述（续） 抽象数据类型，是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。它带给算法设计的好处有： 算法顶层设计与底层实现分离； 算法设计与数据结构设计隔开，允许数据结构自由选择； 便于空间和时间耗费的折衷； 用抽象数据类型表述的算法具有很好的可维护性； 算法自然呈现模块化； 为自顶向下逐步求精和模块化提供有效途径和工具； 算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。 §1.2 算法描述（续） 描述方式 采用C++语言描述 类型丰富、语句精炼 具有面向过程和面向对象的双重特点 采用C++语言描述算法可使整个算法结构紧凑，可读性强 采用C++语言与自然语言结合的方式描述算法 §1.3 算法分析 目的： 分析算法就是估计算法所需资源（时间，空间，通信带宽等） ，以便选取有效的算法。 计算模型： 单处理机，随机存取机（Random-Access Machine，RAM）计算模型，其中指令是顺序执行的，无并发操作 涉及的知识基础： 离散组合数学、概率论、代数等