| 词条 | 计算机算法3 |
| 释义 | 百科名片作/译者：(美)霍罗威茨 冯博琴出版社：机械工业出版社 出版日期：2006年01月 ISBN：9787111176169 [十位:7111176162] 页数：452 重约：0.707KG 定价：￥55.00 内容提要本书是计算机算法在设计与分析文献的一本经典著作。书中介绍了算法和算法性能的基本知识,基本的数据结构知识,重点讨论了不同的算法设计策略,研究了下界理论等,提供了计算机算法的设计技术和有效的算法分析,以及大量的详细实例和实际应用。同时,对NP难和NP完全问题能否有效求解进行了分析。本书还汇聚了各种随机算法与并行算法的充分比较。 本书为读者提供了当前流行的对象设计语言C++的实现版本,适合作为高等院校计算机专业 教材,也是计算机算法方面的重要参考书。 图书目录第1章 导论 1.1 什么是算法 1.2 算法规范 1.2.1 引言 1.2.2 递归算法 1.3 性能分析 1.3.1 空间复杂度 1.3.2 时间复杂度 1.3.3 渐近符号 (O、 Ω、 Θ) 1.3.4 实际复杂度 1.3.5 性能度量 1.4 随机算法 1.4.1 概率论基础 1.4.2 随机算法: 非形式化的描述 1.4.3 识别重复元素 1.4.4 素数测试 1.4.5 优点与缺点 1.5 参考文献和读物 第2章 基本数据结构 2.1 栈和队列 2.2 树 2.2.1 术语 2.2.2 二叉树 2.3 字典 2.3.1 二叉查找树 2.3.2 代价分摊 2.4 优先队列 2.4.1 堆 2.4.2 堆排序 2.5 集合和不相交集合的并 2.5.1 概述 2.5.2 并和查找操作 2.6 图 2.6.1 概述 2.6.2 定义 2.6.3 图的表示方法 2.7 参考文献和读物 第3章 分治算法 3.1 一般方法 3.2 二叉查找 3.3 查找最大值和最小值 3.4 归并排序 3.5 快速排序 3.5.1 性能度量 3.5.2 随机排序算法 3.6 选择 3.6.1 最坏情况下的最优算法 3.6.2 Select2的实现 3.7 Strassen矩阵乘法 3.8 凸包 3.8.1 几种原始几何方法 3.8.2 QuickHull算法 3.8.3 Graham扫描算法 3.8.4 一个O(nlogn)的分治算法 3.9 参考文献和读物 3.10 附加习题 第4章 贪心算法 4.1 一般方法 4.2 背包问题 4.3 树节点分割 4.4 带有期限的作业顺序问题 4.5 最小代价生成树 4.5.1 Prim算法 4.5.2 Kruskal算法 4.5.3 一个最优随机算法(*) 4.6 磁带的最优存储 4.7 最优归并模式 4.8 单源最短路径 4.9 参考文献和读物 4.10 附加习题 第5章 动态规划 5.1 一般方法 5.2 多部图 5.3 每一对顶点之间的最短路径 5.4 单源最短路径: 普通权值 5.5 最优二叉查找树(*) 5.6 串编辑 5.7 0/1背包 5.8 可靠性设计 5.9 旅行商问题 5.10 流水作业调度 5.11 参考文献和读物 5.12 附加习题 第6章 基本的查找和遍历技术 6.1 二叉树算法 6.2 图算法 6.2.1 广度优先搜索和遍历 6.2.2 深度优先搜索和遍历 6.3 连通分支和生成树 6.4 双连通分支和DFS算法 6.5 参考文献和读物 第7章 回溯 7.1 一般方法 7.2 8皇后问题 7.3 子集求和问题 7.4 图的着色 7.5 哈密顿回路 7.6 背包问题 7.7 参考文献和读物 7.8 附加习题 第8章 分支限界法 8.1 一般方法 8.1.1 最小代价查找 8.1.2 15拼板: 一个例子 8.1.3 LC查找的控制抽象 8.1.4 限界 8.1.5 FIFO分支限界法 8.1.6 LC分支限界法 8.2 0/1背包问题 8.2.1 LC分支限界法求解 8.2.2 FIFO分支限界法求解 8.3 旅行商问题(*) 8.4 效率因素 8.5 参考文献和读物 第9章 代数问题 9.1 一般方法 9.2 计算和插值 9.3 快速傅里叶变换 9.3.1 FFT的原地版本 9.3.2 一些保留问题 9.4 模运算 9.5 更快的计算和插值 9.6 参考文献和读物 第10章 下界理论 10.1 比较树 10.1.1 有序查找 10.1.2 排序 10.1.3 选择 10.2 喻示和对立论 10.2.1 归并 10.2.2 最大和次大 10.2.3 状态空间方法 10.2.4 选择 10.3 通过规约求下界 10.3.1 寻找凸包 10.3.2 不相交集合问题 10.3.3 即时中值查找 10.3.4 三角矩阵相乘 10.3.5 下三角矩阵求逆 10.3.6 计算传递闭包 10.4 解决代数问题的技术(*) 10.5 参考文献和读物 第11章 难与完全问题 11.1 基本概念 11.1.1 非确定性算法 11.1.2 难和完全类 11.2 Cook定理(*) 11.3 难的图问题 11.3.1 团判定问题 11.3.2 节点覆盖判定问题 11.3.3 色数判定问题 11.3.4 有向哈密顿回路(*) 11.3.5 旅行商判定问题 11.3.6 与/或图判定问题 11.4 难的调度问题 11.4.1 调度相同的处理器 11.4.2 流水作业调度 11.4.3 作业安排调度 11.5 难的代码生成问题 11.5.1 带有公共子表达式的代码生成 11.5.2 实现并行赋值指令 11.6 一些简化的难问题 11.7 参考文献和读物 11.8 附加习题 第12章 近似算法 12.1 概述 12.2 绝对近似 12.2.1 平面图着色 12.2.2 最多程序存储问题 12.2.3 难的绝对近似 12.3 ε近似 12.3.1 独立任务的调度 12.3.2 装箱问题 12.3.3 难的ε近似问题 12.4 多项式时间近似方案 12.4.1 独立任务的调度 12.4.2 0/1背包 12.5 完全多项式时间近似方案 12.5.1 舍入法 12.5.2 区间划分法 12.5.3 分割法 12.6 概率上的好算法(*) 12.7 参考文献和读物 12.8 附加习题 第13章 PRAM算法 13.1 概述 13.2 计算模型 13.3 基本技术和算法 13.3.1 前缀计算 13.3.2 表排序 13.4 选择 13.4.1 使用n?2个处理器选择最大值 13.4.2 使用n个处理器选择最大值 13.4.3 在整数中选择最大值 13.4.4 使用n?2个处理器的一般选择问题 13.4.5 一个工作最优的随机算法(*) 13.5 归并 13.5.1 对数时间算法 13.5.2 奇偶归并 13.5.3 工作最优的算法 13.5.4 O(log logm)时间算法 13.6 排序 13.6.1 奇偶归并排序 13.6.2 随机选择算法 13.6.3 Preparata算法 13.6.4 Reischuk随机算法(*) 13.7 图问题 13.7.1 计算传递闭包的另一种算法 13.7.2 每一对顶点之间的最短路径 13.8 计算凸包 13.9 下界 13.9.1 平均情况下排序的下界 13.9.2 寻找最大值 13.10 参考文献和读物 13.11 附加习题 第14章 网格算法 14.1 计算模型 14.2 分组路由 14.2.1 线性阵列中的分组路由 14.2.2 网格上PPR的贪心算法 14.2.3 具有小队列的随机算法 14.3 基本算法 14.3.1 广播 14.3.2 前缀计算 14.3.3 数据集中 14.3.4 稀疏枚举排序 14.4 选择 14.4.1 n=p(*)时的随机算法 14.4.2 n>p(*)时的随机选择 14.4.3 n>p时的确定性算法 14.5 归并 14.5.1 在线性阵列上的顺序号归并 14.5.2 线性阵列上的奇偶归并 14.5.3 在网格上的奇偶归并 14.6 排序 14.6.1 在线性阵列上的排序 14.6.2 在网格上的排序 14.7 图问题 14.7.1 传递闭包的n×n网格算法 14.7.2 每一对顶点之间的最短路径 14.8 计算凸包 14.9 参考文献和读物 14.10 附加习题 第15章 超立方体算法 15.1 计算模型 15.1.1 超立方体 15.1.2 蝶形网络 15.1.3 其他网络的嵌入 15.2 PPR路由 15.2.1 贪心算法 15.2.2 随机算法 15.3 基本算法 15.3.1 广播 15.3.2 前缀计算 15.3.3 数据集中 15.3.4 稀疏枚举排序 15.4 选择 15.4.1 n=p(*)时的随机算法 15.4.2 n>p(*)时的随机选择 15.4.3 n>p时的确定性算法 15.5 归并 15.5.1 奇偶归并 15.5.2 双调谐归并 15.6 排序 15.6.1 奇偶归并排序 15.6.2 双调谐排序 15.7 图问题 15.8 计算凸包 15.9 参考文献和读物 15.10 附加习题 索引 编辑推荐与评论本书作者均是世界著名的计算机科学家,在计算机科学理论和算法领域做出了杰出的贡献。本书着重在计算机科学发展领域中,推动新的计算机算法的设计和分析,是一本经典著作,也是计算机算法方面的重要参考书。书中为读者提供了计算机算法的设计技术,对计算机算法的实际设计提供了有效的算法分析。在计算机算法设计方面提供了大量的详细实例和实际应用,并致力于随机算法和并行算法富有成效的深入研究和开发。本书为读者提供了当前流行的对象设计语言C++的实现版本,以及现代计算机科学发展和研究的最新研究成果。 作者介绍Ellis Horowitz于威斯康星-迈迪逊大学获得计算机科学博士学位,从事数据结构、算法和软件设计等领域的计算机科学教育。他是美国国家科学基金会主要调查员。 |
| 随便看 |
百科全书收录4421916条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。