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

第1章 绪论 1

第2章 算法复杂度与问题的下界 10

2.1 算法的时间复杂度 10

2.2 最好、平均和最坏情况的算法分析 12

2.3 问题的下界 24

2.4 排序的最坏情况下界 25

2.5 堆排序：在最坏情况下最优的排序算法 28

2.6 排序的平均情况下界 33

2.7 通过神谕改进下界 35

2.8 通过问题转换求下界 36

2.9 注释与参考 37

2.10 进一步的阅读资料 38

习题 38

第3章 贪心法 40

3.1 生成最小生成树的Kruskal算法 42

3.2 生成最小生成树的Prim算法 44

3.3 单源最短路径问题 46

3.4 二路归并问题 50

3.5 用贪心法解决最小圈基问题 54

3.6 用贪心法解决2终端一对多问题 56

3.7 用贪心法解决1螺旋多边形最小合作警卫问题 59

3.8 实验结果 61

3.9 注释与参考 62

3.10 进一步的阅读资料 62

习题 63

第4章 分治策略 65

4.1 求2维极大点问题 66

4.2 最近点对问题 67

4.3 凸包问题 69

4.4 用分治策略构造Voronoi图 71

4.5 Voronoi图的应用 77

4.6 快速傅里叶变换 79

4.7 实验结果 82

4.8 注释与参考 82

4.9 进一步的阅读资料 83

习题 83

第5章 树搜索策略 85

5.1 广度优先搜索 87

5.2 深度优先搜索 88

5.3 爬山法 89

5.4 最佳优先搜索策略 90

5.5 分支限界策略 91

5.6 用分支限界策略解决人员分配问题 93

5.7 用分支限界策略解决旅行商优化问题 95

5.8 用分支限界策略解决0/1背包问题 99

5.9 用分支限界方法解决作业调度问题 102

5.10 A＊算法 106

5.11 用特殊的A＊算法解决通道路线问题 110

5.12 用A＊算法解决线性分块编码译码问题 113

5.13 实验结果 115

5.14 注释与参考 116

5.15 进一步的阅读资料 116

习题 117

第6章 剪枝搜索方法 119

6.1 方法概述 119

6.2 选择问题 119

6.3 两变量线性规划 121

6.4 1圆心问题 128

6.5 实验结果 132

6.6 注释与参考 133

6.7 进一步的阅读资料 133

习题 133

第7章 动态规划方法 134

7.1 资源配置问题 137

7.2 最长公共子序列问题 138

7.3 2序列比对问题 140

7.4 RNA最大碱基对匹配问题 143

7.5 0/1背包问题 150

7.6 最优二叉树问题 151

7.7 树的带权完全支配问题 154

7.8 树的带权单步图边的搜索问题 159

7.9 用动态规划方法解决1螺旋多边形m守卫路由问题 163

7.10 实验结果 165

7.11 注释与参考 165

7.12 进一步的阅读资料 166

习题 167

第8章 NP完全性理论 169

8.1 关于NP完全性理论的非形式化讨论 169

8.2 判定问题 170

8.3 可满足性问题 171

8.4 NP问题 176

8.5 库克定理 177

8.6 NP完全问题 184

8.7 证明NP完全性的例子 186

8.8 2可满足性问题 201

8.9 注释与参考 204

8.10 进一步的阅读资料 204

习题 205

第9章 近似算法 207

9.1 顶点覆盖问题的近似算法 207

9.2 欧几里得旅行商问题的近似算法 208

9.3 特殊瓶颈旅行商问题的近似算法 209

9.4 特殊瓶颈加权k供应商问题的近似算法 213

9.5 装箱问题的近似算法 217

9.6 直线m中心问题的最优近似算法 218

9.7 多序列比对问题的近似算法 220

9.8 对换排序问题的2近似算法 225

9.9 多项式时间近似方案 230

9.10 最小路径代价生成树问题的2近似算法 239

9.11 最小路径代价生成树问题的PTAS 241

9.12 NPO完全性 245

9.13 注释与参考 250

9.14 进一步的阅读资料 251

习题 252

第10章 分摊分析 254

10.1 使用势能函数的例子 254

10.2 斜堆的分摊分析 256

10.3 AVL树的分摊分析 259

10.4 自组织顺序检索启发式方法的分摊分析 261

10.5 配对堆及其分摊分析 264

10.6 不相交集合并算法的分摊分析 275

10.7 一些磁盘调度算法的分摊分析 284

10.8 实验结果 289

10.9 注释与参考 290

10.10 进一步的阅读资料 290

习题 290

第11章 随机算法 291

11.1 解决最近点对问题的随机算法 291

11.2 随机最近点对问题的平均性能 293

11.3 素数测试的随机算法 295

11.4 模式匹配的随机算法 297

11.5 交互证明的随机算法 300

11.6 最小生成树的随机线性时间算法 302

11.7 注释与参考 305

11.8 进一步的阅读资料 305

习题 306

第12章 在线算法 307

12.1 用贪心法解决在线欧几里得生成树问题 308

12.2 在线k服务员问题及解决定义在平面树上该问题的贪心算法 310

12.3 基于平衡策略的在线穿越障碍算法 315

12.4 用补偿策略求解在线二分匹配问题 322

12.5 用适中策略解决在线m台机器调度问题 326

12.6 基于排除策略的三个计算几何问题的在线算法 331

12.7 基于随机策略的在线生成树算法 335

12.8 注释与参考 338

12.9 进一步的阅读资料 339

习题 340

参考文献 341