算法分析与设计PDF电子书下载

第1章 绪论 1

1.1 算法的基本概念 1

1.1.1 为什么要学习算法 1

1.1.2 算法及其重要特性 2

1.1.3 算法的描述方法 3

1.1.4 算法设计的一般过程 3

1.2 算法分析 5

1.2.1 渐近符号 5

1.2.2 非递归算法的分析 7

1.2.3 递归算法的分析 8

1.2.4 算法的后验分析 11

实验1——求最大公约数 13

阅读材料1——海量数据处理方法：Bloom filter 17

习题1 18

第2章 分治法 28

2.1 概 述 28

2.1.1 分治法简介 28

2.1.2 分治法的基本步骤 29

2.2 最大子段和问题 31

2.3 棋盘覆盖问题 33

2.4 输油管道问题 36

2.5 凸包问题 39

实验2——最近对问题 41

阅读材料2——分治法在中值滤波快速算法中的应用研究 42

习题2 43

第3章 动态规划 52

3.1 动态规划问题的数学描述 52

3.2 动态规划问题的最优化原理 55

3.3 动态规划应用举例 61

3.3.1 数字三角形问题 61

实验3 数字三角形问题 67

阅读材料3——深入探讨动态规划中的几个问题 69

习题3 71

第4章 贪心法 72

4.1 概述 72

4.1.1 贪心法的设计思想 72

4.1.2 贪心法的求解过程 74

4.2 删数问题 75

4.2.1 问题的提出 75

4.2.2 贪心选择策略 75

4.2.3 最优子结构性质 75

4.2.4 贪心选择性质 76

4.2.5 算法实现 76

4.3 图问题中的贪心法 77

4.3.1 TSP问题 77

4.3.2 图着色问题 84

4.4 FatMouse'Trade 87

实验4——图着色问题 90

阅读材料4——用贪心算法求解删数问题 91

习题4 95

第5章 回溯法 98

5.1 概 述 98

5.1.1 问题的解空间 98

5.1.2 解空间树的动态搜索 100

5.1.3 回溯法的求解过程 102

5.1.4 回溯法的时间性能 103

5.2 装载问题 105

5.3 图着色问题 109

5.4 Fire Net 112

实验5——0/1背包问题 115

阅读材料5——基于回溯法油管传输射孔排炮算法研究 116

习题5 119

第6章 分支限界法 122

6.1 概述 122

6.1.1 解空间树的动态搜索 122

6.1.2 分支限界法的设计思想 125

6.1.3 分支限界法的时间性能 127

6.2 TSP问题 128

6.3 电路布线问题 139

实验6——电路布线问题 143

阅读材料6——分支限界法在游戏地图寻径中的应用 144

习题6 147

第7章 概率算法 150

7.1 概 述 150

7.1.1 概率算法的设计思想 151

7.1.2 随机数发生器 151

7.2 舍伍德（Sherwood）型概率算法 153

7.2.1 选择问题 154

7.3 拉斯维加斯（LasVegas）型概率算法 157

7.3.1 八皇后问题 158

7.3.2 整数因子分解问题 160

7.4 蒙特卡罗（Monte Carlo）型概率算法 164

7.4.1 主元素问题 164

实验7——随机数发生器 165

阅读材料7——随机数生成原理 167

习题7 169

第8章 近似算法 174

8.1 概 述 174

8.1.1 近似算法的设计思想 174

8.1.2 近似算法的性能 175

8.2 顶点覆盖问题 176

8.3 平方根问题 182

8.4 TSP问题 183

实验8——TSP问题的近似算法 190

阅读材料8若干NP困难的组合最优化问题的近似算法 191

习题8 193

国际大学生程序设计竞赛试题——The Triangle 200

模拟试题 201

参考文献 207