Blum的算法书单
作者:谢勰
导言
这是图灵奖得主Manuel Blum教授为CMU研究生阶段算法课程开出的书单(原文地址)并有简短的书评(以列表形式给出),为了便于大家学习提高,我们将其译为中文并“画蛇添足”了一些个人阅读感受(以引文形式标出)。
另外八卦一下,Blum的夫人Lenore Blum也是CMU计算机系的教授,著有Complexity and Real Computation,研究方向是复杂性与实(数)计算。他们的儿子Avrim Blum现在也是CMU计算机系的教授,研究方向是机器学习理论和算法理论。所以,他们三个人都非常非常了得,大家在这个页面上可以看到他们的家庭情况和照片。
译文
指定教材:
- Dexter C. Kozen. The Design and Analysis of Algorithms, Springer-Verlag, 1992.
- 这是一部传世名典。重要而且较难的那些算法阐述得很好,而且算法分析很清晰。非常值得认真研读。
这本书以讲座形式写就,着重讲解算法设计思路,一个章节就是完整的讲义,但是读起来可能还需要配合一些参考文献。Kozen是Cornell大学的教授,而这本书也是Corenll大学研究生阶段算法课程多年以来的教材。
可选阅读:
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 3rd Edition, MIT Press, 2009.
- 虽然很厚重但却是极好的一部本科生教材。
《算法导论》不必多说,自然是极好的。CLRS他们早已开始在撰写第四版了,按照每版十年的节奏,新版不远了。
- N. Alon and J. Spencer. The Probabilistic Method. Wiley Interscience, New York, 1992.
- 这是一本很棒的书。它会用各种方式指引你去学概率方法……较难的问题和简单的问题交错编排。
概率方法由著名数学家Erdős所开创的研究分支,不过这本书不好读懂。
- Sarah Baase and Allen van Gelder. Computer Algorithms, Introduction to Design and Analysis. Addison-Wesley, 2000.
这本书国内有影印版,也被一些学校用作教材,但流行程度一般。
- Jon Bentley. Programming Pearls, Addison-Wesley, Inc., 2000.
- Jon Bentley文笔优美,著作也非常富有洞见。
很有名的《编程珠玑》,也是大家耳熟能详的经典。
- Avrim Blum. On-line notes for CS451.
- 这里有许多很好的阅读材料,写得非常细致严谨。
Blum自豪地夸一下自己孩子写的讲义。
- 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完全问题。
《计算机与难解性》,要想检索难解问题,找这本最合适。
- Michael Kearns and Umesh Vazirani. An Introduction to Computational Learning Theory, MIT Press, 1994.
这是关于计算学习理论的一本经典著作,偏重于理论计算机科学家的视角。
- Jon Kleinberg and Éva Tardos. Algorithm Design, Addison-Wesley, 2005.
目前与《算法导论》齐名的本科生算法教材,两位作者都来自Cornell大学,第2版据说将于2018年出版。Kleinberg属于理论学界的明星人物,拿过Nevanlinna奖。
- U. Manber. Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1990.
- 我特别喜欢第1章末尾的那些问题。它们会让你有一个明确的认识,也就是本书会让你学到哪些类型问题的求解方法。
中文名《算法引论》,这本书的核心就是基于归纳法来设计算法,这也是此书独特之处。
- Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms, Cambridge University Press, 1995.
随机算法的标准教材,作者之一的Motwani不幸英年早逝于自家的游泳池,令人扼腕。
- 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。
- 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大师有一系列让人眼花缭乱的算法成果,我们以后再单独撰文谈他。
- Vijay Vazirani. Approximation Algorithms, Springer-Verlag, Berlin, 2001.
近似算法的标准教材,别无二选。
- Peter Winkler. Mathematical Puzzles: A Connoisseur's Collection, A K Peters, Wellesley, MA, 2004.
- 对于本科生、研究生还有专家来说,这些谜题都是非常精彩的。书中很多问题都有解答,但是请……试着在看答案之前先试着自己求解一下。最后一章列出了许多公开问题。当然,公开问题嘛,自然是处于悬而未决的状态,不过书中对它们都给出了来龙去脉和当前研究进展。我希望将来几十年内许多书中的公开问题“将会”得到解答。你何不一试身手呢?
这本书的封面是利用宝石平铺六边形的一个直观证明,可搜索“Diamonds in a Hexagon”问题。
- John H. Reid (editor). Synthesis of Parallel Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, 1993.
- 这本书由多位作者完成,是关于并行算法的一本很好的参考书。
- Joseph JaJa. Introduction to Parallel Algorithms, Addison-Wesley Profssional, 1992.
- 关于PRAM算法的一本书。
转载说明
原文发在微信公众号“算法时空”(主打算法与数据结构手写笔记),现重新编排如下。转载本文请注明出处,翻译以及附注由谢勰(微博)完成。
希望大家多多关注分享微信公众号“算法时空”,
Report Story