01 / 導讀
導讀
引用
Roughgarden, T. (2022). Algorithms Illuminated: Omnibus Edition. Soundlikeyourself Publishing (distributed by Cambridge University Press).
章節概要
合訂本（2022年9月）把分別出版的 Algorithms Illuminated 四個分冊匯為一冊約690頁的精裝書，並刪去了重複內容。全書分四部分共24章，另有兩個附錄、一篇後記（「演算法設計實地指南」）以及提示與解答。序言把本書比作一位資深輔導老師在一年一對一授課中所講內容的記錄，它基於作者自2012年起開設的線上課程和他在史丹佛大學講授的大學部課程。帶星號的小節最為高深，初讀時可以跳過而不影響連貫性；每章以「Upshot」（要點）小結和習題結束。
第一部分 第1–2章：引言；漸近記號
全書從整數乘法和Karatsuba演算法講起，接著是歸併排序及其分析，並以演算法分析的指導原則結束第1章。第2章講大O、大Ω和大Θ記號；序言解釋說，這是刻意忽略常數因子和低階項的一種建模選擇。
第一部分 第3–6章：分治演算法；主定理；快速排序；線性時間選擇
把分治法用於計算逆序對、Strassen矩陣乘法和最近點對；用主定理分析這類遞推式，給出六個例子和帶星號的證明；隨機化快速排序，包括好的樞軸為何重要，以及排序需要Ω(n log n)次比較的帶星號證明；最後是用隨機化的RSelect和確定性的DSelect實現線性時間選擇。
第二部分 第7–9章：圖的基礎；圖搜尋及其應用；Dijkstra最短路徑演算法
講圖的術語、應用、規模和表示方法；廣度優先搜尋與最短路徑、連通分量、深度優先搜尋、拓撲排序、強連通分量以及網路（Web）的結構；然後是Dijkstra演算法，附帶星號的正確性證明及其執行時間分析。
第二部分 第10–12章：堆；搜尋樹；雜湊表與布隆過濾器
序言說這一部分的目標是讓讀者成為資料結構的「內行使用者」，實現細節放在可選的帶星號小節中。堆的部分包括用它加速Dijkstra演算法；搜尋樹從有序陣列講到平衡搜尋樹；雜湊表之後是布隆過濾器以及對其錯誤率的啟發式分析。
第三部分 第13–15章：貪婪演算法入門；霍夫曼編碼；最小生成樹
透過一個排程問題及其正確性證明介紹貪婪範式；把最優字首碼看作樹的霍夫曼演算法；以及Prim演算法和Kruskal演算法求最小生成樹，分別藉助堆和並查集加速，並給出單鏈接聚類的應用。
第三部分 第16–18章：動態規劃入門；高階動態規劃；再論最短路徑
透過路徑上的加權獨立集問題引入動態規劃，配以重構演算法、方法的原理和背包問題；接著是序列比對和最優二叉搜尋樹；最後是處理負邊長的Bellman-Ford演算法和求全源最短路徑的Floyd-Warshall演算法。
第四部分 第19–21章：什麼是NP困難性？；在正確性上妥協：高效的非精確演算法；在速度上妥協：精確但低效的演算法
第四部分從最小生成樹與旅行推銷員問題的對比出發，講解容易與困難的問題、應對NP困難問題的策略、證明NP困難性的簡單方法以及常見的「新手錯誤」。第20章講快速的非精確演算法：最小化完工時間、最大覆蓋、影響力最大化、2-OPT啟發式演算法以及區域性搜尋的原理。第21章講精確但緩慢的方法：Bellman-Held-Karp演算法、用顏色編碼尋找長路徑，以及何時使用混合整數規劃求解器和可滿足性（SAT）求解器。
第四部分 第22–24章：證明問題是NP困難的；P、NP及其他；案例研究：FCC激勵拍賣
講歸約、3-SAT與Cook-Levin定理、歸約模板，以及獨立集、有向哈密頓路徑、旅行推銷員問題和子集和問題的NP困難性證明；全部小節帶星號的一章討論P、NP、P≠NP猜想、指數時間假設和NP完全性；最後是美國頻譜拍賣的案例研究，展示貪婪啟發式和藉助求解器的可行性檢驗如何在實踐中使用。
附錄、後記與提示
數學歸納法證明和離散機率的簡要回顧、演算法設計實地指南，以及章末習題的提示或解答。
核心概念
第一部分：基礎
- 漸近記號：大O、大Ω和大Θ，描述執行時間如何隨輸入規模增長。
- 分治法：分成子問題、遞迴求解、快速合併。
- 主定理：給出許多分治遞推式執行時間的公式。
- 隨機化演算法：執行中「拋銅板」的演算法，如隨機化快速排序和RSelect。
第二部分：圖演算法與資料結構
- 線性時間的圖搜尋：廣度優先和深度優先搜尋及其在連通性和排序上的應用。
- Dijkstra演算法：邊長非負時的單源最短路徑。
- 堆、搜尋樹和雜湊表：根據應用所需的操作來選擇的結構；布隆過濾器以偶爾出錯為代價節省空間。
第三部分：貪婪演算法與動態規劃
- 貪婪範式與正確性證明：短視且不可撤銷的決策，只對特定問題是最優的。
- 最小生成樹與並查集：Prim和Kruskal演算法，以及加速Kruskal演算法的資料結構。
- 動態規劃：系統地求解重疊子問題，如背包問題、序列比對和Bellman-Ford演算法。
第四部分：NP困難問題的演算法
- NP困難性與歸約：識別那些不太可能有總是正確又總是快速的演算法的問題。
- 啟發式與區域性搜尋：在正確性上妥協的快速演算法。
- 精確的指數時間演算法與求解器：用動態規劃、MIP和SAT求解器改進窮舉搜尋。
評析
優點
- 為教學而設計。 序言介紹，正文中穿插了100多道附有解答和說明的小測驗；章末習題從簡單的檢查題到開放性的挑戰題都有，全部附有提示或解答；配套網站還提供帶測試用例的程式設計題。
- 大部頭中有清晰的路線。 星號標出可以跳過的高深內容，每章以「Upshot」結束，序言還說明了哪些章節組彼此獨立（分治、貪婪和動態規劃可以按任意順序講授）。
- 免費影片課程。 作者錄製了200多個影片，覆蓋每一小節，另有Karger收縮演算法、Johnson演算法等額外主題，適合翻轉課堂或自學。
- 對NP困難性的實用處理。 第四部分不止於證明困難性，還講接下來該怎麼辦：啟發式、區域性搜尋、精確的指數時間演算法、MIP和SAT求解器，以及一個真實案例。
局限
- 只有虛擬碼，沒有程式碼。 本書用虛擬碼描述演算法，實現留給程式設計題；想要某種語言現成程式碼的讀者需要其他資料。
- 數學先修要求。 序言假定讀者有一定程式設計經驗，並熟悉數學歸納法和反證法；附錄只是簡要回顧。缺乏這些基礎的讀者能跟上演算法設計，但跟不上分析。
- 內容有所取捨。 網路流和線性規劃等主題沒有出現在目錄中，一些高階主題只在線上影片裡。
- 篇幅大。 約690頁的合訂本超出一門課的容量；序言本身就建議把它分給大學部課程（第一至三部分）和碩士課程（第三至四部分）。
在課程中的定位
本書是本課程第一門演算法課的主教材。Cormen的 Algorithms Unlocked 篇幅短、數學少，面向尚未準備好讀教科書的讀者，可作為第一、二部分的預習。Skiena的 The Algorithm Design Manual 以實踐的角度講解類似的技術，並附有演算法問題目錄，在應用演算法時可與Roughgarden同時或之後使用。Cormen、Leiserson、Rivest和Stein的 Introduction to Algorithms 是全面的教科書和參考書，適合想要嚴格論述和更廣覆蓋面的學生，其中包括本書沒有涉及的主題。
第四部分通向課程中的專門著作。Vazirani的 Approximation Algorithms 以及Williamson和Shmoys的 The Design of Approximation Algorithms 接續第20章「在正確性上妥協」的主題，討論有保證的近似比；Mitzenmacher和Upfal的 Probability and Computing 則展開隨機化快速排序、RSelect和布隆過濾器背後的機率論。
如何使用本書
本書適合二、三年級前後的電腦科學大學部學生、會程式設計並能讀懂證明的自學者，以及準備面試的軟體工程師。如有需要，先用附錄A和B複習歸納法和機率。
實用閱讀計畫：
- 第一門課（核心）： 第一至三部分，即第1–18章，初讀時跳過帶星號的小節。序言指出，資料結構各章（第10–12章）可以放在圖的各章（第7–9章）之前或之後，10.4節除外。
- 第二門課或自學： 第四部分，從第19章開始，再讀講實用技術的第20–21章和講歸約的第22章。第23章全部帶星號，可選讀；第24章是激發興趣的案例研究。
- 帶星號的小節： 掌握主要思想後，再回來讀其中的證明（主定理、快速排序的分析、Dijkstra演算法的正確性）。
遇到小測驗就停下來，先作答再往下讀。先做章末習題，之後再檢視提示和解答。每章至少藉助配套網站的測試用例實現一個演算法，書面難懂的小節可以看影片。考前閱讀各章的「Upshot」和實地指南。
