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算法）。之后再转向带有习题的教材进行练习。
