计算机算法基础 第2版
全新正版 极速发货
￥ 41.51 5.3折 ￥ 79 全新
库存4件
广东广州
认证卖家担保交易快速发货售后保障
作者沈孝钧
出版社机械工业
ISBN9787111746591
出版时间2024-04
装帧平装
开本其他
定价79元
货号1203256988
上书时间2024-06-18
商品详情
- 品相描述：全新
- 商品描述
-
作者简介
沈孝钧 美国密苏里大学荣休教授。他本科毕业于清华大学，后留学美国，就读于伊利诺大学香槟分校，师从著名计算机科学家C.L.Liu教授。获得博士后，受聘于密苏里大学堪萨斯分校计算机系直至退休。在30余年的教学和研究工作中，他主要讲授计算机算法和离散数学。他研究的领域包括离散数学、几何算法、并行处理、计算机网络中的调度算法等。除会议文章外，他有数十篇论文发表在国际著名期刊上，包括SIAMJournalonComputing、DiscreteMathematics、DiscreteAppliedMathematics、IEEEJournalonSelectedAreasinCommunications、IEEETransactionsonNetworking等。<br/><br/>
目录
目 录<br />前言<br />教学建议<br />第1章 概述 1<br />1.1 算法与数据结构及程序的关系 1<br />1.1.1 什么是算法 1<br />1.1.2 算法与数据结构的关系 1<br />1.1.3 算法与程序的关系 2<br />1.1.4 选择排序的例子 2<br />1.1.5 算法的伪码表示 2<br />1.2 算法复杂度分析 3<br />1.2.1 算法复杂度的度量 3<br />1.2.2 算法复杂度与输入数据规模的关系 4<br />1.2.3 输入数据规模的度量模型 4<br />1.2.4 算法复杂度分析中的两个简化假设 5<br />1.2.5 最好情况、最坏情况和平均情况<br />的复杂度分析 5<br />1.3 函数增长渐近性态的比较 6<br />1.3.1 三种比较关系及O、、记号 6<br />1.3.2 表示算法复杂度的常用函数 7<br />1.4 问题复杂度与算法复杂度的关系 9<br />1.4.1 问题复杂度是算法复杂度的<br />下界 9<br />1.4.2 问题复杂度与最佳算法 9<br />1.4.3 易处理问题和难处理问题 9<br />习题 10<br />第2章 分治法 11<br />2.1 分治法原理 11<br />2.1.1 二元搜索的例子 11<br />2.1.2 表示复杂度的递推关系 12<br />2.2 递推关系求解 13<br />2.2.1 替换法 13<br />2.2.2 序列求和法与递归树法 15<br />2.2.3 常用序列和公式 16<br />2.2.4 主方法求解 18<br />2.3 例题示范 19<br />习题 20<br />第3章 基于比较的排序算法 24<br />3.1 插入排序 24<br />3.1.1 插入排序的算法 24<br />3.1.2 插入排序算法的复杂度分析 25<br />3.1.3 插入排序的优缺点 26<br />3.2 合并排序 26<br />3.2.1 合并算法及其复杂度 26<br />3.2.2 合并排序的算法及其复杂度 27<br />3.2.3 合并排序的优缺点 29<br />3.3 堆排序 30<br />3.3.1 堆的数据结构 30<br />3.3.2 堆的修复算法及其复杂度 31<br />3.3.3 为输入数据建堆 32<br />3.3.4 堆排序算法 33<br />3.3.5 堆排序算法的复杂度 34<br />3.3.6 堆排序算法的优缺点 35<br />3.3.7 堆用作优先队列 35<br />3.4 快排序 36<br />3.4.1 快排序算法 36<br />3.4.2 快排序算法最坏情况复杂度 39<br />3.4.3 快排序算法平均情况复杂度 40<br />3.4.4 快排序算法最好情况复杂度 41<br />3.4.5 快排序算法的优缺点 42<br />习题 42<br />第4章 不基于比较的排序算法 46<br />4.1 比较排序的下界 46<br />4.1.1 决策树模型及排序最坏情况下界 46<br />4.1.2 二叉树的外路径总长与排序平均<br />情况下界 49<br />4.1.3 二叉树的全路径总长与堆排序<br />最好情况下界 51<br />4.2 不基于比较的线性时间排序算法 54<br />4.2.1 计数排序 54<br />4.2.2 基数排序 57<br />4.2.3 桶排序 58<br />习题 60<br />第5章 中位数和任一顺序数的选择 63<br />5.1 问题定义 63<br />5.2 最大数和最小数的选择 63<br />5.2.1 最大和最小顺序数的选择算法及<br />其复杂度 64<br />5.2.2 同时找出最大数和最小数的<br />算法 65<br />5.3 线性时间找出任一顺序数的算法 66<br />5.3.1 最坏情况复杂度为O(n)的算法 66 <br />5.3.2 平均情况复杂度为O(n)的算法 68<br />5.4 找出k个最大顺序数的算法 69<br />5.4.1 一个理论联系实际的问题 69 <br />5.4.2 利用堆来找k个最大顺序数的<br />算法 70<br />5.4.3 利用锦标赛树来找k个最大顺序数<br />的算法 70<br />习题 71<br />第6章 动态规划 73<br />6.1 动态规划的基本原理 73<br />6.2 矩阵连乘问题 75<br />6.2.1 定义子问题 75<br />6.2.2 归纳公式 77<br />6.2.3 算法伪码和例子 78<br />6.3 最长公共子序列问题 81<br />6.3.1 定义子问题 81<br />6.3.2 归纳公式 82<br />6.3.3 算法伪码和例子 82<br />6.4 最佳二元搜索树问题 84<br />6.4.1 定义子问题和归纳公式 85<br />6.4.2 算法伪码和例子 87<br />6.5 多级图及其应用 89<br />6.6 最长递增子序列问题 92<br />6.6.1 定义子问题 93<br />6.6.2 归纳公式 93<br />6.6.3 算法伪码和例子 93<br />习题 95<br />第7章 贪心算法 103<br />7.1 最佳邮局设置问题 103<br />7.2 一个简单的最佳活动安排问题 105<br />7.3 其他最佳活动安排问题 106<br />7.3.1 两个大礼堂的最佳活动安排<br />问题 106<br />7.3.2 等长时间的活动的最佳安排<br />问题 109<br />7.4 哈夫曼编码问题 112<br />7.4.1 前缀码 112<br />7.4.2 最佳前缀码——哈夫曼编码 114<br />7.5 最佳加油计划问题 118<br />7.5.1 最佳加油计划问题的描述 118<br />7.5.2 贪心算法的基本思路 119<br />7.5.3 贪心算法的伪码 120<br />习题 121<br />第8章 图的周游算法 128<br />8.1 图的表示 128<br />8.1.1 邻接表 129<br />8.1.2 邻接矩阵 129<br />8.2 广度优先搜索及应用 130<br />8.2.1 广度优先搜索策略 130<br />8.2.2 广度优先搜索算法及距离树 131<br />8.2.3 无向图的二着色问题 133<br />8.3 深度优先搜索及应用 136<br />8.3.1 深度优先搜索的策略 136<br />8.3.2 深度优先搜索算法和深度优先<br />搜索树 137<br />8.3.3 深度优先搜索算法举例和图中<br />边的分类 140<br />8.3.4 拓扑排序 141<br />8.3.5 无回路有向图中最长路径问题<br />及应用 144<br />8.3.6 有向图的强连通分支的分解 146<br />8.3.7 无向图的双连通分支的分解 150<br />习题 156<br />第9章 图的最小支撑树 162<br />9.1 计算最小支撑树的一个通用的<br />贪心算法策略 163<br />9.2 Kruskal 算法 165<br />9.3 Prim 算法 168<br />习题 173<br />第10章 单源最短路径 178<br />10.1 Dijkstra 算法 179<br />10.2 Bellman-Ford 算法 184<br />习题 189<br />第11章 网络流 192<br />11.1 网络模型和最大网络流问题 192<br />11.2 网络中的流与割的关系 196<br />11.2.1 网络中的割及其容量 197<br />11.2.2 剩余网络和增广路径 198<br />11.2.3 最大流最小割定理 201<br />11.3 Ford-Fulkerson 算法 202<br />11.3.1 Ford-Fulkerson 的通用算法 202<br />11.3.2 Edmonds-Karp 算法 204<br />11.3.3 Dinic 算法 207<br />11.4 二部图的匹配问题 210<br />11.4.1 0-1网络的最大流问题 211<br />11.4.2 用网络流求二部图的最大匹配<br />的算法 212<br />11.4.3 Philip Hall 婚配定理 214<br />11.4.4 Birkhoff-von Neumann 定理 215<br />11.5 推进-重标号算法简介 217<br />11.5.1 预流和高度函数 217<br />11.5.2 在剩余网络中对顶点的两个<br />操作 219<br />11.5.3 推进-重标号算法的初始化 220<br />11.5.4 推进-重标号的通用算法 220<br />11.5.5 推进-重标号的通用算法的复杂<br />度分析 223<br />习题 224<br />第12章 计算几何基础 228<br />12.1 平面线段及相互关系 228<br />12.1.1 向量的点积和叉积 229<br />12.1.2 平面线段的相互关系 230<br />12.2 平扫线技术和线段相交的确定 233<br />12.2.1 平扫线的状态和事件点 234<br />12.2.2 用平扫线确定线段相交的<br />算法 235<br />12.3 平面点集的凸包 237<br />12.3.1 Graham 扫描法 238<br />12.3.2 Jarvis行进法 243<br />12.4 最近点对问题 245<br />12.4.1 预备工作和分治法的底 245<br />12.4.2 分治法的分 246<br />12.4.3 分治法的合 247<br />12.4.4 分治法的伪码 248<br />习题 249<br />第13章 字符串匹配 252<br />13.1 一个朴素的字符串匹配算法 252<br />13.2 Rabin-Karp 算法 253<br />13.3 基于有限状态自动机的匹配<br />算法 255<br />13.3.1 有限状态自动机简介 255<br />13.3.2 字符串匹配用的自动机 256<br />13.3.3 基于有限状态自动机的匹配<br />算法 259<br />13.4 Knuth-Morris-Pratt (KMP) 算法 260<br />13.4.1 模式的前缀函数 260<br />13.4.2 基于前缀函数的KMP 算法 263<br />习题 265<br />第14章 NP 完全问题 266<br />14.1 预备知识 267<br />14.1.1 图灵机 267<br />14.1.2 符号集和编码对计算复杂度的<br />影响 268<br />14.1.3 判断型问题和优化型问题及其<br />关系 268<br />14.1.4 判断型问题的形式语言表示 270<br />14.1.5 多项式关联和多项式归约 271<br />14.2 P和NP语言类 272<br />14.2.1 非确定图灵机和NP语言类 273<br />14.2.2 多项式检验算法和NP类语言的<br />关系 274<br />14.3 NPC语言类和NPC问题 276<br />14.3.1 第一个NPC问题 277<br />14.3.2 若干著名NPC问题的证明 281<br />习题 295<br />第15章 近似算法 301<br />15.1 近似算法的性能评价 301<br />15.2 顶点覆盖问题 302<br />15.3 货郎担问题 303<br />15.3.1 满足三角不等式的货郎担<br />问题 304<br />15.3.2 无三角不等式关系的一般<br />货郎担问题 307<br />15.4 集合覆盖问题 307<br />15.5 MAX-3-SAT问题 310<br />15.6 加权的顶点覆盖问题 311<br />15.7 子集和问题 313<br />15.7.1 一个保证最优解的指数型算法 313<br />15.7.2 子集和问题的一个完全多项式<br />近似机制 314<br />*15.8 鸿沟定理和不可近似性 317<br />15.8.1 鸿沟定理 318<br />15.8.2 任务均匀分配问题 319<br />习题 321<br />第16章 穷举搜索 324<br />16.1 问题及方法的描述 324<br />16.2 回溯法 326<br />16.2.1 回溯法的通用算法 326<br />16.2.2 n皇后问题 327<br />16.2.3 子集和问题 328<br />16.2.4 回溯法的效率估计 330<br />16.3 分支限界法 331<br />16.3.1 分支限界法解n皇后问题 332<br />16.3.2 0/1背包问题 334<br />16.4 博弈树和α-β剪枝 340<br />16.4.1 博弈树及其评估的方法 340<br />16.4.2 α-β剪枝法 344<br />习题 346<br />第17章 平摊分析和斐波那契堆 348<br />17.1 平摊分析的常用方法 349<br />17.1.1 聚集法 349<br />17.1.2 记账法 350<br />17.1.3 势能法 352<br />17.2 动态表格 353<br />17.2.1 只允许扩张的动态表格 353<br />17.2.2 扩张和收缩都有的动态表格 355<br />17.3 斐波那契堆 358<br />17.3.1 斐波那契堆的构造 358<br />17.3.2 可合并堆的操作 360<br />17.3.3 减小一个关键字和删除任一结点<br />的操作 365<br />17.3.4 最大度数的界 367<br />习题 369<br />附录A 红黑树 372<br />附录B 用于分离集合操作的数据<br />结构 385<br />参考文献 397<br />
内容摘要
本书作者根据自己20多年的教学与科研实践，系统地总结了计算机算法的设计与分析方法，覆盖了大部分主要的算法技术，包括：分治法、贪心法、动态规划、图的遍历技术、穷举搜索等，涉及一系列重要的算法问题，包括排序问题、选择问题、生成树问题、网络流问题、二分图的匹配问题、字符串的匹配问题和几何算法问题等，还介绍了问题本身的计算复杂性的概念和NP完全问题的理论等。
主编推荐
本书作者根据自己几十年的教学与科研实践，系统地总结了计算机算法的设计与分析方法，覆盖了大部分最主要的算法技术，包括分治法、贪心算法、动态规划、图的遍历技术、穷举搜索等，涉及一系列重要的算法问题，包括排序问题、选择问题、最小生成树问题、最短路径问题、网络流问题、二分图的匹配问题、字符串的匹配问题和几何算法问题等。作者力求通过有趣和难易适中的案例说明算法的特点和应用场景，使读者能够理解如何针对具体问题选择高效的算法。本书适合作为高校计算机及相关专业算法课程的教材，也适合作为软件研发人员了解算法的技术参考书。
相关推荐
— 没有更多了 —
以下为对购买帮助不大的评价