算法基础PDF电子书下载

目录 1

第1章　预备知识 1

1.1 简介 1

1.2　什么是算法 1

1.3　程序符号 4

1.4　数学符号 5

1.4.1 命题演算 5

1.4.2　集合论 6

1.4.3　整数、实数和区间 7

1.4.4　函数和关系 7

1.4.5　量词 8

1.4.6　累加与累积 9

1.4.7　杂项 10

1.5　证明技巧1——反证法 11

1.6　证明技巧2——数学归纳法 12

1.6.1　数学归纳法的法则 15

1.6.2　不同颜色的马 18

1.6.3　一般化的数学归纳法 19

1.6.4　构造性归纳 22

1.7　一些回顾 24

1.7.1 极限 24

1.7.2　简单级数 26

1.7.3　基本组合 30

1.7.4 概率基础 32

1.8　习题 38

1.9　参考与深入阅读 43

2.2　问题和实例 45

2.1 简介 45

第2章　基本算法 45

2.3　算法的效率 46

2.4　平均和最坏情况分析 48

2.5　什么是基本运算？ 50

2.6　为什么寻求效率？ 52

2.7　一些例子 53

2.7.1　计算行列式的值 53

2.7.2　排序 53

2.7.3　大整数的乘法 55

2.7.4 计算最大公约数 55

2.7.5　计算斐波纳契序列 56

2.7.6　傅立叶变换 57

2.9 习题 58

2.8　什么时候算法是确定的？ 58

2.10　参考与深入阅读 61

第3章　渐近记法 62

3.1 引言 62

3.2　同阶记法 62

3.3　其他渐近记法 67

3.3.1 Ω记法 67

3.3.2　Θ记法 68

3.4　条件渐近记法 69

3.5 具有多个参数的渐近记法 71

3.6　渐近记法的操作 71

3.7　习题 72

3.8　参考与深入阅读 75

4.2.1 先后顺序 76

4.2　分析控制结构 76

4.2.2　For循环 76

第4章　算法分析 76

4.1 引言 76

4.2.3　递调用 78

4.2.4 while和repeat循环 79

4.3　使用标称 80

4.4 补充例子 82

4.4.1 选择排序 82

4.4.2　插入排序 83

4.4.3　欧儿里德算法 83

4.4.4　汉诺塔 85

4.4.5 计算行列式的值 86

4.5　平均情况分析 86

4.6　分期分析 87

4.6.1 势函数 88

4.7.1 推测 90

4.6.2　账户戏法 90

4.7　求解递归式 90

4.7.2　齐次递归式 92

4.7.3　非齐次递归式 96

4.7.4　变量变换 100

4.7.5　范围转换 105

4.7.6　渐近递归式 106

4.8　习题 107

4.9　参考与深入阅读 113

第5章　一些数据结构 114

5.1　数组、栈和队列 114

5.2　记录和指针 116

5.3　链表 117

5.4 图 118

5.5　树 119

5.6　关联表 124

5.7　堆 126

5.8　二项堆 132

5.9　不相交集结构 136

5.10　习题 141

5.11 参考与深入阅读 144

第6章　贪婪算法 146

6.1 找零钱（1） 146

6.2　贪婪算法的一般特性 147

6.3　图：最小生成树 148

6.3.1 Kruskal算法 150

6.3.2　Prim算法 152

6.4　图：最短路径 154

6.5　背包问题（1） 157

6.6.1　最小化时间 160

6.6 日程安排 160

6.6.2　有期限的日程安排 162

6.7　习题 168

6.8　参考与深入阅读 170

第7章　分治算法 171

7.1　简介：大整数乘法 171

7.2　通用模板 174

7.3　二分搜索 176

7.4　排序 178

7.4.1 归并排序 178

7.4.2　快速排序 180

7.5　查找中值 184

7.6　矩阵乘法 188

7.7　求幂 189

7.8　综合：密码学简介 192

7.9　习题 194

7.10　参考与深入阅读 200

第8章　动态规划 202

8.1　两个简单的例子 202

8.1.1　计算二项式系数 202

