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

目录 1

第1章 绪论 1

1.1 算法的基本概念 1

1.1.1 为什么要学习算法 1

1.1.2 算法及其重要特性 3

1.1.3 算法的描述方法 4

1.1.4 算法设计的一般过程 5

1.1.5 重要的问题类型 8

1.2 算法分析 10

1.2.1 渐进符号 10

1.2.2 最好、最坏和平均情况 12

1.2.3 非递归算法的分析 13

1.2.4 递归算法的分析 14

1.2.5 算法的后验分析 16

1.3 实验项目——求最大公约数 18

阅读材料——人工神经网络与BP算法 19

习题1 21

第2章 NP完全理论 25

2.1 下界 25

2.1.1 平凡下界 26

2.1.2 判定树模型 26

2.1.3 最优算法 27

2.2 算法的极限 28

2.2.1 易解问题与难解问题 28

2.2.2 实际问题难以求解的原因 30

2.2.3 不可解问题 32

2.3 P类问题和NP类问题 34

2.3.1 判定问题 34

2.3.2 确定性算法与P类问题 35

2.3.3 非确定性算法与NP类问题 35

2.4 NP完全问题 36

2.4.1 问题变换与计算复杂性归约 37

2.4.2 NP完全问题的定义 38

2.4.3 基本的NP完全问题 40

2.4.4 NP完全问题的计算机处理 41

2.5 实验项目——SAT问题 43

阅读材料——遗传算法 43

习题2 47

第3章 蛮力法 49

3.1 蛮力法的设计思想 49

3.2 查找问题中的蛮力法 50

3.2.1 顺序查找 50

3.2.2 串匹配问题 52

3.3 排序问题中的蛮力法 56

3.3.1 选择排序 56

3.3.2 起泡排序 57

3.4 组合问题中的蛮力法 58

3.4.1 生成排列对象 58

3.4.2 生成子集 58

3.4.4 任务分配问题 59

3.4.3 0/1背包问题 59

3.5.1 哈密顿回路问题 61

3.5 图问题中的蛮力法 61

3.5.2 TSP问题 62

3.6 几何问题中的蛮力法 63

3.6.1 最近对问题 63

3.6.2 凸包问题 64

3.7 实验项目——串匹配问题 65

阅读材料——蚁群算法 67

习题3 70

4.1 概述 73

4.1.1 分治法的设计思想 73

第4章 分治法 73

4.1.2 分治法的求解过程 74

4.2 递归 75

4.2.1 递归的定义 75

4.2.2 递归函数的运行轨迹 77

4.2.3 递归函数的内部执行过程 77

4.3 排序问题中的分治法 78

4.3.1 归并排序 78

4.3.2 快速排序 80

4.4 组合问题中的分治法 83

4.4.1 最大子段和问题 83

4.4.2 棋盘覆盖问题 85

4.4.3 循环赛日程安排问题 87

4.5 几何问题中的分治法 88

4.5.1 最近对问题 89

4.5.2 凸包问题 90

4.6 实验项目——最近对问题 91

阅读材料——鱼群算法 92

习题4 95

第5章 减治法 97

5.1 减治法的设计思想 97

5.2 查找问题中的减治法 98

5.2.1 折半查找 98

5.2.2 二叉查找树 100

5.3.1 堆排序 101

5.3 排序问题中的减治法 101

5.3.2 选择问题 105

5.4 组合问题中的减治法 106

5.4.1 淘汰赛冠军问题 106

5.4.2 假币问题 107

5.5 实验项目——8枚硬币问题 109

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

习题5 112

第6章 动态规划法 115

6.1 概述 115

6.1.1 最优化问题 115

6.1.2 最优性原理 116

6.1.3 动态规划法的设计思想 117

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

6.2.1 TSP问题 119

6.2.2 多段图的最短路径问题 121

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

6.3.1 0/1背包问题 123

6.3.2 最长公共子序列问题 126

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

6.4.1 最优二叉查找树 128

6.4.2 近似串匹配问题 132

6.5 实验项目——最大子段和问题 134

阅读材料——文化算法 135

习题6 137

第7章 贪心法 139

7.1 概述 139

7.1.1 贪心法的设计思想 139

7.1.2 贪心法的求解过程 140

7.2 图问题中的贪心法 141

7.2.1 TSP问题 141

7.2.2 图着色问题 144

7.2.3 最小生成树问题 145

7.3 组合问题中的贪心法 148

7.3.1 背包问题 148

7.3.2 活动安排问题 151

7.3.3 多机调度问题 153

7.4 实验项目——霍夫曼编码 155

阅读材料——模拟退火算法 157

习题7 159

第8章 回溯法 161

8.1 概述 161

8.1.1 问题的解空间 161

8.1.2 解空间树的动态搜索（1） 163

8.1.3 回溯法的求解过程 165

8.1.4 回溯法的时间性能 166

8.2 图问题中的回溯法 168

8.2.1 图着色问题 168

8.2.2 哈密顿回路问题 170

8.3.1 八皇后问题 173

8.3 组合问题中的回溯法 173

8.3.2 批处理作业调度问题 175

8.4 实验项目——0/1背包问题 177

阅读材料——禁忌搜索算法 178

习题8 180

第9章 分支限界法 183

9.1 概述 183

9.1.1 解空间树的动态搜索（2） 183

9.1.2 分支限界法的设计思想 186

9.1.3 分支限界法的时间性能 188

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

9.2.1 TSP问题 188

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

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

9.3.1 任务分配问题 195

9.3.2 批处理作业调度问题 198

9.4 实验项目——电路布线问题 200

阅读材料——免疫算法 201

习题9 203

第10章 概率算法 205

10.1 概述 205

10.1.1 概率算法的设计思想 206

10.1.2 随机数发生器 207

10.2 舍伍德（Sherwood）型概率算法 207

10.2.1 快速排序 208

10.2.2 选择问题 209

10.3 拉斯维加斯（Las Vegas）型概率算法 210

10.3.1 八皇后问题 211

10.3.2 整数因子分解问题 212

10.4 蒙特卡罗（Monte Carlo）型概率算法 214

10.4.1 主元素问题 215

10.4.2 素数测试问题 216

10.5 实验项目——随机数发生器 218

阅读材料——DNA计算与DNA计算机 219

习题10 221

11.1 概述 223

11.1.1 近似算法的设计思想 223

第11章 近似算法 223

11.1.2 近似算法的性能 224

11.2 图问题中的近似算法 225

11.2.1 顶点覆盖问题 225

11.2.2 TSP问题 226

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

11.3.1 装箱问题 228

11.3.2 子集和问题 231

11.4 实验项目——TSP问题的近似算法 235

阅读材料——量子密码技术 235

习题11 237

12.1 计算模型 239

第12章 计算复杂性理论 239

12.1.1 图灵机的基本模型 240

12.1.2 k带图灵机和时间复杂性 241

12.1.3 离线图灵机和空间复杂性 244

12.2 P类问题和NP类问题 245

12.2.1 非确定性图灵机 245

12.2.2 P类语言和NP类语言 246

12.3 NP完全问题 247

12.3.1 多项式时间变换 247

12.3.2 Cook定理 248

1 2.4 实验项目——NP完全问题树 251

阅读材料——算法优化策略 251

习题12 254

参考文献 255