算法分析进阶：超越最坏情况分析
正版保障 假一赔十 可开发票
￥ 120.38 6.7折 ￥ 179 全新
库存52件
广东广州
认证卖家担保交易快速发货售后保障
作者[美]蒂姆·拉夫加登（Tim Roughgarden） 著
出版社机械工业出版社
ISBN9787111760184
出版时间2023-02
装帧平装
开本16开
定价179元
货号17713434
上书时间2025-01-08
商品详情
- 品相描述：全新
- 商品描述
-
目录
译者序<br />前言<br />作者名单第1章 引言1 1.1 算法的最坏情况分析1<br /> 1.1.1 不可比较算法的比较1<br /> 1.1.2 最坏情况分析带来的好处2<br /> 1.1.3 算法分析的目标2<br /> 1.2 著名的失败事件和对替代方法的<br />迫切需要3<br /> 1.2.1 线性规划的单纯形法3<br /> 1.2.2 聚类与NP困难最优化<br />问题3<br /> 1.2.3 机器学习的不合理的<br />有效性4<br /> 1.2.4 在线算法分析5<br /> 1.2.5 最坏情况分析的骗局5<br /> 1.3 示例：在线分页问题中的参数<br />化界6<br /> 1.3.1 根据引用局部性的参数化6<br /> 1.3.2 定理1.1的证明7<br /> 1.3.3 讨论8<br /> 1.4 本书概述9<br /> 1.4.1 最坏情况分析的改进9<br /> 1.4.2 确定性数据模型10<br /> 1.4.3 半随机模型11<br /> 1.4.4 平滑分析12<br /> 1.4.5 机器学习和统计学中的<br />应用13<br /> 1.4.6 进一步的应用14<br /> 1.5 本章注解16<br /> 致谢16<br /> 参考文献16<br /> 练习题17第一部分 最坏情况分析的改进第2章 参数化算法20 2.1 引言20<br /> 2.1.1 热身：顶点覆盖问题20<br /> 2.2 随机化23<br /> 2.2.1 随机分离：集合拆分问题25<br /> 2.2.2 去随机化26<br /> 2.3 结构上的参数化26<br /> 2.4 核心化27<br /> 2.4.1 热身：Buss规则27<br /> 2.4.2 形式定义以及与FPT的成员<br />关系28<br /> 2.4.3 Buss规则在矩阵秩上的<br />推广29<br /> 2.5 困难性和最优性30<br /> 2.5.1 W\[1\]困难性30<br /> 2.5.2 ETH和SETH31<br /> 2.5.3 核心化的困难性和最优性32<br /> 2.6 展望：新的范例和应用领域33<br /> 2.6.1 FPT-近似和有损核心33<br /> 2.6.2 P问题中的FPT35<br /> 2.6.3 应用领域36<br /> 2.7 总体方向36<br /> 2.8 本章注解36<br /> 参考文献37<br /> 练习题40第3章 从自适应分析到实例<br />最优性41 3.1 案例研究1：最大点集合问题41<br /> 3.1.1 Jarvis步进算法41<br /> 3.1.2 Graham扫描算法42<br /> 3.1.3 Marriage Before Conquest<br />算法42<br /> 3.1.4 垂直熵43<br /> 3.1.5 （忽视顺序的）实例<br />最优性44<br /> 3.1.6 部分有序的输入46<br /> 3.1.7 不可能性的结果46<br /> 3.2 案例研究2：实例最优的聚合<br />算法47<br /> 3.2.1 实例最优性47<br /> 3.2.2 问题的设定48<br /> 3.2.3 阈值算法48<br /> 3.2.4 阈值算法的实例最优性49<br /> 3.2.5 最优性比上的匹配下界49<br /> 3.3 对更多结果和技术的综述50<br /> 3.3.1 输入顺序50<br /> 3.3.2 输入结构50<br /> 3.3.3 顺序与结构之间的协同<br />作用51<br /> 3.4 讨论51<br /> 3.4.1 与参数化算法的比较51<br /> 3.4.2 与在线算法的竞争分析的<br />比较52<br /> 3.5 开放式问题精选52<br /> 3.5.1 高维的情况52<br /> 3.5.2 最大点集合的分层52<br /> 3.6 关键要点53<br /> 3.7 本章注解53<br /> 致谢53<br /> 参考文献53<br /> 练习题54第4章 资源增广57 4.1 再论在线分页问题57<br /> 4.1.1 模型57<br /> 4.1.2 FIF和LRU57<br /> 4.1.3 竞争比58<br /> 4.1.4 资源增广界58<br /> 4.2 讨论59<br /> 4.3 自私路由问题61<br /> 4.3.1 模型和一个推动研究的<br />示例61<br /> 4.3.2 资源增广保证62<br /> 4.3.3 定理4.4的证明<br />（平行边）62<br /> 4.3.4 定理4.4的证明<br />（一般网络）63<br /> 4.4 调度问题中速度的改变64<br /> 4.4.1 非预知未来调度64<br /> 4.4.2 关于SETF的资源增广<br />保证65<br /> 4.4.3 引理4.8的证明：准备<br />工作66<br /> 4.4.4 引理4.8的证明：主要<br />论证67<br /> 4.5 松弛竞争算法69<br /> 4.6 本章注解71<br /> 致谢71<br /> 参考文献71<br /> 练习题72第二部分 确定性数据模型第5章 扰动弹性76 5.1 引言76<br /> 5.2 组合最优化问题78<br /> 5.3 认证算法的设计80<br /> 5.4 认证算法示例84<br /> 5.5 扰动弹性的聚类问题85<br /> 5.5.1 度量扰动弹性蕴含了<br />中心紧邻性87<br /> 5.6 2-扰动弹性实例的算法88<br /> 5.7 k-median的（3+ε)-认证的<br />局部搜索算法90<br /> 5.8 本章注解91<br /> 参考文献92<br /> 练习题94第6章 近似解稳定性与代理<br />目标95 6.1 引言和动机95<br /> 6.2 定义和讨论96<br /> 6.3 k-median问题99<br /> 6.3.1 定义99<br /> 6.3.2 一些令人关注的结果99<br /> 6.3.3 算法和证明100<br /> 6.3.4 小簇的处理104<br /> 6.4 k-means、min-sum以及其他聚类<br />目标105<br /> 6.5 聚类应用105<br /> 6.6 纳什均衡106<br /> 6.7 总体方向107<br /> 6.8 开放式问题108<br /> 6.9 松弛108<br /> 6.10 本章注解108<br /> 参考文献109<br /> 练习题110第7章 稀疏恢复111 7.1 引言111<br /> 7.2 一种简单的只插入流算法112<br /> 7.3 删除的处理：线性概略算法113<br /> 7.3.1 CountMinSketch：1保证114<br /> 7.3.2 CountSketch：2保证116<br /> 7.3.3 关于恢复保证的讨论116<br /> 7.4 均匀算法118<br /> 7.4.1 受限的等距特性118<br /> 7.4.2 测量后噪声和测量前<br />噪声119<br /> 7.4.3 迭代法120<br /> 7.4.4 L1最小化121<br /> 7.5 下界122<br /> 7.6 不同的测量模型123<br /> 7.6.1 一种混合结果：RIP-1矩阵<br />和稀疏矩阵123<br /> 7.6.2 傅里叶测量124<br /> 7.7 矩阵恢复125<br /> 7.8 本章注解127<br /> 参考文献127<br /> 练习题129第三部分 半随机模型第8章 分布分析132 8.1 引言132<br /> 8.1.1 分布分析的利弊132<br /> 8.1.2 最优停止问题133<br /> 8.1.3 讨论133<br /> 8.1.4 阈值规则和先知不等式134<br /> 8.2 经典算法的平均情况论证135<br /> 8.2.1 快速排序135<br /> 8.2.2 线性探测136<br /> 8.2.3 装箱问题137<br /> 8.3 欧几里得问题的表现良好的平均<br />算法138<br /> 8.3.1 2D凸包问题138<br /> 8.3.2 平面上的旅行商问题139<br /> 8.3.3 讨论141<br /> 8.4 随机图和植入模型142<br /> 8.4.1 Erds-Rényi随机图142<br /> 8.4.2 植入图模型143<br /> 8.4.3 讨论144<br /> 8.5
— 没有更多了 —
以下为对购买帮助不大的评价