算法分析進階：超越最壞情況分析 [美]蒂姆·拉夫加登
定 價：179 元
- 作者：[美]蒂姆·拉夫加登
- 出版時間：2024/10/1
- ISBN：9787111760184
- 出 版 社：機械工業(yè)出版社
- 中圖法分類：TP301.6
- 頁碼：
- 紙張：膠版紙
- 版次：
- 開本：16開
本書源于斯坦福大學(xué)的研究生課程，由40位學(xué)者聯(lián)袂撰寫，旨在推廣zui壞情況分析的替代方法，以及這些方法的應(yīng)用，包括聚類、線性規(guī)劃和神經(jīng)網(wǎng)絡(luò)訓(xùn)練等。
算法設(shè)計中沒有靈丹妙藥（no silver bullet）——不存在任何一種足夠強大和靈活，能夠解決所有計算問題的算法思想。同樣，算法分析中也沒有靈丹妙藥，因為對算法進行分析的最具啟發(fā)性的方法往往取決于問題和應(yīng)用的細節(jié)。然而，典型的算法課程幾乎完全停留在一種單一的分析框架上，即最壞情況分析。本書的目的就是糾正這種不平衡。
前 言Beyond the Worst-Case Analysis of Algorithms
算法設(shè)計中不存在任何靈丹妙藥 原文為no silver bullet，源于Frederick P. Brooks, Jr. 在1986年發(fā)表的著名同名文章�！g者注——不存在任何一種足夠強大和靈活，能夠解決所有我們感興趣的計算問題的算法思想。因此，本科的算法課程應(yīng)該退而求其次，強調(diào)少量的通用算法設(shè)計范例（比如動態(tài)規(guī)劃、分治算法和貪心算法），其中的每一種范例適用于跨越多個應(yīng)用領(lǐng)域的一系列問題。
算法分析中也不存在靈丹妙藥，因為對算法進行分析的最具啟發(fā)性的方法往往取決于問題和應(yīng)用的細節(jié)。然而，典型的算法課程的重點幾乎完全停留在一種單一的分析框架，即最壞情況分析，一個算法由其在一個給定規(guī)模的任意輸入上的最差性能進行評估。本書的目的是要糾正這種不平衡，推廣若干種最壞情況分析的替代方法（這些方法主要在過去20年的理論計算機科學(xué)文獻中逐漸形成），以及它們的一些最為引人注目的算法應(yīng)用。40位卓越的研究者介紹了這個領(lǐng)域的各個方面，導(dǎo)論式的第1章對本書內(nèi)容逐章進行概述。
本書源于我在斯坦福大學(xué)開發(fā)和教授過幾次的研究生課程。 我的主頁 (www.timroughgarden.org) 提供了這門課程的課堂講稿和視頻，其中涵蓋了本書的幾個主題。雖然本書的范圍已經(jīng)遠遠超出了一學(xué)期（甚至一學(xué)年）的課程所能講授的內(nèi)容，不過這本書的子集可以構(gòu)成各種研究生課程的基礎(chǔ)。我要求各位作者避免進行全面的綜述，而專注于少數(shù)的關(guān)鍵模型和結(jié)果，這些模型和結(jié)果可以在二年級研究生的理論計算機科學(xué)和理論機器學(xué)習(xí)課堂上講授。大部分章節(jié)以開放式的研究方向以及適合課堂教學(xué)的練習(xí)題作為結(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課程的斯坦福大學(xué)的學(xué)生，特別是我的助教Rishi Gupta、Joshua Wang和Qiqi Yan。本書英文版封面由Max Greenleaf Miller設(shè)計。本書英文版的編輯得到了NSF獎項CCF-1813188和ARO獎項W911NF1910294的部分支持。
蒂姆·拉夫加登（Tim Roughgarden）
哥倫比亞大學(xué)計算機科學(xué)系教授，之前曾任教于斯坦福大學(xué)，主要研究領(lǐng)域包括算法、博弈論以及微觀經(jīng)濟學(xué)。他曾獲得美國青年科學(xué)家與工程師總統(tǒng)獎（PECASE），ACM頒發(fā)的Grace Murray Hopper獎，世界博弈論學(xué)會頒發(fā)的Kalai獎，數(shù)學(xué)優(yōu)化學(xué)會頒發(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 機器學(xué)習(xí)的不合理的
有效性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 機器學(xué)習(xí)和統(tǒng)計學(xué)中的
應(yīng)用13
1.4.6 進一步的應(yīng)用14
1.5 本章注解16
致謝16
參考文獻16
練習(xí)題17第一部分 最壞情況分析的改進第2章 參數(shù)化算法20 2.1 引言20
2.1.1 熱身：頂點覆蓋問題20
2.2 隨機化23
2.2.1 隨機分離：集合拆分問題25
2.2.2 去隨機化26
2.3 結(jié)構(gòu)上的參數(shù)化26
2.4 核心化27
2.4.1 熱身：Buss規(guī)則27
2.4.2 形式定義以及與FPT的成員
關(guān)系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 展望：新的范例和應(yīng)用領(lǐng)域33
2.6.1 FPT-近似和有損核心33
2.6.2 P問題中的FPT35
2.6.3 應(yīng)用領(lǐng)域36
2.7 總體方向36
2.8 本章注解36
參考文獻37
練習(xí)題40第3章 從自適應(yīng)分析到實例
最優(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 不可能性的結(jié)果46
3.2 案例研究2：實例最優(yōu)的聚合
算法47
3.2.1 實例最優(yōu)性47
3.2.2 問題的設(shè)定48
3.2.3 閾值算法48
3.2.4 閾值算法的實例最優(yōu)性49
3.2.5 最優(yōu)性比上的匹配下界49
3.3 對更多結(jié)果和技術(shù)的綜述50
3.3.1 輸入順序50
3.3.2 輸入結(jié)構(gòu)50
3.3.3 順序與結(jié)構(gòu)之間的協(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 關(guān)鍵要點53
3.7 本章注解53
致謝53
參考文獻53
練習(xí)題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)絡(luò)）63
4.4 調(diào)度問題中速度的改變64
4.4.1 非預(yù)知未來調(diào)度64
4.4.2 關(guān)于SETF的資源增廣
保證65
4.4.3 引理4.8的證明：準備
工作66
4.4.4 引理4.8的證明：主要
論證67
4.5 松弛競爭算法69
4.6 本章注解71
致謝71
參考文獻71
練習(xí)題72第二部分 確定性數(shù)據(jù)模型第5章 擾動彈性76 5.1 引言76
5.2 組合最優(yōu)化問題78
5.3 認證算法的設(shè)計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
練習(xí)題94第6章 近似解穩(wěn)定性與代理
目標95 6.1 引言和動機95
6.2 定義和討論96
6.3 k-median問題99
6.3.1 定義99
6.3.2 一些令人關(guān)注的結(jié)果99
6.3.3 算法和證明100
6.3.4 小簇的處理104
6.4 k-means、min-sum以及其他聚類
目標105
6.5 聚類應(yīng)用105
6.6 納什均衡106
6.7 總體方向107
6.8 開放式問題108
6.9 松弛108
6.10 本章注解108
參考文獻109
練習(xí)題110第7章 稀疏恢復(fù)111
書單推薦![算法分析進階：超越最壞情況分析 [美]蒂姆·拉夫加登](/images/noimages.gif)
