第1章算法引论.ppt

算法设计与分析
主要内容介绍
第1章 算法引论
第2章 递归与分治策略
第3章 动态规划
第4章 贪心算法
第5章 回溯法
第6章 分支限界法
第7章 概率算法
第8章 NP完全性理论
第9章 近似算法
第10章 算法优化策略
第1章算法引论
算法与程序
表达算法的抽象机制
描述算法
算法复杂性分析
算法与程序
算法:
是满足下述性质的指令序列。
输入:有零或多个外部量作为算法的输入。
输出:算法产生至少一个量作为输出。
确定性:组成算法的每条指令清晰、无歧义。
有限性:算法中每条指令的执行次数有限,执行每条指令的时间也有限。
程序:
是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。
例如:
操作系统是一个程序,不是算法,但其各种任务如作业管理、进程调度可以采用特定的算法来实现。
表达算法的抽象机制
(数据、运算和控制)
算法的数据:
基本数据(布尔值字符整数实数)
较复杂数据(向量矩阵记录)
更复杂数据(集合树图声音图像)
算法的运算:
基本运算(逻辑赋值算术关系)
复杂运算(函数值计算向量运算集合运算表、树、图上的运算)

高级程序设计语言的主要好处是:
(1)更接近算法语言,易学、易掌握;
(2)提供了结构化程序设计的环境和工具,使得设计出来的程序可读性好,可维护性强,可靠性高;
(3)不依赖于机器语言,与具体的计算机硬件关系不大,因而所写出来的程序可植性好、重用率高;
(4)把繁杂琐碎的事务交给编译程序,自动化程度高。

算法从非形式的自然语言表达到形式化的高级语言表达,是一个复杂的过程,要做很多繁杂琐碎的事情,因而仍然需要抽象。
对于一个数学问题,设计算法的一般步骤为:
(1)先选用该问题的一个数据模型。
(2)接着,弄清数据模型在已知条件下的初始状态和要求的结果状态,以及两个状态之间的关系。
(3)然后探索从已知初始状态出发到达要求的结果状态所必需的运算步骤。
例如:计算自然数m,n的最大公约数
按照自顶向下逐步求精的原则,在探索运算步骤时,首先应该考虑算法顶层运算步骤,然后再考虑底层运算步骤。
顶层运算步骤:是指定义在数据模型级上的运算步骤,或叫宏观运算。它们组成算法的主干部分。表达这部分算法的程序就是主程序。
底层运算步骤:是指顶层抽象的运算的具体实现。它们依赖于数据模型的结构,依赖于数据模型结构的具体表示。包括两部分:一是数据模型的具体表示;二是定义在该数据模型上的运算的具体实现。