算法设计

1.众多名校采用的算法设计课程教材； 2.用实际示例阐明枯燥的算法理论； 3.更注重算法设计思路而非算法复杂度分析； 4.本书覆盖面广，且含有200多道精彩的习题，最后还扩展了PSPACE问题、参数复杂性等内容。 这是一本被众多名校采用的算法设计课程教材，强调用实际示例阐明枯燥的算法理论，更注重算法设计思路而非算法复杂度分析。本书采用新颖的教学方式，通过分析真实世界的问题来激发算法思想。两位作者以一种清晰、直接的方式，指导学生自己分析和定义问题，并从中找出适用于给定场景的算法设计原则。本书鼓励读者更深入地理解算法设计过程，探索算法在计算机科学的更广阔领域中的应用。 本书具有以下特色： ·强调问题分析和设计方法； ·遵循结构化教学法，引导学生掌握问题形式化、算法设计和算法分析的全过程； ·通过一系列带解答的问题，展示计算机科学家设计和应用算法的过程； ·包含 200 多道作业题，其中一些题目出自 Yahoo! 和 Oracle 等公司； ·提供广泛用于处理 NP 困难问题和随机应用的算法，这些是极其重要的算法主题。

这是一本关于算法设计和分析的经典教材。本书围绕算法设计进行组织，对每种算法技术用多个典型范例进行分析，把算法的理论跟实际问题结合起来，具有很大的启发性。本书侧重算法设计思路，每章都从实际问题出发，经过深入具体的分析引出相应算法的设计思想，并对算法的正确性和复杂性进行合理的分析和论证。本书覆盖面广，且含有200多道精彩的习题，最后还扩展了PSPACE问题、参数复杂性等内容。本书适合作为计算机及相近专业本科高年级学生以及研究生算法课程的参考教材，也适合作为对信息学奥林匹克竞赛感兴趣的高中生的指导书籍。对算法分析和设计感兴趣的IT专业技术人员也可以将本书作为案头推荐的参考书或工程实践手册。

乔恩·克莱因伯格（Jon Kleinberg）是康奈尔大学计算机科学教授。他于1996年从麻省理工学院获得博士学位。他荣获过美国国家科学基金会事业奖（NSF Career Award）、海军研究局青年研究员奖（ONR Young Investigator Award）、IBM杰出创新奖（IBM Outstanding Innovation Award）、美国国家科学院创新研究奖（National Academy of Sciences Award for Initiatives in Research），还获得过帕卡德基金会（Packard Foundation）和斯隆基金会（Sloan Foundation）的研究基金以及康奈尔工程学院与计算机科学系教学奖。 克莱因伯格的研究集中在算法上，特别是与网络结构和信息相关的算法，以及这些算法在信息科学、优化、数据挖掘及计算生物学等方面的应用。他利用信息中心和权威信息进行网络分析的工作，对形成近期新一代因特网搜索引擎的基础起了很大的作用。

第1章引言：一些典型问题
1.1第一个问题：稳定匹配
1.25个典型问题
带解答的练习
练习
注释和进一步阅读
第2章算法分析基础
2.1计算可解性
2.2增长的渐近阶
2.3用列表和数组实现稳定匹配算法
2.4常见运行时间综述
2.5更复杂的数据结构：优先队列
带解答的练习
练习
注释和进一步阅读
第3章图
3.1基本定义和应用
3.2图连通性和图遍历
3.3用队列和栈实现图遍历
3.4二分性测试：广度优先搜索的应用
3.5有向图中的连通性
3.6有向无环图和拓扑排序
带解答的练习
练习
注释和进一步阅读
第4章贪心算法
4.1区间调度：贪心算法保持领先
4.2最小化延迟的调度：交换论证
4.3很优缓存：更复杂的交换论证
4.4图的最短路径
4.5最小生成树问题
4.6实现Kruskal算法：Union-Find数据结构
4.7聚类
4.8哈夫曼码和数据压缩
*4.9最小开销树形图：多阶段贪心算法
带解答的练习
练习
注释和进一步阅读
第5章分治
5.1第一个递推式：归并排序算法
5.2进一步的递推关系
5.3计数逆序
5.4寻找最近点对
5.5整数乘法
5.6卷积和快速傅里叶变换
带解答的练习
练习
注释和进一步阅读
第6章动态规划
6.1加权区间调度：递归过程
6.2动态规划原理：备忘录或子问题迭代
6.3分段最小二乘：多重选择
6.4子集和与背包：加一个变量
6.5RNA二级结构：区间上的动态规划
6.6序列比对
6.7通过分治在线性空间中序列比对
6.8图中的最短路径
6.9最短路径和距离向量协议
*6.10图中的负环
带解答的练习
练习
注释和进一步阅读
第7章网络流
7.1优选流问题和Ford-Fulkerson算法
7.2网络中的优选流和最小割
7.3选择好的增广路径
*7.4预流推进优选流算法
7.5第一个应用：二分匹配问题
7.6有向图和无向图中的不相交路径
7.7优选流问题的扩展
7.8调查设计
7.9航空公司调度
7.10图像分割
7.11项目选择
7.12棒球排除
*7.13进一步的方向：为匹配问题增加开销
带解答的练习
练习
注释和进一步阅读
第8章NP和计算难解性
8.1多项式时间归约
8.2通过“小配件”归约：可满足性问题
8.3有效证书和NP的定义
8.4NP接近问题
8.5排序问题
8.6划分问题
8.7图着色
8.8数值问题
8.9co-NP和NP的不对称性
8.10困难问题的部分分类
带解答的练习
练习
注释和进一步阅读
第9章PSPACE：NP之外的一类问题
9.1PSPACE
9.2PSPACE中的一些难题
9.3在多项式空间中求解量化问题和博弈
9.4在多项式空间中求解规划问题
9.5证明问题是PSPACE接近的
带解答的练习
练习
注释和进一步阅读
第10章扩展易解性的界限
10.1寻找小的顶点覆盖
10.2求解树上的NP困难问题
10.3圆弧集着色
*10.4图的树分解
*10.5构造树分解
带解答的练习
练习
注释和进一步阅读
第11章近似算法
11.1贪心算法和很优值的界限：负载均衡问题
11.2中心选址问题
11.3集合覆盖：一般贪心启发式
11.4定价方法：顶点覆盖
11.5用定价方法优选化：不相交路径问题
11.6线性规划和舍入：顶点覆盖的应用
*11.7再论负载均衡：更高级的LP应用
11.8任意好的近似：背包问题
带解答的练习
练习
注释和进一步阅读
第12章局部搜索
12.1优化问题的地形
12.2Metropolis算法和模拟退火算法
12.3局部搜索在Hopfield神经网络中的应用
12.4通过局部搜索的优选割近似
12.5选择邻居关系
*12.6用局部搜索分类
12.7很优响应动态和纳什均衡
带解答的练习
练习
注释和进一步阅读
第13章随机算法
13.1第一个应用：消除争用
13.2寻找全局最小割
13.3随机变量及其期望
13.4MAX3-SAT的随机近似算法
13.5随机分治：找中位数和Quicksort
13.6哈希：字典的随机实现
13.7寻找最近点对：随机方法
13.8随机缓存
13.9切尔诺夫界
13.10负载均衡
13.11分组路由
13.12背景知识：一些基本概率定义
带解答的练习
练习
注释和进一步阅读
后记：永远运行的算法
参考文献