算法分析進階：超越最壞情況分析 [美]蒂姆·拉夫加登
定 價：179 元
- 作者：[美]蒂姆·拉夫加登
- 出版時間：2024/10/1
- ISBN：9787111760184
- 出 版 社：機械工業(yè)出版社
- 中圖法分類：TP301.6
- 頁碼：
- 紙張：膠版紙
- 版次：
- 開本：16開
本書源于斯坦福大學的研究生課程，由40位學者聯(lián)袂撰寫，旨在推廣zui壞情況分析的替代方法，以及這些方法的應用，包括聚類、線性規(guī)劃和神經網(wǎng)絡訓練等。
算法設計中沒有靈丹妙藥（no silver bullet）——不存在任何一種足夠強大和靈活，能夠解決所有計算問題的算法思想。同樣，算法分析中也沒有靈丹妙藥，因為對算法進行分析的最具啟發(fā)性的方法往往取決于問題和應用的細節(jié)。然而，典型的算法課程幾乎完全停留在一種單一的分析框架上，即最壞情況分析。本書的目的就是糾正這種不平衡。
前 言Beyond the Worst-Case Analysis of Algorithms
算法設計中不存在任何靈丹妙藥 原文為no silver bullet，源于Frederick P. Brooks, Jr. 在1986年發(fā)表的著名同名文章。——譯者注——不存在任何一種足夠強大和靈活，能夠解決所有我們感興趣的計算問題的算法思想。因此，本科的算法課程應該退而求其次，強調少量的通用算法設計范例（比如動態(tài)規(guī)劃、分治算法和貪心算法），其中的每一種范例適用于跨越多個應用領域的一系列問題。
算法分析中也不存在靈丹妙藥，因為對算法進行分析的最具啟發(fā)性的方法往往取決于問題和應用的細節(jié)。然而，典型的算法課程的重點幾乎完全停留在一種單一的分析框架，即最壞情況分析，一個算法由其在一個給定規(guī)模的任意輸入上的最差性能進行評估。本書的目的是要糾正這種不平衡，推廣若干種最壞情況分析的替代方法（這些方法主要在過去20年的理論計算機科學文獻中逐漸形成），以及它們的一些最為引人注目的算法應用。40位卓越的研究者介紹了這個領域的各個方面，導論式的第1章對本書內容逐章進行概述。
本書源于我在斯坦福大學開發(fā)和教授過幾次的研究生課程。 我的主頁 (www.timroughgarden.org) 提供了這門課程的課堂講稿和視頻，其中涵蓋了本書的幾個主題。雖然本書的范圍已經遠遠超出了一學期（甚至一學年）的課程所能講授的內容，不過這本書的子集可以構成各種研究生課程的基礎。我要求各位作者避免進行全面的綜述，而專注于少數(shù)的關鍵模型和結果，這些模型和結果可以在二年級研究生的理論計算機科學和理論機器學習課堂上講授。大部分章節(jié)以開放式的研究方向以及適合課堂教學的練習題作為結束。本書英文版的電子版可以從https://www.cambridge.org/9781108494311#resources獲得（密碼為 BWCA_CUP）。
如果沒有許多人的辛勤工作，就不可能出版如此規(guī)模的專輯。首先，我要感謝各位作者在撰寫自己的章節(jié)時的奉獻和守時精神，以及對其他章節(jié)初稿的反饋。我要感謝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）
哥倫比亞大學計算機科學系教授，之前曾任教于斯坦福大學，主要研究領域包括算法、博弈論以及微觀經濟學。他曾獲得美國青年科學家與工程師總統(tǒng)獎（PECASE），ACM頒發(fā)的Grace Murray Hopper獎，世界博弈論學會頒發(fā)的Kalai獎，數(shù)學優(yōu)化學會頒發(fā)的Tucker獎，以及EATCS-SIGACT頒發(fā)的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 線性規(guī)劃的單純形法3
1.2.2 聚類與NP困難最優(yōu)化
問題3
1.2.3 機器學習的不合理的
有效性4
1.2.4 在線算法分析5
1.2.5 最壞情況分析的騙局5
1.3 示例：在線分頁問題中的參數(shù)
化界6
1.3.1 根據(jù)引用局部性的參數(shù)化6
1.3.2 定理1.1的證明7
1.3.3 討論8
1.4 本書概述9
1.4.1 最壞情況分析的改進9
1.4.2 確定性數(shù)據(jù)模型10
1.4.3 半隨機模型11
1.4.4 平滑分析12
1.4.5 機器學習和統(tǒng)計學中的
應用13
1.4.6 進一步的應用14
1.5 本章注解16
致謝16
參考文獻16
練習題17第一部分 最壞情況分析的改進第2章 參數(shù)化算法20 2.1 引言20
2.1.1 熱身：頂點覆蓋問題20
2.2 隨機化23
2.2.1 隨機分離：集合拆分問題25
2.2.2 去隨機化26
2.3 結構上的參數(shù)化26
2.4 核心化27
2.4.1 熱身：Buss規(guī)則27
2.4.2 形式定義以及與FPT的成員
關系28
2.4.3 Buss規(guī)則在矩陣秩上的
推廣29
2.5 困難性和最優(yōu)性30
2.5.1 W\[1\]困難性30
2.5.2 ETH和SETH31
2.5.3 核心化的困難性和最優(yōu)性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章 從自適應分析到實例
最優(yōu)性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�。ê鲆曧樞虻模⿲嵗�
最優(yōu)性44
3.1.6 部分有序的輸入46
3.1.7 不可能性的結果46
3.2 案例研究2：實例最優(yōu)的聚合
算法47
3.2.1 實例最優(yōu)性47
3.2.2 問題的設定48
3.2.3 閾值算法48
3.2.4 閾值算法的實例最優(yōu)性49
3.2.5 最優(yōu)性比上的匹配下界49
3.3 對更多結果和技術的綜述50
3.3.1 輸入順序50
3.3.2 輸入結構50
3.3.3 順序與結構之間的協(xié)同
作用51
3.4 討論51
3.4.1 與參數(shù)化算法的比較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的證明
（一般網(wǎng)絡）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第二部分 確定性數(shù)據(jù)模型第5章 擾動彈性76 5.1 引言76
5.2 組合最優(yōu)化問題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章 近似解穩(wěn)定性與代理
目標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
書單推薦![算法分析進階：超越最壞情況分析 [美]蒂姆·拉夫加登](/images/noimages.gif)