8.1.2　系列赛 203

8.2　找零钱（2） 205

8.3　最优性原则 207

8.4　背包问题（2） 208

8.5　最短路径 209

8.6　链式矩阵乘法 211

8.7　使用递归 214

8.8　存储函数 216

8.9　习题 217

8.10　参考与深入阅读 221

9.1 图和游戏：简介 223

第9章　搜索图 223

9.2　遍历树 228

9.2.1　预处理 228

9.3　深度优先搜索：无向图 230

9.3.1　关节点 232

9.4　深度优先搜索：有向图 233

9.4.1 无环图：拓扑排序 234

9.5　广度优先搜索 236

9.6 回溯法 239

9.6.1　背包问题（3） 240

9.6.2　八皇后问题 242

9.6.3　通用模板 244

9.7　分支界限 244

9.7.1　分配任务问题 245

9.8　极小化原则 248

9.7.2　背包问题（4） 248

9.7.3　一般考虑 248

9.9　习题 251

9.10　参考与深入阅读 256

第10章　概率算法 257

10.1 简介 257

10.2　概率不意味着不确定 258

10.3　预期与平均时间 259

10.4　生成伪随机数 259

10.5　数值概率算法 261

10.5.1　Buffon的针 261

10.5.2　数值积分 264

10.5.3　概率计数 265

10.6.1　验证矩阵乘法 267

10.6　Monte Carlo算法 267

10.6.2　素数性测试 269

10.6.3　一个数可能是素数吗？ 272

10.6.4　随机优势的扩大 274

10.7　Las Vegas算法 276

10.7.1　重访八皇后问题 278

10.7.2　概率选择与排序 281

10.7.3　通用散列 282

10.7.4　大整数分解因数 284

10.8　习题 287

10.9　参考与深入阅读 293

第11章　并行算法 295

11.1　并行计算的模型 295

11.2　一些基本的技术 297

11.2.1　计算完全二叉树 297

11.2.2　指针倍增 298

11.3　工作量与效率 301

11.4　图论的两个例子 303

11.4.1　最短路径 303

11.4.2　连通分量 304

11.5　表达式的并行求值 308

11.6　并行排序网络 312

11.6.1　0-1原理 313

11.6.2　并行合并网络 314

11.6.3　改进的排序网络 315

11.7　并行排序 316

11.7.1　预备工作 316

11.7.2　核心思想 317

11.7.3　算法 317

11.7.4　细节概述 318

11.8 EREW和CRCW p-ram的一些注意点 319

11.9　分布式计算 320

11.10　习题 321

11.11　参考与深入阅读 323

第12章　计算复杂性 324

12.1　引言：一个简单的例子 324

12.2　信息-理论论证 325

12.2.1　排序的复杂性 327

12.2.2　复杂性对算法设计的帮助 330

12.3　对手论证 331

12.3.1　查找数组的最大项 332

12.3.2　测试图的连通性 333

12.3.3　中值再考察 333

12.4　线性归约 335

12.4.1　形式定义 337

12.4.2　矩阵问题中的归约 338

12.4.3　最短路径问题中的归约 342

12.5　NP完全性介绍 344

12.5.1 P和NP类 345

1 2.5.2　多项式归约 348

12.5.3　NP完全性问题 351

12.5.4　一些NP完全性证明 353

12.5.5 NP难问题 356

12.5.6　非确定性算法 357

12.6　复杂性类纵览 359

12.7　习题 362

12.8　参考与深入阅读 366

第13章　启发式和近似算法 369

13.1　启发式算法 369

13.1.1 图着色 369

13.1.2　旅行商 371

13.2　近似算法 372

13.2.1　度量旅行商 372

13.2.2　背包问题（5） 374

13.2.3　装箱问题 375

13.3　NP难近似问题 377

13.3.1　绝对难近似问题 378

13.3.2　相对难近似问题 379

13.4　相同，惟一不同 380

13.5　近似模式 383

13.5.1　重访装箱问题 383

13.5.2　背包问题（6） 384

13.6　习题 386

13.7　参考与深入阅读 389

参考文献 390