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

第1章 入门 1

1.1问题 1

1.2算法的概念 1

1.3算法的正确性 3

1.4算法的效率 5

1.5问题的下界 9

1.6小结 10

习题 11

实验题 12

第2章 渐近符号 13

2.1 Θ符号 13

2.2 Ο符号 15

2.3 Ω符号 16

2.4渐近符号的性质 17

2.5常用函数的直观含义 18

2.6小结 18

习题 19

第3章 算法分析方法 20

3.1概率分析 20

3.2分摊分析 22

3.2.1合计方法 23

3.2.2记账方法 25

3.2.3势能方法 27

3.3实验分析 29

3.4小结 30

习题 31

第4章 递归 32

4.1算法思想 32

4.1.1递归算法的应用 33

4.1.2递归与迭代 40

4.2递归方程的求解 41

4.2.1替换方法 41

4.2.2递归树方法 43

4.2.3公式法 45

4.3多项式求值实验 47

4.4小结 48

习题 48

实验题 49

第5章 分治算法 50

5.1算法思想 50

5.2合并排序 51

5.3快速排序 53

5.4大整数乘法 56

5.5矩阵乘法 58

5.6残缺棋盘游戏 59

5.7快速傅里叶变换（FFT） 62

5.8小结 63

习题 63

实验题 65

第6章 动态规划 66

6.1算法思想 66

6.2装配线调度问题 68

6.3矩阵链乘法问题 73

6.4最长公共子序列问题 77

6.5 0/1背包问题 81

6.6最优二叉搜索树问题 84

6.7动态规划的基本性质 88

6.8小结 92

习题 92

实验题 94

第7章 贪心算法 95

7.1算法思想 95

7.2任务选择问题 95

7.3背包问题 100

7.4哈夫曼编码问题 102

7.5缓存维护问题 106

7.6任务选择问题实验 108

7.7小结 109

习题 109

实验题 111

第8章 图算法 112

8.1图的搜索问题 113

8.1.1宽度优先搜索 113

8.1.2深度优先搜索 117

8.2最小生成树问题 121

8.2.1 Kruskal算法 122

8.2.2 Prim算法 124

8.3最短路径问题 125

8.3.1单个源点的最短路径问题 128

8.3.2所有点对的最短路径问题 131

8.4小结 134

习题 135

实验题 137

第9章 网络流与匹配 138

9.1最大流问题 138

9.1.1 FordFulkerson方法 140

9.1.2最短路径增广算法 145

9.1.3 Dinic算法 148

9.1.4 MPM算法 151

9.1.5最大流问题的变形 152

9.2最小费用流问题 153

9.2.1消除回路算法 154

9.2.2最小费用路算法 156

9.2.3最小费用路算法的改进 158

9.3匹配问题 160

9.3.1二分图匹配 163

9.3.2一般图的匹配 167

9.4小结 172

习题 172

实验题 174

第10章 线性规划 175

10.1线性规划问题 175

10.1.1线性规划问题的标准形式 176

10.1.2线性规划问题的松弛形式 178

10.2求解算法 180

10.2.1图解法 180

10.2.2单纯形算法 181

10.3对偶 188

10.4小结 192

习题 192

实验题 193

第11章NP完全理论 194

11.1判定问题 195

11.2 P和NP 197

11.3 NPC 201

11.3.1 NPC的定义 201

11.3.2电路可满足性问题 203

11.4 NPC的证明 206

11.4.1可满足性问题 206

11.4.2 3-CNF可满足性问题 208

11.4.3团问题 210

11.4.4顶点覆盖问题 212

11.5其他NP完全问题 213

11.6小结 215

习题 215

第12章 回溯 218

12.1算法思想 218

12.2装载问题 222

12.3 0/1背包问题 226

12.4着色问题 228

12.5 n皇后问题 230

12.6旅行商问题 232

12.7流水作业调度问题 234

12.8零件切割问题 236

12.9小结 238

习题 238

实验题 240

第13章 分支限界 241

13.1算法思想 241

13.2装载问题 243

13.3 0/1背包问题 251

13.4可满足性问题 254

13.5旅行商问题 256

13.6流水作业调度问题 258

13.7 0/1背包问题实验 260

13.8小结 261

习题 262

实验题 263

第14章 启发式搜索 264

14.1算法思想 264

14.2 A搜索 265

14.2.1最短路径问题 267

14.2.2 8数字问题 268

14.3博弈搜索算法 271

14.3.1α和β剪支 273

14.3.2分硬币游戏 275

14.3.3井字博弈 275

14.4小结 281

习题 281

实验题 283

第15章 数论 284

15.1数论基础 284

15.2最大公约数 287

15.3同余 289

15.4模幂运算 294

15.5数论的应用 295

15.5.1 Hash函数 295

15.5.2 RSA公钥加密系统 296

15.6小结 299

习题 299

实验题 300

第16章 计算几何 301

16.1叉积及其应用 301

16.2计算任意线段的交点 304

16.3凸包 306

16.3.1礼物包装算法 307

16.3.2 Graham扫描法 309

16.3.3分治算法求凸包 310

16.4最近点对 316

16.5 Voronoi图 318

16.5.1 Voronoi图的定义及其性质 318

16.5.2 Voronoi图的构造 321

16.5.3 Voronoi图的应用 325

16.6小结 327

习题 327

实验题 328

参考文献 329