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

第一部分 基础知识 3

第1章 算法设计基础 3

1.1算法的基本概念 3

1.1.1算法及其重要特性 3

1.1.2算法的描述方法 5

1.1.3算法设计的一般过程 6

1.2为什么要学习和研究算法 7

1.2.1算法在问题求解中的地位 8

1.2.2算法训练能够提高计算思维能力 10

1.2.3算法研究是推动计算机技术发展的关键 11

1.3重要的问题类型 12

1.3.1查找问题 12

1.3.2排序问题 12

1.3.3图问题 13

1.3.4组合问题 13

1.3.5几何问题 13

阅读材料——算法研究与图灵奖 14

习题1 16

第2章 算法分析基础 17

2.1算法的时间复杂性分析 17

2.1.1输入规模与基本语句 18

2.1.2算法的渐进分析 19

2.1.3最好、最坏和平均情况 20

2.1.4非递归算法的时间复杂性分析 20

2.1.5递归算法的时间复杂性分析 22

2.2算法的空间复杂性分析 23

2.3最优算法 23

2.3.1问题的计算复杂性下界 24

2.3.2平凡下界 25

2.3.3判定树模型 25

阅读材料——算法的实验分析 26

习题2 28

第二部分 基本的算法设计技术 33

第3章 蛮力法 33

3.1概述 33

3.1.1蛮力法的设计思想 33

3.1.2一个简单的例子——百元买百鸡问题 34

3.2查找问题中的蛮力法 36

3.2.1顺序查找 36

3.2.2串匹配问题 37

3.3排序问题中的蛮力法 42

3.3.1选择排序 42

3.3.2起泡排序 43

3.4组合问题中的蛮力法 44

3.4.1 0/1背包问题 44

3.4.2任务分配问题 45

3.5图问题中的蛮力法 46

3.5.1哈密顿回路问题 46

3.5.2 TSP问题 47

3.6几何问题中的蛮力法 48

3.6.1最近对问题 48

3.6.2凸包问题 49

阅读材料——KMP算法中next值的计算 51

习题3 53

第4章 分治法 55

4.1概述 55

4.1.1分治法的设计思想 55

4.1.2一个简单的例子——数字旋转方阵 57

4.2排序问题中的分治法 59

4.2.1归并排序 59

4.2.2快速排序 61

4.3组合问题中的分治法 64

4.3.1最大子段和问题 64

4.3.2棋盘覆盖问题 65

4.4几何问题中的分治法 67

4.4.1最近对问题 68

4.4.2凸包问题 71

阅读材料——递归函数的执行过程 72

习题4 74

第5章 减治法 77

5.1概述 77

5.1.1减治法的设计思想 77

5.1.2一个简单的例子——两个序列的中位数 78

5.2查找问题中的减治法 80

5.2.1折半查找 80

5.2.2二叉查找树 82

5.2.3选择问题 84

5.3排序问题中的减治法 86

5.3.1插入排序 86

5.3.2堆排序 88

5.4组合问题中的减治法 90

5.4.1淘汰赛冠军问题 90

5.4.2假币问题 91

阅读材料——假币问题的复杂版本 93

习题5 94

第6章 动态规划法 97

6.1概述 97

6.1.1多阶段决策过程 98

6.1.2动态规划法的设计思想 99

6.1.3一个简单的例子——数塔问题 100

6.2图问题中的动态规划法 102

6.2.1多段图的最短路径问题 102

6.2.2多源点最短路径问题 106

6.2.3 TSP问题 107

6.3组合问题中的动态规划法 109

6.3.1最长递增子序列问题 109

6.3.2最长公共子序列问题 111

6.3.3 0/1背包问题 114

6.4查找问题中的动态规划法 116

6.4.1最优二叉查找树 116

6.4.2近似串匹配问题 119

阅读材料——人工神经网络 121

习题6 124

第7章 贪心法 127

7.1概述 127

7.1.1贪心法的设计思想 127

7.1.2一个简单的例子——埃及分数 128

7.2图问题中的贪心法 129

7.2.1 TSP问题 129

7.2.2图着色问题 132

7.2.3最小生成树问题 134

7.3组合问题中的贪心法 138

7.3.1背包问题 138

7.3.2活动安排问题 140

7.3.3多机调度问题 142

阅读材料——贪心法的正确性证明 144

习题7 146

第三部分 基于搜索的算法设计技术 151

第8章 回溯法 151

8.1概述 151

8.1.1问题的解空间树 151

8.1.2回溯法的设计思想 152

8.1.3回溯法的时间性能 153

8.1.4一个简单的例子——素数环问题 154

8.2图问题中的回溯法 155

8.2.1图着色问题 155

8.2.2哈密顿回路问题 158

8.3组合问题中的回溯法 160

8.3.1八皇后问题 160

8.3.2批处理作业调度问题 163

阅读材料——遗传算法 166

习题8 169

第9章 分支限界法 171

9.1概述 171

9.1.1分支限界法的设计思想 171

9.1.2分支限界法的时间性能 172

9.1.3一个简单的例子——圆排列问题 173

9.2图问题中的分支限界法 175

9.2.1 TSP问题 175

9.2.2多段图的最短路径问题 178

9.3组合问题中的分支限界法 180

9.3.1 0/1背包问题 180

9.3.2任务分配问题 182

9.3.3批处理作业调度问题 184

阅读材料——蚁群算法 187

习题9 189

第四部分 计算的限制 193

第10章 问题的复杂性 193

10.1问题的复杂性分类 193

10.1.1什么是计算 194

10.1.2可计算问题与不可计算问题 195

10.1.3易解问题与难解问题 197

10.2 P类问题和NP类问题 199

10.2.1判定问题 199

10.2.2确定性算法与P类问题 199

10.2.3非确定性算法与NP类问题 200

10.3 NP完全问题 201

10.3.1问题变换 201

10.3.2 NP完全问题的定义 202

10.3.3基本的NP完全问题 202

10.3.4 NP完全问题的计算机处理 203

阅读材料——Cook定理 204

习题10 207

第11章 近似算法 209

11.1概述 209

11.1.1近似算法的设计思想 209

11.1.2一个简单的例子——求π的近似值 210

11.2图问题中的近似算法 211

11.2.1顶点覆盖问题 211

11.2.2 TSP问题 212

11.3组合问题中的近似算法 214

11.3.1装箱问题 214

11.3.2子集和问题 216

阅读材料——粒子群算法 219

习题11 221

第12章 概率算法 223

12.1概述 223

12.1.1概率算法的设计思想 224

12.1.2随机数发生器 224

12.2舍伍德型概率算法 225

12.2.1舍伍德型概率算法的设计思想 225

12.2.2快速排序 226

12.2.3二叉查找树 227

12.3拉斯维加斯型概率算法 228

12.3.1拉斯维加斯型概率算法的设计思想 228

12.3.2八皇后问题 229

12.3.2整数因子划分问题 230

12.4蒙特卡罗型概率算法 231

12.4.1蒙特卡罗型概率算法的设计思想 231

12.4.2主元素问题 232

12.4.3素数测试问题 233

阅读材料——模拟淬火算法 234

习题12 235

附录A名词索引 237

参考文献 243