Blum的算法书单

作者:谢勰

导言

这是图灵奖得主Manuel Blum教授为CMU研究生阶段算法课程开出的书单(原文地址)并有简短的书评（以列表形式给出），为了便于大家学习提高，我们将其译为中文并“画蛇添足”了一些个人阅读感受（以引文形式标出）。

另外八卦一下，Blum的夫人Lenore Blum也是CMU计算机系的教授，著有Complexity and Real Computation，研究方向是复杂性与实（数）计算。他们的儿子Avrim Blum现在也是CMU计算机系的教授，研究方向是机器学习理论和算法理论。所以，他们三个人都非常非常了得，大家在这个页面上可以看到他们的家庭情况和照片。

译文

指定教材：

1. Dexter C. Kozen. The Design and Analysis of Algorithms, Springer-Verlag, 1992.

• 这是一部传世名典。重要而且较难的那些算法阐述得很好，而且算法分析很清晰。非常值得认真研读。

这本书以讲座形式写就，着重讲解算法设计思路，一个章节就是完整的讲义，但是读起来可能还需要配合一些参考文献。Kozen是Cornell大学的教授，而这本书也是Corenll大学研究生阶段算法课程多年以来的教材。

可选阅读：

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 3rd Edition, MIT Press, 2009.

• 虽然很厚重但却是极好的一部本科生教材。

《算法导论》不必多说，自然是极好的。CLRS他们早已开始在撰写第四版了，按照每版十年的节奏，新版不远了。

2. N. Alon and J. Spencer. The Probabilistic Method. Wiley Interscience, New York, 1992.

• 这是一本很棒的书。它会用各种方式指引你去学概率方法……较难的问题和简单的问题交错编排。

概率方法由著名数学家Erdős所开创的研究分支，不过这本书不好读懂。

3. Sarah Baase and Allen van Gelder. Computer Algorithms, Introduction to Design and Analysis. Addison-Wesley, 2000.

这本书国内有影印版，也被一些学校用作教材，但流行程度一般。

4. Jon Bentley. Programming Pearls, Addison-Wesley, Inc., 2000.

• Jon Bentley文笔优美，著作也非常富有洞见。

很有名的《编程珠玑》，也是大家耳熟能详的经典。

5. Avrim Blum. On-line notes for CS451.

• 这里有许多很好的阅读材料，写得非常细致严谨。

Blum自豪地夸一下自己孩子写的讲义。

6. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co. New York, NY, 1990.

• 优美而又清晰地阐明了NP完全性。书后所附大多数公开问题现在已解决。不过，图的同构、整数因子化和3-处理器调度目前仍然不知道是否为NP完全问题。

《计算机与难解性》，要想检索难解问题，找这本最合适。

7. Michael Kearns and Umesh Vazirani. An Introduction to Computational Learning Theory, MIT Press, 1994.

这是关于计算学习理论的一本经典著作，偏重于理论计算机科学家的视角。

8. Jon Kleinberg and Éva Tardos. Algorithm Design, Addison-Wesley, 2005.

目前与《算法导论》齐名的本科生算法教材，两位作者都来自Cornell大学，第2版据说将于2018年出版。Kleinberg属于理论学界的明星人物，拿过Nevanlinna奖。

9. U. Manber. Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1990.

• 我特别喜欢第1章末尾的那些问题。它们会让你有一个明确的认识，也就是本书会让你学到哪些类型问题的求解方法。

中文名《算法引论》，这本书的核心就是基于归纳法来设计算法，这也是此书独特之处。

10. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms, Cambridge University Press, 1995.

随机算法的标准教材，作者之一的Motwani不幸英年早逝于自家的游泳池，令人扼腕。

11. Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory, Cambridge University Press, Cambridge, 2007.

提供不可打印的网络版可供下载。

《算法博弈论》，作者Roughgarden在(http://theory.stanford.edu/~tim/f13/f13.html)中给出了下载地址，用户名是agt1user密码是camb2agt。

12. Robert Endre Tarjan. Data Structures and Network Algorithms (CBMS-NSF Regional Conference Series in Applied Mathematics), Society for Industrial and Applied Mathematrics, Philadelphia, PA, 1983.

• Bob Tarjan是世界超一流算法大师。

懂的人都知道，Tarjan大师有一系列让人眼花缭乱的算法成果，我们以后再单独撰文谈他。

13. Vijay Vazirani. Approximation Algorithms, Springer-Verlag, Berlin, 2001.

近似算法的标准教材，别无二选。

14. Peter Winkler. Mathematical Puzzles: A Connoisseur's Collection, A K Peters, Wellesley, MA, 2004.

• 对于本科生、研究生还有专家来说，这些谜题都是非常精彩的。书中很多问题都有解答，但是请……试着在看答案之前先试着自己求解一下。最后一章列出了许多公开问题。当然，公开问题嘛，自然是处于悬而未决的状态，不过书中对它们都给出了来龙去脉和当前研究进展。我希望将来几十年内许多书中的公开问题“将会”得到解答。你何不一试身手呢？

这本书的封面是利用宝石平铺六边形的一个直观证明，可搜索“Diamonds in a Hexagon”问题。

15. John H. Reid (editor). Synthesis of Parallel Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, 1993.

• 这本书由多位作者完成，是关于并行算法的一本很好的参考书。

16. Joseph JaJa. Introduction to Parallel Algorithms, Addison-Wesley Profssional, 1992.

• 关于PRAM算法的一本书。

转载说明

原文发在微信公众号“算法时空”(主打算法与数据结构手写笔记)，现重新编排如下。转载本文请注明出处，翻译以及附注由谢勰(微博)完成。

希望大家多多关注分享微信公众号“算法时空”，

Report Story