包邮算法概论

目 录
第0章 序言 10.1 书籍和算法 10.2 从Fibonacci数列开始 30.3 大O符号 6习题 9第1章 数字的算法 131.1 基本算术 131.1.1 加法 131.1.2 乘法和除法 161.2 模运算 181.2.1 模的加法和乘法 211.2.2 模的指数运算 211.2.3 Euclid的*大公因数算法 231.2.4 Euclid算法的一种扩展 241.2.5 模的除法 271.3 素性测试 281.4 密码学 351.4.1 密钥机制：一次一密乱码本和AES 361.4.2 RSA 381.5 通用散列表 401.5.1 散列表 411.5.2 散列函数族 41习题 44第2章 分治算法 532.1 乘法 532.2 递推式 572.3 合并排序 592.4 寻找中项 622.5 矩阵乘法 662.6 快速Fourier变换 672.6.1 多项式的另一种表示法 682.6.2 计算步骤的分治实现 712.6.3 插值 752.6.4 快速Fourier变换的细节 78习题 83第3章 图的分解 933.1 为什么是图 933.2 无向图的深度优先搜索 963.2.1 迷宫探索 963.2.2 深度优先搜索 993.2.3 无向图的连通性 1003.2.4 前序和后序 1003.3 有向图的深度优先搜索 1013.3.1 边的类型 1013.3.2 有向无环图 1033.4 强连通部件 1053.4.1 定义有向图的连通性 1053.4.2 一个有效的算法 106习题 110第4章 图中的路径 1194.1 距离 1194.2 广度优先搜索 1204.3 边的长度 1224.4 Dijkstra算法 1234.4.1 广度优先搜索的一个改进 1234.4.2 另一种解释 1274.4.3 运行时间 1294.5 优先队列的实现 1294.5.1 数组 1294.5.2 二分堆 1304.5.3 d堆 1314.6 含有负边的图的*短路径 1314.6.1 负边 1314.6.2 负环 1354.7 有向无环图中的*短路径 135习题 136第5章 贪心算法 1435.1 *小生成树 1435.1.1 一个贪心方法 1445.1.2 分割性质 1465.1.3 Kruskal算法 1475.1.4 一种用于分离集的数据结构 1485.1.5 Prim算法 1535.2 Huffman编码 1565.3 Horn公式 1605.4 集合覆盖 162习题 164第6章 动态规划 1736.1 重新审视有向无环图的*短路径问题 1736.2 *长递增子序列 1756.3 编辑距离 1776.4 背包问题 1836.5 矩阵链式相乘 1866.6 *短路径问题 1896.7 树中的独立集 193习题 195第7章 线性规划与归约 2057.1 线性规划简介 2057.1.1 示例：利润*大化 2067.1.2 示例：生产计划 2107.1.3 示例：*优带宽分配 2127.1.4 线性规划的变体 2147.2 网络流 2167.2.1 石油运输 2167.2.2 *大流 2167.2.3 对算法的深入观察 2177.2.4 *优性的保证 2217.2.5 算法的效率 2227.3 二部图的匹配 2227.4 对偶 2247.5 零和博弈(游戏) 2287.6 单纯形算法 2327.6.1 n维空间中的顶点和邻居 2327.6.2 算法 2337.6.3 补遗 2367.6.4 单纯形法的运行时间 2387.7 后记：电路值 241习题 243第8章 NP-完全问题 2538.1 搜索问题 2538.2 NP-完全问题 2648.3 所有的归约 268习题 286第9章 NP-完全问题的处理 2939.1 智能穷举搜索 2949.1.1 回溯 2949.1.2 分支定界 2979.2 近似算法 2999.2.1 顶点覆盖 3009.2.2 聚类 3029.2.3 TSP 3049.2.4 背包问题 3069.2.5 逼近的层次 3079.3 局部搜索中的启发方法 3089.3.1 重新审视旅行商问题 3089.3.2 图划分 3119.3.3 处理局部*优 313习题 316第10章 量子算法 32110.1 量子位元、叠加状态和度量 32110.2 算法设计 32510.3 量子傅立叶变换 32710.4 周期性 32910.5 量子电路 33110.5.1 基本量子门 33110.5.2 量子电路的两种基本类型 33210.5.3 量子傅立叶变换电路 33310.6 将因子分解问题转化为周期求解问题 33510.7 因子分解的量子算法 337习题 339历史背景及深入阅读的资料 343