01 / 導讀
導讀
引用
Cormen, T. H. (2013). Algorithms Unlocked. MIT Press.
章節概要
Algorithms Unlocked 是一本篇幅不長的書（約236頁，圖書館書目記為xiii + 222頁），共十章，之後是參考文獻和索引。出版社把它介紹為由 Introduction to Algorithms 的合著者為非專業讀者撰寫的指南，「用有限的數學」解釋演算法如何讓計算機解決問題。書中的演算法以虛擬碼給出，各章從查詢和排序講起，經過圖、字串、密碼學和壓縮，一直講到沒有人知道如何高效求解的問題。
第1章：什麼是演算法，為什麼要關心演算法？
開篇一章講計算機演算法是什麼，以及讀者為什麼應該關心它們。Mike James在 I Programmer 上的書評指出，這一章以通俗的英語開頭，但在最初幾頁內就出現了n的平方根之類的代數內容。
第2章：如何描述和評估計算機演算法
講如何用虛擬碼（陣列、迴圈、遞迴）書寫演算法，以及如何分析其執行時間，包括類似大O的記號。同一篇書評指出，這一章引入了迴圈不變式和遞迴，這標示了本書的程度。
第3章：排序和查詢演算法
從線性查詢和二分查詢講到標準的比較排序。Google Books書目中的術語列表包括選擇排序、插入排序、歸併排序和快速排序；James稱這一章講的是每個程式設計師都應當瞭解的查詢與排序理論。
第4章：排序的下界以及如何突破
講為什麼基於比較的排序無法突破某個下界，以及計數排序這類不比較鍵的排序如何繞開它。
第5章：有向無環圖
從有向無環圖開始，把圖作為任務間依賴關係和網路的模型；出版社舉出的圖可以建模的例子有道路網路、任務依賴關係和金融關係。
第6章：最短路徑
講最短路徑演算法：據James介紹，包括Dijkstra演算法、Bellman-Ford演算法和Floyd-Warshall演算法，他稱這一章數學味較濃，有矩陣和較長的程式。Google Books術語列表中的負權環、優先佇列等詞也指向同樣的內容。
第7章：字串演算法
講以DNA為背景的字串問題，包括最長公共子序列以及把一個字串變換為另一個字串。
第8章：密碼學基礎
講密碼學背後的基本原理：書評提到RSA和隨機數生成，Google Books術語列表中包括明文、密文和素數。
第9章：資料壓縮
講壓縮的基礎知識；據書評介紹，從霍夫曼編碼開始，一直講到常見壓縮工具的基礎LZW。
第10章：難？問題
講旅行推銷員問題、P與NP、NP完全性、NP困難性和不可判定性，並涉及3-CNF可滿足性、哈密頓迴路和k團等問題之間的多項式時間歸約。書評者稱這是最偏理論的一章。
核心概念
第1–4章：描述、分析與排序
- 演算法：接受輸入併產生正確輸出的精確步驟，以正確性和執行時間來評判。
- 虛擬碼與迴圈不變式：與具體語言無關的演算法表述方式，以及論證演算法正確性的工具。
- 執行時間分析：操作次數如何隨輸入規模增長。
- 排序下界：比較排序的極限，以及計數排序這類避免比較的排序。
第5–7章：圖與字串
- 有向無環圖：沒有環的圖，用於建模任務間的依賴關係。
- 最短路徑：在加權圖中求路徑的Dijkstra、Bellman-Ford和Floyd-Warshall演算法。
- 最長公共子序列：透過逐步累積子問題答案來求解的字串問題。
第8–10章：秘密、壓縮與難解性
- 公鑰密碼：像RSA這樣建立在數論基礎上的加密。
- 霍夫曼編碼與LZW：用變長編碼壓縮，以及用重複字串字典壓縮。
- NP完全性與歸約：為什麼有些問題似乎沒有高效演算法，以及如何證明一個問題與另一個問題一樣難。
評析
優點
- 小書大視野。 短短十章涵蓋了演算法課程的核心（排序、圖演算法、NP完全性），還加入了字串處理、密碼學和資料壓縮各章，讓讀者看到演算法的用途遠不止於排序。
- 專家為新手而寫。 作者是 Introduction to Algorithms 的合著者，出版社引用的推薦語稱本書易讀而不失深度。
- 講的是真正的演算法，而不只是故事。 James認為，本書用虛擬碼給出實際的演算法並做執行時間分析，因此比科普讀物教得更多；對於能跟上細節的讀者，他稱之為「真正好讀的書」。
局限
- 程度混雜。 James的主要批評是：行文針對完全的初學者，而頁面上卻有大量代數、虛擬碼、迴圈不變式和分析；需要最淺顯講解的讀者可能會被數學擋住，而能駕馭數學的讀者又可能覺得語氣過於淺白。
- 不是練習冊。 出版社的介紹和書評都沒有提到練習，目錄中也看不到；習慣透過做題學習的讀者需要另備一本書。
- 只有虛擬碼。 書評指出本書堅持使用虛擬碼，讀者需要自己把演算法改寫成真正的程式語言。
在課程中的定位
本書是本課程中最平易的一本，可在讀完整教材之前作為預習。Roughgarden的 Algorithms Illuminated 是自然的下一步：這是一本基於作者線上課程的完整教材，配有影片、小測驗、習題和程式設計練習，以更大的深度講解同樣的內容。Skiena的 The Algorithm Design Manual 適合想獲得為實際問題選擇演算法的實用指導的讀者。
Cormen、Leiserson、Rivest和Stein的 Introduction to Algorithms 是同一作者與同事合著的全面教材；James把 Algorithms Unlocked 稱為通往作者那本「更成熟的書」的入口。課程中關於近似演算法和隨機化演算法的著作（Vazirani；Williamson和Shmoys；Mitzenmacher和Upfal）要在學完一門完整的演算法課之後很久才讀。
如何使用本書
本書適合準備學習或剛開始學習電腦科學的一年級學生、沒有受過正規訓練但想了解標準演算法背後原理的程式設計師，以及不怕代數的其他領域讀者。James認為理想的讀者是電腦科學一年級學生或預備學生，或者想輕鬆瞭解這一領域的程式設計師。有一定程式設計經驗會讓虛擬碼容易理解得多。
實用閱讀計畫：
- 核心： 第1–3章和第5–6章，它們提供了基本詞彙（虛擬碼、執行時間）、排序與查詢演算法，以及後續每門課程都會用到的圖與最短路徑演算法。
- 其次： 第4章和第10章；關於下界和NP完全性的兩章引入的概念，在完整課程中會得到更形式化的證明。
- 按興趣選讀： 講字串、密碼學和壓縮的第7–9章，在讀完第2章後可以按任意順序閱讀。
邊讀邊動筆：在小輸入上逐步跟蹤每個虛擬碼過程，並用自己熟悉的語言實現兩三個演算法（二分查詢、歸併排序、Dijkstra演算法）。之後再轉向帶有習題的教材進行練習。
