| 作者 |
| 桑迪普·森 阿米特·库玛尔 托马斯 H.科尔曼 |
| 丛书名 |
| 计算机科学丛书 |
| 出版社 |
| 机械工业出版社 |
| ISBN |
| 9782106021620 |
| 简要 |
| 简介 |
| 内容简介书籍计算机书籍 ---------------------------8081125 - 现代算法设计与分析--------------------------- 本书不仅讲解传统的算法设计策略和技巧，而且关注算法领域不断涌现的新概念、新方法和新应用，帮助读者把握技术热点及发展趋势。书中引入了降维技术、并行算法、随机算法、层次化存储结构算法和流算法等新内容，大量使用概率分析和随机化技术，并包含众多新颖的示例，特别是强调计算模型和计算环境，不再局限于理想化的随机存取机模型。全书内容简洁明快，并配有丰富的习题和拓展阅读资料，适合作为高等院校计算机相关专业的教材，也适合业界技术人员阅读参考。 ---------------------------4898587 - 算法基础：打开算法之门--------------------------- 本书介绍了什么是计算机算法，如何描述它们，以及如何来评估它们。这些计算机算法将提供：利用计算机搜索信息的简单方式；解决各种排序问题的方法；利用有向无环图和最短路径法来解决基本问题的方法(可用于建模公路网络，任务间的依赖及金融关系)；解决字符串(例如DNA结构)问题的方法；密码学背后的基本原理；数据压缩的基础知识；以及甚至一些没有人能够理解如何在计算机上用相当长的时间来解决的问题。 本书适合作为计算机专业本科生“算法设计与分析”课程的教材，也适合相关专业人员阅读。 |
| 目录 |
| [套装书具体书目] 4898587 - 算法基础：打开算法之门 - 9787111520764 - 机械工业出版社 - 定价 59 8081125 - 现代算法设计与分析 - 9787111679554 - 机械工业出版社 - 定价 99 ---------------------------8081125 - 现代算法设计与分析--------------------------- 出版者的话 译者序 前言 致谢 第1章 模型与分析1 1.1 计算斐波那契数1 1.2 快速乘法3 1.3 计算模型3 1.4 随机算法简介4 1.4.1 另一种随机算法6 1.5 其他计算模型8 1.5.1 外部存储器模型8 1.5.2 并行模型8 拓展阅读10 习题10 第2章 概率基础与尾部不等式13 2.1 概率基础13 2.2 尾部不等式17 2.3 生成随机数20 2.3.1 生成具有任意分布的随机变量21 2.3.2 由顺序文件生成随机变量21 2.3.3 生成随机置换23 拓展阅读25 习题25 第3章 热身问题27 3.1 计算最大公因子的欧几里得算法27 3.1.1 扩展欧几里得算法27 3.1.2 在密码学中的应用28 3.2 寻找第k小的元素28 3.2.1 选择随机的划分元29 3.2.2 中位数的中位数30 3.3 词的排序32 3.4 可归并的堆34 3.4.1 归并二项堆35 3.5 一个简单的半动态词典35 3.5.1 势能法与平摊分析36 3.6 下界37 拓展阅读39 习题39 第4章 优化Ⅰ：蛮力法与贪婪策略42 4.1 启发式搜索方法42 4.1.1 博弈树44 4.2 贪婪算法的框架46 4.2.1 最大支撑树49 4.2.2 寻找最小权值子集49 4.2.3 一个调度问题50 4.3 最小支撑树算法的高效数据结构51 4.3.1 并查集的一种简单数据结构52 4.3.2 更快的方案53 4.3.3 增长最慢的函数54 4.3.4 整合55 4.3.5 仅做道路压缩56 4.4 其他不同形式的贪婪策略57 4.5 与贪婪策略的折中58 4.6 梯度下降59 4.6.1 应用63 拓展阅读65 习题66 第5章 优化Ⅱ：动态规划69 5.1 背包问题70 5.2 上下文无关文法的解析71 5.3 最长单调子序列72 5.4 函数逼近74 5.5 最大似然估计的Viterbi算法75 5.6 树中的最大权独立集76 拓展阅读76 习题77 第6章 查找80 6.1 跳表——一个简单的字典80 6.1.1 跳表的构造80 6.1.2 分析81 6.1.3 更强的尾部估计82 6.2 树堆：随机查找树83 6.3 全域哈希86 6.3.1 全域哈希函数的存在性88 6.4 完美哈希函数88 6.4.1 将期望界转换为最差情况的界89 6.5 一个复杂度为log log N的优先级队列89 拓展阅读91 习题92 第7章 多维查找与几何算法94 7.1 区间树与范围树94 7.1.1 一维范围查找94 7.1.2 二维范围查找96 7.2 kd树97 7.3 优先级查找树99 7.4 平面凸包101 7.4.1 Jarvis March算法102 7.4.2 Graham扫描算法102 7.4.3 排序与凸包103 7.5 快速凸包算法104 7.5.1 分析105 7.5.2 期望运行时间106 7.6 使用持久化数据结构的点定位107 7.7 增量构造法109 拓展阅读111 习题111 第8章 字符串匹配与指纹函数114 8.1 RabinKarp指纹字符串查找算法114 8.2 KMP算法117 8.2.1 KMP算法的分析120 8.2.2 模式分析120 8.3 字典树及其应用121 拓展阅读123 习题123 第9章 快速傅里叶变换及其应用125 9.1 多项式求值与插值125 9.1.1 多项式相乘126 9.2 CooleyTukey算法126 9.3 蝶形网络128 9.4 SchonageStrassen快速乘法算法129 9.5 广义字符串匹配131 9.5.1 基于卷积的方法131 拓展阅读133 习题133 第10章 图算法135 10.1 深度优先搜索135 10.2 深度优先搜索的应用138 10.2.1 强连通分支138 10.2.2 双连通分支140 10.3 道路问题142 10.3.1 BellmanFord单源最短道路算法143 10.3.2 Dijkstra单源最短道路算法143 10.3.3 任意两点之间的最短道路算法145 10.4 计算赋权图中的支撑子145 10.5 全局最小割148 10.5.1 收缩算法149 10.5.2 最小割的概率149 拓展阅读150 习题151 第11章 最大流及其应用153 11.1 最大流的性质与算法155 11.1.1 最大流与最小割155 11.1.2 FordFulkerson算法156 11.1.3 EdmondKarp可增广道路策略157 11.1.4 单调性引理及迭代次数的界158 11.2 最大流的应用159 11.2.1 边不相交的道路159 11.2.2 二部图的匹配159 11.2.3 环流问题162 11.2.4 项目规划164 拓展阅读165 习题165 第12章 NP完全性与近似算法168 12.1 分类与可归约性170 12.2 CookLevin定理172 12.3 常见的NP完全问题173 12.4 NP完全性的证明175 12.4.1 顶点覆盖及相关问题175 12.4.2 图的3着色问题176 12.4.3 背包问题及相关问题177 12.5 其他重要的复杂度类179 12.6 使用近似算法处理困难性181 12.6.1 最大背包问题182 12.6.2 最小集合覆盖183 12.6.3 几何旅行商问题184 12.6.4 3着色问题185 12.6.5 最大割问题185 拓展阅读186 习题186 第13章 降维188 13.1 随机投影与JohnsonLindenstrauss引理188 13.2 高斯消元法191 13.3 奇异值分解及其应用192 13.3.1 矩阵代数与SVD定理192 13.3.2 使用SVD的低秩近似194 13.3.3 低秩近似的应用196 13.3.4 聚类问题197 13.3.5 SVD定理的证明199 拓展阅读200 习题200 第14章 并行算法201 14.1 并行计算模型201 14.2 排序和比较问题202 14.2.1 寻找最大值202 14.2.2 排序204 14.3 并行前缀208 14.4 基本的图算法212 14.4.1 列表排名212 14.4.2 连通分支214 14.5 基本的几何算法216 14.6 并行模型之间的关系217 14.6.1 网格上的路由218 拓展阅读220 习题220 第15章 层次化存储结构及高速缓存223 15.1 层次化存储模型223 15.2 矩阵转置224 15.2.1 矩阵乘法225 15.3 在外部存储器中进行排序226 15.3.1 我们可以改进这个算法吗227 15.4 高速缓存参数无关的算法设计228 15.4.1 参数无关的矩阵转置229 拓展阅读231 习题232 第16章 流数据模型233 16.1 引言233 16.2 查找流中的频繁元素233 16.3 流中的相异元素236 16.4 频数矩问题及其应用238 16.4.1 均值的中位数241 16.4.2 二阶频数矩的特例241 16.5 流模型下界的证明243 拓展阅读244 习题245 附录A 递推关系与生成函数247 参考文献253 ---------------------------4898587 - 算法基础：打开算法之门--------------------------- 出版者的话 译者序 前言 第1章什么是算法以及为什么应该关注算法1 1.1正确性2 1.2资源利用3 1.3针对非计算机专业人士的计算机算法5 1.4针对计算机专业人士的计算机算法6 1.5拓展阅读7 第2章如何描述和评估计算机算法9 2.1如何描述计算机算法9 2.2如何描述运行时间16 2.3循环不变式19 2.4递归21 2.5拓展阅读23 第3章排序算法和查找算法24 3.1二分查找26 3.2选择排序31 3.3插入排序34 3.4归并排序38 3.5快速排序47 3.6小结55 3.7拓展阅读57 第4章排序算法的下界和如何超越下界58 4.1基于排序的规则58 4.2基于比较排序的下界59 4.3使用计数排序超越下界60 4.4基数排序66 4.5拓展阅读68 第5章有向无环图69 5.1有向无环图72 5.2拓扑排序72 5.3如何表示有向图76 5.4拓扑排序的运行时间77 5.5PERT图表中的关键路径78 5.6有向无环图中的最短路径82 5.7拓展阅读86 第6章最短路径87 6.1Dijkstra算法89 6.2BellmanFord算法98 6.3FloydWarshall算法103 6.4拓展阅读112 第7章字符串算法114 7.1最长公共子序列114 7.2字符串转换120 7.3字符串匹配128 7.4拓展阅读135 第8章密码学基础136 8.1简单替代密码137 8.2对称密钥加密138 8.3公钥加密142 8.4RSA加密系统144 8.5混合加密系统153 8.6计算随机数153 8.7拓展阅读154 第9章数据压缩156 9.1哈夫曼编码158 9.2传真机165 9.3LZW压缩166 9.4拓展阅读176 第10章难？问题177 10.1棕卡车问题177 10.2P、NP和NP完全类181 10.3可判定问题和归约183 10.4主问题186 10.5NP完全问题例析188 10.6总体策略203 10.7前景206 10.8不可判定问题208 10.9小结210 10.10拓展阅读211 参考文献212 索引214 |