算法概论PDF电子书下载

第0章 序言 1

书籍和算法 1

从Fibonacci数列开始 3

大O符号 6

习题 9

第1章 数字的算法 13

基本算术 13

加法 13

乘法和除法 16

模运算 18

模的加法和乘法 21

模的指数运算 21

Euclid的最大公因数算法 23

Euclid算法的一种扩展 24

模的除法 27

素性测试 28

密码学 35

密钥机制：一次一密乱码本和AES 36

RSA 38

通用散列表 40

散列表 41

散列函数族 41

习题 44

第2章 分治算法 53

乘法 53

递推式 57

合并排序 59

寻找中项 62

矩阵乘法 66

快速Fourier变换 67

多项式的另一种表示法 68

计算步骤的分治实现 71

插值 75

快速Fourier变换的细节 78

习题 83

第3章 图的分解 93

为什么是图 93

无向图的深度优先搜索 96

迷宫探索 96

深度优先搜索 99

无向图的连通性 100

前序和后序 100

有向图的深度优先搜索 101

边的类型 101

有向无环图 103

强连通部件 105

定义有向图的连通性 105

一个有效的算法 106

习题 110

第4章 图中的路径 119

距离 119

广度优先搜索 120

边的长度 122

Dijkstra算法 123

广度优先搜索的一个改进 123

另一种解释 127

运行时间 129

优先队列的实现 129

数组 129

二分堆 130

d堆 131

含有负边的图的最短路径 131

负边 131

负环 135

有向无环图中的最短路径 135

习题 136

第5章 贪心算法 143

最小生成树 143

一个贪心方法 144

分割性质 146

Kruskal算法 147

一种用于分离集的数据结构 148

Prim算法 153

Huffman编码 156

Horn公式 160

集合覆盖 162

习题 164

第6章 动态规划 173

重新审视有向无环图的最短路径问题 173

最长递增子序列 175

编辑距离 177

背包问题 183

矩阵链式相乘 186

最短路径问题 189

树中的独立集 193

习题 195

第7章 线性规划与归约 205

线性规划简介 205

示例：利润最大化 206

示例：生产计划 210

示例：最优带宽分配 212

线性规划的变体 214

网络流 216

石油运输 216

最大流 216

对算法的深入观察 217

最优性的保证 221

算法的效率 222

二部图的匹配 222

对偶 224

零和博弈（游戏） 228

单纯形算法 232

n维空间中的顶点和邻居 232

算法 233

补遗 236

单纯形法的运行时间 238

后记：电路值 241

习题 243

第8章NP-完全问题 253

搜索问题 253

NP-完全问题 264

所有的归约 268

习题 286

第9章NP-完全问题的处理 293

智能穷举搜索 294

回溯 294

分支定界 297

近似算法 299

顶点覆盖 300

聚类 302

TSP 304

背包问题 306

逼近的层次 307

局部搜索中的启发方法 308

重新审视旅行商问题 308

图划分 311

处理局部最优 313

习题 316

第10章 量子算法 321

量子位元、叠加状态和度量 321

算法设计 325

量子傅立叶变换 327

周期性 329

量子电路 331

基本量子门 331

量子电路的两种基本类型 332

量子傅立叶变换电路 333

将因子分解问题转化为周期求解问题 335

因子分解的量子算法 337

习题 339

历史背景及深入阅读的资料 343