算法分析进阶：超越最坏情况分析 [美]蒂姆·拉夫加登
定 价：179 元
- 作者：[美]蒂姆·拉夫加登
- 出版时间：2024/10/1
- ISBN：9787111760184
- 出 版 社：机械工业出版社
- 中图法分类：TP301.6
- 页码：
- 纸张：胶版纸
- 版次：
- 开本：16开
本书源于斯坦福大学的研究生课程，由40位学者联袂撰写，旨在推广zui坏情况分析的替代方法，以及这些方法的应用，包括聚类、线性规划和神经网络训练等。
算法设计中没有灵丹妙药（no silver bullet）——不存在任何一种足够强大和灵活，能够解决所有计算问题的算法思想。同样，算法分析中也没有灵丹妙药，因为对算法进行分析的最具启发性的方法往往取决于问题和应用的细节。然而，典型的算法课程几乎完全停留在一种单一的分析框架上，即最坏情况分析。本书的目的就是纠正这种不平衡。
前 言Beyond the Worst-Case Analysis of Algorithms
算法设计中不存在任何灵丹妙药 原文为no silver bullet，源于Frederick P. Brooks, Jr. 在1986年发表的著名同名文章。——译者注——不存在任何一种足够强大和灵活，能够解决所有我们感兴趣的计算问题的算法思想。因此，本科的算法课程应该退而求其次，强调少量的通用算法设计范例（比如动态规划、分治算法和贪心算法），其中的每一种范例适用于跨越多个应用领域的一系列问题。
算法分析中也不存在灵丹妙药，因为对算法进行分析的最具启发性的方法往往取决于问题和应用的细节。然而，典型的算法课程的重点几乎完全停留在一种单一的分析框架，即最坏情况分析，一个算法由其在一个给定规模的任意输入上的最差性能进行评估。本书的目的是要纠正这种不平衡，推广若干种最坏情况分析的替代方法（这些方法主要在过去20年的理论计算机科学文献中逐渐形成），以及它们的一些最为引人注目的算法应用。40位卓越的研究者介绍了这个领域的各个方面，导论式的第1章对本书内容逐章进行概述。
本书源于我在斯坦福大学开发和教授过几次的研究生课程。 我的主页 (www.timroughgarden.org) 提供了这门课程的课堂讲稿和视频，其中涵盖了本书的几个主题。虽然本书的范围已经远远超出了一学期（甚至一学年）的课程所能讲授的内容，不过这本书的子集可以构成各种研究生课程的基础。我要求各位作者避免进行全面的综述，而专注于少数的关键模型和结果，这些模型和结果可以在二年级研究生的理论计算机科学和理论机器学习课堂上讲授。大部分章节以开放式的研究方向以及适合课堂教学的练习题作为结束。本书英文版的电子版可以从https://www.cambridge.org/9781108494311#resources获得（密码为 BWCA_CUP）。
如果没有许多人的辛勤工作，就不可能出版如此规模的专辑。首先，我要感谢各位作者在撰写自己的章节时的奉献和守时精神，以及对其他章节初稿的反馈。我要感谢Avrim Blum、Moses Charikar、Lauren Cowles、Anupam Gupta、Ankur Moitra和Greg Valiant在本书英文版处于萌芽阶段时的热情参与和出色的建议。我还要感谢所有选修我的CS264和CS369N课程的斯坦福大学的学生，特别是我的助教Rishi Gupta、Joshua Wang和Qiqi Yan。本书英文版封面由Max Greenleaf Miller设计。本书英文版的编辑得到了NSF奖项CCF-1813188和ARO奖项W911NF1910294的部分支持。
蒂姆·拉夫加登（Tim Roughgarden）
哥伦比亚大学计算机科学系教授，之前曾任教于斯坦福大学，主要研究领域包括算法、博弈论以及微观经济学。他曾获得美国青年科学家与工程师总统奖（PECASE），ACM颁发的Grace Murray Hopper奖，世界博弈论学会颁发的Kalai奖，数学优化学会颁发的Tucker奖，以及EATCS-SIGACT颁发的G?del奖。
译者序
前言
作者名单第1章 引言1 1.1 算法的最坏情况分析1
1.1.1 不可比较算法的比较1
1.1.2 最坏情况分析带来的好处2
1.1.3 算法分析的目标2
1.2 著名的失败事件和对替代方法的
迫切需要3
1.2.1 线性规划的单纯形法3
1.2.2 聚类与NP困难最优化
问题3
1.2.3 机器学习的不合理的
有效性4
1.2.4 在线算法分析5
1.2.5 最坏情况分析的骗局5
1.3 示例：在线分页问题中的参数
化界6
1.3.1 根据引用局部性的参数化6
1.3.2 定理1.1的证明7
1.3.3 讨论8
1.4 本书概述9
1.4.1 最坏情况分析的改进9
1.4.2 确定性数据模型10
1.4.3 半随机模型11
1.4.4 平滑分析12
1.4.5 机器学习和统计学中的
应用13
1.4.6 进一步的应用14
1.5 本章注解16
致谢16
参考文献16
练习题17第一部分 最坏情况分析的改进第2章 参数化算法20 2.1 引言20
2.1.1 热身：顶点覆盖问题20
2.2 随机化23
2.2.1 随机分离：集合拆分问题25
2.2.2 去随机化26
2.3 结构上的参数化26
2.4 核心化27
2.4.1 热身：Buss规则27
2.4.2 形式定义以及与FPT的成员
关系28
2.4.3 Buss规则在矩阵秩上的
推广29
2.5 困难性和最优性30
2.5.1 W\[1\]困难性30
2.5.2 ETH和SETH31
2.5.3 核心化的困难性和最优性32
2.6 展望：新的范例和应用领域33
2.6.1 FPT-近似和有损核心33
2.6.2 P问题中的FPT35
2.6.3 应用领域36
2.7 总体方向36
2.8 本章注解36
参考文献37
练习题40第3章 从自适应分析到实例
最优性41 3.1 案例研究1：最大点集合问题41
3.1.1 Jarvis步进算法41
3.1.2 Graham扫描算法42
3.1.3 Marriage Before Conquest
算法42
3.1.4 垂直熵43
3.1.5 （忽视顺序的）实例
最优性44
3.1.6 部分有序的输入46
3.1.7 不可能性的结果46
3.2 案例研究2：实例最优的聚合
算法47
3.2.1 实例最优性47
3.2.2 问题的设定48
3.2.3 阈值算法48
3.2.4 阈值算法的实例最优性49
3.2.5 最优性比上的匹配下界49
3.3 对更多结果和技术的综述50
3.3.1 输入顺序50
3.3.2 输入结构50
3.3.3 顺序与结构之间的协同
作用51
3.4 讨论51
3.4.1 与参数化算法的比较51
3.4.2 与在线算法的竞争分析的
比较52
3.5 开放式问题精选52
3.5.1 高维的情况52
3.5.2 最大点集合的分层52
3.6 关键要点53
3.7 本章注解53
致谢53
参考文献53
练习题54第4章 资源增广57 4.1 再论在线分页问题57
4.1.1 模型57
4.1.2 FIF和LRU57
4.1.3 竞争比58
4.1.4 资源增广界58
4.2 讨论59
4.3 自私路由问题61
4.3.1 模型和一个推动研究的
示例61
4.3.2 资源增广保证62
4.3.3 定理4.4的证明
（平行边）62
4.3.4 定理4.4的证明
（一般网络）63
4.4 调度问题中速度的改变64
4.4.1 非预知未来调度64
4.4.2 关于SETF的资源增广
保证65
4.4.3 引理4.8的证明：准备
工作66
4.4.4 引理4.8的证明：主要
论证67
4.5 松弛竞争算法69
4.6 本章注解71
致谢71
参考文献71
练习题72第二部分 确定性数据模型第5章 扰动弹性76 5.1 引言76
5.2 组合最优化问题78
5.3 认证算法的设计80
5.4 认证算法示例84
5.5 扰动弹性的聚类问题85
5.5.1 度量扰动弹性蕴含了
中心紧邻性87
5.6 2-扰动弹性实例的算法88
5.7 k-median的（3+ε)-认证的
局部搜索算法90
5.8 本章注解91
参考文献92
练习题94第6章 近似解稳定性与代理
目标95 6.1 引言和动机95
6.2 定义和讨论96
6.3 k-median问题99
6.3.1 定义99
6.3.2 一些令人关注的结果99
6.3.3 算法和证明100
6.3.4 小簇的处理104
6.4 k-means、min-sum以及其他聚类
目标105
6.5 聚类应用105
6.6 纳什均衡106
6.7 总体方向107
6.8 开放式问题108
6.9 松弛108
6.10 本章注解108
参考文献109
练习题110第7章 稀疏恢复111
书单推荐![算法分析进阶：超越最坏情况分析 [美]蒂姆·拉夫加登](/uploadfile/202411/9787111760184.jpg)
