清华大学出版社 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)即有限性。 算法：是满足下述性质的指令序列。 程序：