商品描述: 基本信息
书名:算法设计(英文版)
定价：138元
作者:[美]乔恩·克莱因伯格（JonKleinberg）
出版社：人民邮电出版社
出版日期：2019-05-01
ISBN：9787115495921
字数：
页码：814
版次：
装帧：平装
开本：16开
商品重量：
编辑推荐
- 众多名校采用的算法设计课程教材- 用实际示例阐明枯燥的算法理论- 更注重算法设计思路而非算法复杂度分析本书采用新颖的方法来讲算法课程，通过激发算法思想的真实世界问题，引入了算法思想。两位作者以一种清晰、直接的方式，指导学生自己分析和定义问题，并从中找出哪些设计原则适用于给定的场景。本书鼓励更深入地理解算法设计过程，以及算法在计算机科学的更广阔的领域中的应用。本书有以下几个特色：1.强调分析和设计方法；2.遵循结构化教学方法，引导学生学习问题形式化、算法设计和算法分析的全过程；3.通过一系列带解答的问题，展示计算机科学家设计和应用算法的过程；4.包含200多道作业题，其中一些题目来自Yahoo！和Oracle这样的公司；5.提供广泛用于处理NP困难问题和随机应用的算法，这些是非常重要的算法主题。
内容提要
这是一本关于算法设计和分析的教材。本书围绕算法设计进行组织，对每种算法技术选择了多个典型范例进行分析，把算法的理论跟实际存在的问题结合起来，具有很大的启发性。本书侧重算法设计思路，不再赘述算法复杂度的分析，每章都从实际问题出发，经过深入的具体分析引出相应的算法的设计思想，并对算法的正确性和复杂性进行合理的分析和论证。本书覆盖面很宽，且含有200多道精彩的习题，还扩展了PSPACE问题、参数复杂性等内容。
目录
目录1　Introduction： Some Representative Problems / 引言：某些有代表性的问题　11．1　A First Problem： Stable Matching / 个问题：稳定匹配　11．2　Five Representative Problems / 五个有代表性的问题　12Solved　Exercises / 带解答的练习　19Exercises　/ 练习　22Notes　and Further Reading / 注释和进一步阅读　282　Basics of Algorithm Analysis / 算法分析基础　292．1　Computational Tractability / 计算可解性　292．2　Asymptotic Order of Growth / 增长的渐近阶　352．3　Implementing the Stable Matching Algorithm Using Lists and Arrays / 用列表和数组实现稳定匹配算法422．4　A Survey of Common Running Times / 常用运行时间概述　472．5　A More Complex Data Structure： Priority Queues / 更复杂的数据结构：优先队列　57Solved　Exercises / 带解答的练习　65Exercises　/ 练习　67Notes　and Further Reading / 注释和进一步阅读　703　Graphs / 图　733．1　Basic Definitions and Applications / 基本定义与应用　733．2　Graph Connectivity and Graph Traversal / 图的连通性与图的遍历　783．3　Implementing Graph Traversal Using Queues and Stacks / 用优先队列与栈实现图的遍历　873．4　Testing Bipartiteness： An Application of Breadth-First Search / 二分性测试：宽度优先搜索的应用　943．5　Connectivity in Directed Graphs / 有向图中的连通性　973．6　Directed Acyclic Graphs and Topological Ordering / 有向无环图与拓扑排序　99Solved　Exercises / 带解答的练习　104Exercises　/ 练习　107Notes　and Further Reading / 注释和进一步阅读　1124　Greedy Algorithms / 贪心算法　1154．1　Interval Scheduling： The Greedy Algorithm Stays Ahead / 区间调度：贪心算法领先　1164．2　Scheduling to Minimize Lateness： An Exchange Argument / 延迟调度：交换论证　1254．3　Optimal Caching： A More Complex Exchange Argument / 高速缓存：更复杂的交换论证1314．4　Shortest Paths in a Graph / 图的短路径　1374．5　The Minimum Spanning Tree Problem / 生成树问题　1424．6　Implementing Kruskal’s Algorithm： The Union-Find Data Structure / 实现Kruskal算法：Union-Find数据结构　1514．7　Clustering / 聚类　1574．8　Huffman Codes and Data Compression / 赫夫曼码与数据压缩　1614．9 Minimum-Cost Arborescences： A Multi-Phase Greedy Algorithm / 费用有向树：多阶段贪心算法　177Solved　Exercises / 带解答的练习　183Exercises　/ 练习　188Notes　and Further Reading / 注释和进一步阅读　2055　Divide and Conquer / 分治策略　2095．1　A First Recurrence： The Mergesort Algorithm / 个递推式：归并排序算法　2105．2　Further Recurrence Relations / 更多的递推关系　2145．3　Counting Inversions / 计数逆序　2215．4　Finding the Closest Pair of Points / 找接邻近的点对　2255．5　Integer Multiplication / 整数乘法　2315．6　Convolutions and the Fast Fourier Transform / 卷积与快速傅里叶变换　234Solved　Exercises / 带解答的练习　242Exercises　/ 练习　246Notes　and Further Reading / 注释和进一步阅读　2496　Dynamic Programming / 动态规划　2516．1　Weighted Interval Scheduling： A Recursive Procedure / 带权的区间调度：递归过程　2526．2　Principles of Dynamic Programming： Memoization or Iteration over Subproblems / 动态规划原理：备忘录或者子问题迭代　2586．3　Segmented Least Squares： Multi-way Choices / 分段的二乘：多重选择　2616．4　Subset Sums and Knapsacks： Adding a Variable / 子集和与背包：加一个变量　2666．5　RNA Secondary Structure： Dynamic Programming over Intervals / RNA二级结构：在区间上的动态规划　2726．6　Sequence Alignment / 序列比对　2786．7　Sequence Alignment in Linear Space via Divide and Conquer / 通过分治策略在线性空间的序列比对　2846．8　Shortest Paths in a Graph / 图中的短路径　2906．9　Shortest Paths and Distance Vector Protocols / 短路径和距离向量协议　2976．10 Cycles in a Graph / 图中的负圈　301Solved　Exercises / 带解答的练习　307Exercises　/ 练习　312Notes　and Further Reading / 注释和进一步阅读　3357　Network Flow / 网络流　3377．1　The Mamum-Flow Problem and the Ford-Fulkerson Algorithm / 流问题与Ford-Fulkerson算法　3387．2　Mamum Flows and Minimum Cuts in a Network / 网络中的流与割　3467．3　Choosing Good Augmenting Paths / 选择好的增广路径3527．4 The Preflow-Push Mamum-Flow Algorithm / 前向流推动流算法　3577．5　A First Application： The Bipartite Matching Problem / 个应用：二分匹配问题　3677．6　Disjoint Paths in Directed and Undirected Graphs / 有向与无向图中的不交路径　3737．7　Extensions to the Mamum-Flow Problem / 对流问题的推广　3787．8　Survey Design / 调查设计3847．9　Airline Scheduling / 航线调度　3877．10　Image Segmentation / 图像分割　3917．11　Project Selection / 项目选择　3967．12　Baseball Elimination / 棒球排除　4007．13 A Further Direction： Adding Costs to the Matching Problem / 进一步的方向：对匹配问题增加费用　404Solved　Exercises / 带解答的练习　411Exercises　/ 练习　415Notes　and Further Reading / 注释和进一步阅读　4488　NP and Computational Intractability / NP与计算的难解性　4518．1　Polynomial-Time Reductions / 多项式时间归约　4528．2　Reductions via “Gadgets”： The Satisfiability Problem / 使用“零件”的归约：可满足性问题　4598．3　Efficient Certification and the Definition of NP / 有效证书和NP的定义　4638．4　NP-Complete Problems / NP完全问题　4668．5　Sequencing Problems / 排序问题　4738．6　Partitioning Problems / 划分问题　4818．7　Graph Coloring / 图着色　4858．8　Numerical Problems / 数值问题　4908．9　Co-NP and the Asymmetry of NP / Co-NP及NP的不对称性　4958．10　A Partial Taxonomy of Hard Problems / 难问题的部分分类　497Solved　Exercises / 带解答的练习　500Exercises　/ 练习　505Notes　and Further Reading / 注释和进一步阅读　5299　PSPACE： A Class of Problems beyond NP / PSPACE：一类超出NP的问题　5319．1　PSPACE / PSPACE　5319．2　Some Hard Problems in PSPACE / PSPACE中的难问题　5339．3　Solving Quantified Problems and Games in Polynomial Space / 在多项式空间中解量化问题和博弈问题　5369．4　Solving the Planning Problem in Polynomial Space / 在多项式空间内求解规划问题　5389．5　Proving Problems PSPACE-Complete / 证明问题是PSPACE完全的　543Solved　Exercises / 带解答的练习　547Exercises　/ 练习　550Notes　and Further Reading / 注释和进一步阅读　55110　Extending the Limits of Tractability / 扩展易解性的界限　55310．1　Finding Small Vertex Covers / 找小的顶点覆盖　55410．2　Solving NP-Hard Problems on Trees / 在树上解NP难问题　55810．3　Coloring a Set of Circular Arcs / 圆弧集着色　56310．4 Tree Decompositions of Graphs / 图的树分解　57210．5 Constructing a Tree Decomposition / 构造树分解　584Solved　Exercises / 带解答的练习　591Exercises　/ 练习　594Notes　and Further Reading / 注释和进一步阅读　59811　Appromation Algorithms / 近似算法　59911．1　Greedy Algorithms and Bounds on the Optimum： A Load Balancing Problem / 贪心算法与值的界限：负载均衡问题　60011．2　The Center Selection Problem / 中心选址问题　60611．3　Set Cover： A General Greedy Heuristic / 集合覆盖：一般的贪心启发式方法　61211．4　The Pricing Method： Vertex Cover / 定价法：顶点覆盖　61811．5　Mamization via the Pricing Method： The Disjoint Paths Problem / 用定价法化：不交路径问题　62411．6　Linear Programming and Rounding： An Application to Vertex Cover / 线性规划与舍入：对顶点覆盖的应用　63011．7 Load Balancing Revisited： A More Advanced LP Application / 再论负载均衡：更高级的LP应用　63711．8　Arbitrarily Good Appromations： The Knapsack Problem / 任意好的近似：背包问题　644Solved　Exercises / 带解答的练习　649Exercises　/ 练习　651Notes　and Further Reading / 注释和进一步阅读　65912　Local Search / 局部搜索　66112．1　The Landscape of an Optimization Problem / 化问题的地形图　66212．2　The Metropolis Algorithm and Simulated Annealing / Metropolis算法与模拟退火算法　66612．3　An Application of Local Search to Hopfield Neural Networks / 局部搜索在Hopfield神经网络中的应用　67112．4　Mamum-Cut Appromation via Local Search / 局部搜索对割近似的应用　67612．5　Choosing a Neior Relation / 选择邻居关系　67912．6 Classification via Local Search / 用局部搜索分类　68112．7　Best-Response Dynamics and Nash Equilibria / 响应动态过程与纳什均衡　690Solved　Exercises / 带解答的练习　700Exercises　/ 练习　702Notes　and Further Reading / 注释和进一步阅读　70513　Randomized Algorithms / 随机算法　70713．1　A First Application： Contention Resolution / 个应用：消除争用　70813．2　Finding the Global Minimum Cut / 求完全割　71413．3　Random Variables and Their Expectations / 随机变量及其期望　71913．4　A Randomized Appromation Algorithm for MAX 3-SAT / 关于MAX 3-SAT的随机近似算法　72413．5　Randomized Divide and Conquer： Median-Finding and Quicksort / 随机分治策略：求中位数与快速排序　72713．6　Hashing： A Randomized Implementation of Dictionaries / 散列法：字典的随机实现　73413．7　Finding the Closest Pair of Points： A Randomized Approach / 求邻近点对：随机方法　74113．8　Randomized Caching / 随机超高速缓存　75013．9　Chernoff Bounds / 切尔诺夫界　75813．10　Load Balancing / 负载均衡　76013．11　Packet Routing / 包路由选择　76213．12　Background： Some Basic Probability Definitions / 背景：某些基本概率定义　769Solved　Exercises / 带解答的练习　776Exercises　/ 练习　782Notes　and Further Reading / 注释和进一步阅读　793Epilogue：　Algorithms That Run Forever / 后记：永不停止运行的算法　795References　/ 参考文献　805
作者介绍
Jon Kleinberg是美国国家科学院（NAS）、美国国家工程院（NAE）、美国人文与科学院（AAAS）三料院士。在计算机科学领域是“传说级”的人物，而且还获得过国际数学家大会颁发“奈望林纳奖”，该奖是数学家大会为了表彰信息科学方面的重要数学贡献而设的。
序言

【封面】

— 没有更多了 —