定 价:119出 版 社:人民邮电出版社出版日期:2021年03月01日页 数:503装 帧:平装ISBN:9787115546647

1.众多名校采用的算法设计课程教材；2.用实际示例阐明枯燥的算法理论；3.更注重算法设计思路而非算法复杂度分析；4.本书覆盖面广，且含有200多道精彩的习题，很后还扩展了PSPACE问题、参数复杂性等内容。这是一本被众多名校采用的算法设计课程教材，强调用实际示例阐明枯燥的算法理论，更注重算法设计思路而非算法复杂度分析。本书采用新颖的教学方式，通过分析真实世界的问题来激发算法思想。两位作者以一种清晰、直接的方式，指导学生自己分析和定义问题，并从中找出适用于给定场景的算法设计原则。本书鼓励......

●目 录第 1章 引言：一些典型问题 11.1 第 一个问题：稳定匹配 11.2 5个典型问题 8带解答的练习 12练习 14注释和进一步阅读 17第 2章 算法分析基础 182.1 计算可解性 182.2 增长的渐近阶 212.3 用列表和数组实现稳定匹配算法 262.4 常见运行时间综述 292.5 更复杂的数据结构：优先队列 35带解答的练习 40练习 41注释和进一步阅读 44第3章 图 453.1 基本定义和应用 453.2 图连通性和图遍历 483.3 用队列和栈实现图遍历 533.4 二分性测试：广度优先搜索的应用 583.5 有向图中的连通性 593.6 有向无环图和拓扑排序 61带解答的练习 64练习 66注释和进一步阅读 69第4章 贪心算法 704.1 区间调度：贪心算法保持领先 704.2 最小化延迟的调度：交换论证 764.3 最优缓存：更复杂的交换论证 804.4 图的最短路径 834.5 最小生成树问题 874.6 实现Kruskal算法：Union-Find数据结构 924.7 聚类 974.8 哈夫曼码和数据压缩 99*4.9 最小开销树形图：多阶段贪心算法 109带解答的练习 113练习 116注释和进一步阅读 125第5章 分治 1275.1 第 一个递推式：归并排序算法 1275.2 进一步的递推关系 1305.3 计数逆序 1345.4 寻找最近点对 1375.5 整数乘法 1415.6 卷积和快速傅里叶变换 142带解答的练习 148练习 150注释和进一步阅读 152第6章 动态规划 1536.1 加权区间调度：递归过程 1536.2 动态规划原理：备忘录或子问题迭代 1576.3 分段最小二乘：多重选择 1596.4 子集和与背包：加一个变量 1626.5 RNA二级结构：区间上的动态规划 1666.6 序列比对 1696.7 通过分治在线性空间中序列比对 1736.8 图中的最短路径 1776.9 最短路径和距离向量协议 182*6.10 图中的负环 184带解答的练习 187练习 190注释和进一步阅读 204第7章 网络流 2057.1 优选流问题和Ford-Fulkerson算法 2057.2 网络中的优选流和最小割 2117.3 选择好的增广路径 214*7.4 预流推进优选流算法 2187.5 第 一个应用：二分匹配问题 2257.6 有向图和无向图中的不相交路径 2287.7 优选流问题的扩展 2327.8 调查设计 2367.9 航空公司调度 2377.10 图像分割 2407.11 项目选择 2437.12 棒球排除 246*7.13 进一步的方向：为匹配问题增加开销 249带解答的练习 253练习 255注释和进一步阅读 274第8章 NP和计算难解性 2768.1 多项式时间归约 2768.2 通过“小配件”归约：可满足性问题 2808.3 有效证书和NP的定义 2838.4 NP完全问题 2858.5 排序问题 2898.6 划分问题 2948.7 图着色 2978.8 数值问题 3008.9 co-NP和NP的不对称性 3038.10 困难问题的部分分类 305带解答的练习 307练习 309注释和进一步阅读 323第9章 PSPACE：NP之外的一类问题 3249.1 PSPACE 3249.2 PSPACE中的一些难题 3259.3 在多项式空间中求解量化问题和博弈 3279.4 在多项式空间中求解规划问题 3289.5 证明问题是PSPACE完全的 331带解答的练习 334练习 335注释和进一步阅读 336第 10章 扩展易解性的界限 33710.1 寻找小的顶点覆盖 33810.2 求解树上的NP困难问题 34010.3 圆弧集着色 343*10.4 图的树分解 349*10.5 构造树分解 356带解答的练习 361练习 363注释和进一步阅读 365第 11章 近似算法 36611.1 贪心算法和最优值的界限：负载均衡问题 36611.2 中心选址问题 37011.3 集合覆盖：一般贪心启发式 37411.4 定价方法：顶点覆盖 37811.5 用定价方法优选化：不相交路径问题 38211.6 线性规划和舍入：顶点覆盖的应用 386*11.7 再论负载均衡：更不错的LP应用 39011.8 任意好的近似：背包问题 394带解答的练习 398练习 399注释和进一步阅读 404第 12章 局部搜索 40612.1 优化问题的地形 40612.2 Metropolis算法和模拟退火算法 40912.3 局部搜索在Hopfield神经网络中的应用 41212.4 通过局部搜索的优选割近似 41512.5 选择邻居关系 417*12.6 用局部搜索分类 41812.7 最优响应动态和纳什均衡 423带解答的练习 430练习 431注释和进一步阅读 433第 13章 随J算法 43413.1 第 一个应用：消除争用 43513.2 寻找全局最小割 43813.3 随J变量及其期望 44213.4 MAX 3-SAT的随J近似算法 44513.5 随J分治：找中位数和Quicksort 44713.6 哈希：字典的随J实现 45213.7 寻找最近点对：随J方法 45713.8 随J缓存 46213.9 切尔诺夫界 46713.10 负载均衡 46813.11 分组路由 47013.12 背景知识：一些基本概率定义 474带解答的练习 479练习 483注释和进一步阅读 489后记：永远运行的算法 491参考文献 497

内容简介

这是一本关于算法设计和分析的经典教材。本书围绕算法设计进行组织，对每种算法技术用多个典型范例进行分析，把算法的理论跟实际问题结合起来，具有很大的启发性。本书侧重算法设计思路，每章都从实际问题出发，经过深入具体的分析引出相应算法的设计思想，并对算法的正确性和复杂性进行合理的分析和论证。本书覆盖面广，且含有200多道精彩的习题，很后还扩展了PSPACE问题、参数复杂性等内容。

[美] 乔恩·克莱因伯格（Jon Kleinberg） 著 王海鹏 译

作者简介乔恩·克莱因伯格（Jon Kleinberg），康奈尔大学计算机科学教授。他于1996年从麻省理工学院获得博士学位。他荣获过美国国家科学基金会事业奖、海军研究局青年研究员奖、IBM 杰出创新奖和美国国家科学院创新研究奖等众多奖项。他的研究集中在算法上，特别是与网络结构和信息相关的算法，以及这些算法在信息科学、优化、数据挖掘以及计算生物学等方面的应用。伊娃·塔多斯（éva Tardos），康奈尔大学计算机科学教授。她是美国艺术与科学学院院士、ACM会士。她荣获过美国国家科学基金会总统青年研究员奖和富尔克森奖等众多奖项。她的研究兴趣主要集中在图和网络问题的算法设计和分析上。她因在......