分类:编程开发
语言:简体中文
大小:未知
发布时间:13-06-28
第一部分 基础工具.第1章 算法分析 21.1 算法的分析方法学 21.1.1 伪代码 41.1.2 随机存取机(ram)模型 51.1.3 统计基本操作的数量 61.1.4 递归算法分析 71.2 渐近符号 81.2.1 大o符号 81.2.2 与大“o”相关的渐近符号 101.2.3 渐近表示的重要性 121.3 数学概览 131.3.1 求和 131.3.2 对数和指数 141.3.3 简单证明技术 161.3.4 概率基础 181.4 算法分析案例研究 201.4.1 二次时间前缀平均值算法 211.4.2 线性时间前缀平均值算法 221.5 平摊方法 22.1.5.1 平摊技术 231.5.2 扩展数组实现分析 251.6 实验 281.6.1 实验组织 281.6.2 数据分析和可视化 291.7 习题 31基础题 31创新题 33程序设计 351.8 本章注记 36第2章 基本数据结构 372.1 栈和队列 372.1.1 栈 372.1.2 队列 402.2 向量、表和序列 432.2.1 向量 432.2.2 表 442.2.3 序列 482.3 树 492.3.1 树抽象数据类型 512.3.2 树的遍历 522.3.3 二叉树 552.3.4 表示树的数据结构 602.4 优先队列和堆 622.4.1 优先队列抽象数据类型 632.4.2 pq排序、选择排序和插入排序 642.4.3 堆数据结构 662.4.4 堆排序 712.5 字典与散列表 762.5.1 无序字典adt 762.5.2 散列表 772.5.3 散列函数 782.5.4 压缩映射 802.5.5 冲突处理模式 802.5.6 通用散列 832.6 java示例:堆 852.7 习题 87基础题 87创新题 89程序设计 912.8 本章注记 91第3章 查找树和跳跃表 933.1 有序字典和二叉查找树 943.1.1 有序表 943.1.2 二叉查找树 963.1.3 二叉查找树中的查找 963.1.4 二叉查找树中的插入 983.1.5 二叉查找树中的删除 993.1.6 二叉查找树的性能 1003.2 avl树 1013.2.1 更新操作 1023.2.2 性能 1053.3 深度有界查找树 1063.3.1 多路查找树 1063.3.2 (2,4)树 1083.3.3 红黑树 1133.4 伸展树 1233.4.1 伸展 1233.4.2 伸展过程的平摊分析 1283.5 跳跃表 1313.5.1 查找 1323.5.2 更新操作 1333.5.3 跳跃表的概率分析 1353.6 java示例:avl树和红黑树 1363.6.1 avl树的java实现 1383.6.2 红黑树的java实现 1413.7 习题 143基础题 143创新题 144程序设计 1453.8 本章注记 146第4章 排序、集合和选择 1474.1 归并排序 1474.1.1 分治法 1484.1.2 归并排序和递归方程 1514.2 集合抽象数据类型 1524.2.1 简单的集合实现 1524.2.2 具有union-find操作的划分 1534.2.3 基于树的划分实现 1544.3 快速排序 1594.4 基于比较的排序下界 1624.5 桶排序和基数排序 1634.5.1 桶排序 1634.5.2 基数排序 1644.6 比较排序算法 1654.7 选择 1664.7.1 剪枝-查找法 1664.7.2 随机化快速选择 1664.7.3 随机化快速选择分析 1674.8 java示例:原位快速排序 1684.9 习题 170基础题 170创新题 171程序设计 1724.10 本章注记 173第5章 基本技术 1745.1 贪心法 1745.1.1 背包问题 1755.1.2 任务调度 1765.2 分治法 1775.2.1 分治递归方程 1775.2.2 整数相乘 1825.2.3 矩阵相乘 1835.3 动态规划 1855.3.1 矩阵链乘 1855.3.2 一般技术 1875.3.3 0-1背包问题 1885.4 习题 190基础题 190创新题 191程序设计 1915.5 本章注记 192第二部分 图算法第6章 图 1946.1 图抽象数据类型 1946.2 图的数据结构 1996.2.1 边表结构 1996.2.2 邻接表结构 2016.2.3 邻接矩阵结构 2036.3 图的遍历 2046.3.1 深度优先查找 2046.3.2 双连通分量 2066.3.3 广度优先查找 2116.4 有向图 2136.4.1 遍历有向图 2146.4.2 传递闭包 2166.4.3 dfs和垃圾收集 2186.4.4 有向无环图 2196.5 java示例:深度优先查找 2226.5.1 修饰模式 2226.5.2 dfs引擎 2236.5.3 模板方法设计模式 2246.6 习题 227基础题 227创新题 228程序设计 2296.7 本章注记 229第7章 加权图 2307.1 单源点最短路径 2317.1.1 dijkstra算法 2317.1.2 bellman-ford最短路径算法 2367.1.3 有向无环图中的最短路径 2387.2 所有顶点对之间的最短路径 2407.2.1 动态规划最短路径算法.. 2407.2.2 利用矩阵相乘计算最短路径 2417.3 最小生成树 2447.3.1 kruskal算法 2457.3.2 prim-jarník算法 2497.3.3 bar?vka算法 2517.3.4 mst算法比较 2537.4 java示例:dijkstra算法 2537.5 习题 256基础题 256创新题 256程序设计 2577.6 本章注记 258第8章 网络流和匹配 2598.1 流和割 2608.1.1 流网络 2608.1.2 割 2618.2 最大流 2628.2.1 剩余容量和增大路径 2628.2.2 ford-fulkerson算法 2648.2.3 ford-fulkerson算法分析 2668.2.4 edmonds-karp算法 2678.3 最大二分匹配 2698.4 最小代价流 2708.4.1 增大回路 2718.4.2 连续最短路径 2728.4.3 修改权值 2738.5 java示例:最小代价流 2768.6 习题 281基础题 281创新题 281程序设计 2828.7 本章注记 282第三部分 因特网算法第9章 文本处理 2849.1 串和模式匹配算法 2849.1.1 串操作 2859.1.2 蛮力模式匹配 2869.1.3 boyer-moore算法 2879.1.4 knuth-morris-pratt算法 2899.2 trie 2929.2.1 标准trie 2929.2.2 压缩trie 2949.2.3 后缀trie 2959.2.4 搜索引擎 2989.3 文本压缩 2989.3.1 赫夫曼编码算法 2999.3.2 修正贪心法 3009.4 文本相似性测试 3019.4.1 最长公共子序列问题 3019.4.2 应用动态规划求解lcs问题 3019.5 习题 303基础题 303创新题 304程序设计 3059.6 本章注记 305第10章 数论和密码学 30610.1 与数有关的基本算法 30610.1.1 基本数论的一些事实 30710.1.2 欧几里得gcd算法 30810.1.3 模运算 31010.1.4 模指数运算 31310.1.5 模乘法逆元 31510.1.6 素性测试 31610.2 密码计算 32010.2.1 对称加密模式 32110.2.2 公钥密码系统 32210.2.3 rsa密码系统 32310.2.4 el gamal密码系统 32510.3 信息安全算法和协议 32610.3.1 单向散列函数 32610.3.2 时间戳和认证字典 32710.3.3 硬币抛掷和比特承诺 32710.3.4 安全电子传输(set)协议 32810.3.5 密钥分发和交换 32910.4 快速傅里叶变换 33010.4.1 本原单位根 33210.4.2 离散傅里叶变换 33310.4.3 快速傅里叶变换算法 33510.4.4 大整数相乘 33710.5 java示例:fft 33910.6 习题 345基础题 345创新题 345程序设计 34610.7 本章注记 346第11章 网络算法 34811.1 复杂性测度和模型 34911.1.1 网络协议栈 34911.1.2 消息传递模型 34911.1.3 网络算法的复杂性测度 35011.2 基本分布式算法 35111.2.1 环网上的领导人选举 35111.2.2 树网上的领导人选举 35411.2.3 广度优先查找 35611.2.4 最小生成树 35911.3 广播路由和单播路由 36011.3.1 广播路由的洪泛算法 36011.3.2 单播路由的距离矢量算法 36111.3.3 单播路由的链路-状态算法 36211.4 多播路由 36311.4.1 逆向路径转发 36311.4.2 中心树 36411.4.3 steiner树 36511.5 习题 367基础题 367创新题 367程序设计 36911.6 本章注记 369第四部分 其他主题第12章 计算几何 37212.1 范围树 37212.1.1 一维范围查找 37312.1.2 二维范围查找 37512.2 优先查找树 37712.2.1 构造一棵优先查找树 37812.2.2 优先查找树中的查找 37812.2.3 优先范围树 38012.3 四叉树和k-d树 38012.3.1 四叉树 38112.3.2 k-d树 38212.4 平面扫描技术 38312.4.1 正交线段相交 38312.4.2 查找最近点对 38512.5 凸包 38812.5.1 几何对象表示 38812.5.2 点方位测试 38912.5.3 凸包的基本性质 39012.5.4 礼品包扎算法 39212.5.5 graham扫描算法 39312.6 java示例:凸包 39512.7 习题 398基础题 398创新题 398程序设计 40012.8 本章注记 400第13章 np完全性 40113.1 p类和np类 40213.1.1 定义复杂类p和复杂类np 40213.1.2 np中的一些有趣问题 40413.2 np完全性 40613.2.1 多项式时间归约和np困难度 40613.2.2 cook-levin定理 40713.3 重要的np完全问题 40813.3.1 cnf-sat和3sat 41013.3.2 vertex-cover 41213.3.3 clique和set-cover 41313.3.4 subset-sum和knapsack 41513.3.5 hamiltonian-cycle和tsp 41713.4 近似算法 41913.4.1 多项式时间的近似模式 42013.4.2 vertex-cover的2-近似算法 42213.4.3 tsp特例的2-近似算法 42313.4.4 set-cover的对数近似算法 42413.5 回溯法和分枝限界法 42613.5.1 回溯法 42613.5.2 分枝限界法 42913.6 习题 433基础题 433创新题 434程序设计 43513.7 本章注记 435第14章 算法框架 43714.1 外存算法 43714.1.1 分层的存储器管理 43814.1.2 (a, 树和b树 44014.1.3 外存排序 44314.2 并行算法 44514.2.1 并行计算模型 44514.2.2 简单并行分治法 44614.2.3 串行子集和brent定理 44714.2.4 递归倍增 44714.2.5 并行归并和排序 45014.2.6 找出凸多边形的直径 45014.3 在线算法 45214.3.1 高速缓存算法 45214.3.2 拍卖策略 45714.3.3 竞争查找树 45814.4 习题 461基础题 461创新题 461程序设计 46214.5 本章注记 462附录a 有用的数学知识 464a.1 对数和指数 464a.2 整型函数和关系 465a.3 求和 466a.4 有用的数学技术 467参考书目 468索引... 476
...