说明
原文发在微信公众号“算法时空”(主打算法与数据结构手写笔记)，现重新编排如下。转载本文请注明出处，翻译以及附注由谢勰(微博)完成。
导言
这是图灵奖得主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大学的教授，而这本书也是Cornell大学研究生阶段算法课程多年以来的教材。
可选阅读：
[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.
- 提供不可打印的网络版可供下载。
[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算法的一本书。
网友评论