第1章算法引论11.1算法与程序1

1.2表达算法的抽象机制1

1.3描述算法3

1.4算法复杂性分析13

小结16

习题17

第2章递归与分治策略19

2.1递归的概念19

2.2分治法的基本思想26

2.3二分搜索技术27

2.4大整数的乘法28

2.5Strassen矩阵乘法30

2.6棋盘覆盖32

2.7合并排序34

2.8快速排序37

2.9线性时间选择39

2.10最接近点对问题43

2.11循环赛日程表53

小结54

习题54

第3章动态规划61

3.1矩阵连乘问题62

目录3.2动态规划算法的基本要素67

3.3最长公共子序列71

3.4凸多边形最优三角剖分75

3.5多边形游戏79

3.6图像压缩82

3.7电路布线85

3.8流水作业调度88

3.901背包问题92

3.10最优二叉搜索树98

小结101

习题102

第4章贪心算法107

4.1活动安排问题107

4.2贪心算法的基本要素110

4.2.1贪心选择性质111

4.2.2最优子结构性质111

4.2.3贪心算法与动态规划算法的差异111

4.3最优装载114

4.4哈夫曼编码116

4.4.1前缀码117

4.4.2构造哈夫曼编码117

4.4.3哈夫曼算法的正确性119

4.5单源最短路径121

4.5.1算法基本思想121

4.5.2算法的正确性和计算复杂性123

4.6最小生成树125

4.6.1最小生成树性质125

4.6.2Prim算法126

4.6.3Kruskal算法128

4.7多机调度问题130

4.8贪心算法的理论基础133

4.8.1拟阵133

4.8.2带权拟阵的贪心算法134

4.8.3任务时间表问题137

小结141

习题141

第5章回溯法146

5.1回溯法的算法框架146

5.1.1问题的解空间146

5.1.2回溯法的基本思想147

5.1.3递归回溯149

5.1.4迭代回溯150

5.1.5子集树与排列树151

5.2装载问题152

5.3批处理作业调度160

5.4符号三角形问题162

5.5n后问题165

5.60\|1背包问题168

5.7最大团问题171

5.8图的m着色问题174

5.9旅行售货员问题177

5.10圆排列问题179

5.11电路板排列问题181

5.12连续邮资问题185

5.13回溯法的效率分析187

小结190

习题191

第6章分支限界法195

6.1分支限界法的基本思想195

6.2单源最短路径问题198

6.3装载问题202

6.4布线问题211

6.50\|1背包问题216

6.6最大团问题222

6.7旅行售货员问题225

6.8电路板排列问题229

6.9批处理作业调度232

小结237

习题238

第7章概率算法240

7.1随机数241

7.2数值概率算法244

7.2.1用随机投点法计算π值244

7.2.2计算定积分245

7.2.3解非线性方程组247

7.3舍伍德算法250

7.3.1线性时间选择算法250

7.3.2跳跃表252

7.4拉斯维加斯算法259

7.4.1n后问题260

7.4.2整数因子分解264

7.5蒙特卡罗算法266

7.5.1蒙特卡罗算法的基本思想266

7.5.2主元素问题268

7.5.3素数测试270

小结273

习题273

第8章NP完全性理论278

8.1计算模型279

8.1.1随机存取机RAM279

8.1.2随机存取存储程序机RASP287

8.1.3RAM模型的变形与简化291

8.1.4图灵机295

8.1.5图灵机模型与RAM模型的关系297

8.1.6问题变换与计算复杂性归约299

8.2P类与NP类问题301

8.2.1非确定性图灵机301

8.2.2P类与NP类语言302

8.2.3多项式时间验证304

8.3NP完全问题305

8.3.1多项式时间变换305

8.3.2Cook定理307

8.4一些典型的NP完全问题310

8.4.1合取范式的可满足性问题311

8.4.23元合取范式的可满足性问题312

8.4.3团问题313

8.4.4顶点覆盖问题314

8.4.5子集和问题315

8.4.6哈密顿回路问题317

8.4.7旅行售货员问题322

小结323

习题323

第9章近似算法326

9.1近似算法的性能327

9.2顶点覆盖问题的近似算法328

9.3旅行售货员问题近似算法329

9.3.1具有三角不等式性质的旅行售货员问题330

9.3.2一般的旅行售货员问题331

9.4集合覆盖问题的近似算法333

9.5子集和问题的近似算法336

9.5.1子集和问题的指数时间算法336

9.5.2子集和问题的完全多项式时间近似格式337

小结340

习题340

第10章算法优化策略345

10.1算法设计策略的比较与选择345

10.1.1最大子段和问题的简单算法345

10.1.2最大子段和问题的分治算法346

10.1.3最大子段和问题的动态规划算法348

10.1.4最大子段和问题与动态规划算法的推广349

10.2动态规划加速原理352

10.2.1货物储运问题352

10.2.2算法及其优化353

10.3问题的算法特征357

10.3.1贪心策略357

10.3.2对贪心策略的改进357

10.3.3算法三部曲359

10.3.4算法实现360

10.3.5算法复杂性366

10.4优化数据结构366

10.4.1带权区间最短路问题366

10.4.2算法设计思想367

10.4.3算法实现方案369

10.4.4并查集373

10.4.5可并优先队列376

10.5优化搜索策略380

小结388

习题388

词汇索引391

参考文献397