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

第1章 算法概述 1

1.1算法与程序 1

1.2算法复杂性分析 1

习题1 5

第2章 递归与分治策略 7

2.1递归的概念 7

2.2分治法的基本思想 13

2.3二分搜索技术 14

2.4大整数的乘法 15

2.5Strassen矩阵乘法 16

2.6棋盘覆盖 17

2.7合并排序 19

2.8快速排序 21

2.9线性时间选择 24

2.10最接近点对问题 26

2.11循环赛日程表 33

习题2 34

第3章 动态规划 40

3.1矩阵连乘问题 41

3.2动态规划算法的基本要素 45

3.3最长公共子序列 48

3.4最大子段和 52

3.5凸多边形最优三角剖分 57

3.6多边形游戏 60

3.7图像压缩 64

3.8电路布线 66

3.9流水作业调度 68

3.100-1背包问题 71

3.11最优二叉搜索树 76

3.12动态规划加速原理 78

习题3 82

第4章 贪心算法 86

4.1活动安排问题 87

4.2贪心算法的基本要素 89

4.3最优装载 91

4.4哈夫曼编码 93

第7章 概率算法 98

4.5单源最短路径 98

4.6最小生成树 100

4.7多机调度问题 105

4.8贪心算法的理论基础 106

习题4 113

第5章 回溯法 117

5.1回溯法的算法框架 117

5.2装载问题 122

5.3批处理作业调度 129

5.4符号三角形问题 132

5.5n后问题 134

5.60-1背包问题 138

5.7最大团问题 141

5.8图的m着色问题 143

5.9旅行售货员问题 146

5.10圆排列问题 148

5.11电路板排列问题 151

5.12连续邮资问题 154

5.13回溯法的效率分析 156

习题5 159

第6章 分支限界法 163

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

6.2单源最短路径问题 166

6.3装载问题 168

6.4布线问题 176

6.50-1背包问题 179

6.6最大团问题 183

6.7旅行售货员问题 186

6.8电路板排列问题 189

6.9批处理作业调度 192

习题6 196

7.1随机数 199

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

7.2数值概率算法 201

7.2.2计算定积分 202

7.2.3解非线性方程组 204

7.3舍伍德（Sherwood）算法 206

7.3.1线性时间选择算法 206

7.3.2搜索有序表 208

7.3.3跳跃表 212

7.4拉斯维加斯（Las Vegas）算法 218

7.4.1n后问题 219

7.4.2整数因子分解 223

7.5蒙特卡罗（Monte Carlo）算法 224

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

7.5.2主元素问题 226

7.5.3素数测试 228

习题7 230

8.1线性规划问题和单纯形算法 234

8.1.1线性规划问题及其表示 234

第8章 线性规划与网络流 234

8.1.2线性规划基本定理 235

8.1.3约束标准型线性规划问题的单纯形算法 235

8.1.4将一般问题转化为约束标准型 239

8.1.5一般线性规划问题的2阶段单纯形算法 239

8.1.6单纯形算法的描述和实现 240

8.1.7退化情形的处理 246

8.1.8应用举例 246

8.2.1网络与流 248

8.2最大网络流问题 248

8.2.2增广路算法 253

8.2.3预流推进算法 257

8.2.4最大流问题的变换与应用 262

8.3最小费用流问题 269

8.3.1最小费用流 269

8.3.2消圈算法 270

8.3.3最小费用路算法 272

8.3.4网络单纯形算法 274

8.3.5最小费用流问题的变换与应用 281

习题8 289

第9章 NP完全性理论与近似算法 293

9.1计算模型 293

9.1.1随机存取机RAM 293

9.1.2随机存取存储程序机RASP 296

9.1.3图灵机 297

9.2P类与NP类问题 298

9.2.1非确定性图灵机 298

9.2.2P类与NP类语言 299

9.2.3多项式时间验证 300

9.3NP完全问题 301

9.3.1多项式时间变换 301

9.3.2一些典型的NP完全问题 302

9.4NP完全问题的近似算法 303

9.4.1近似算法的性能 304

9.4.2顶点覆盖问题的近似算法 305

9.4.3旅行售货员问题近似算法 306

9.4.4集合覆盖问题的近似算法 309

9.4.5子集和问题的近似算法 311

习题9 314

附录C++概要 319

1．变量、指针和引用 319

2．函数与参数传递 320

3．c++的类 321

4．类的对象 321

7．友元函数 322

6．运算符重载 322

5．构造函数与析构函数 322

8．内联函数 323

9．结构 323

10．联合 323

11．异常 323

12．模板 324

13．动态存储分配 326

参考文献 328