算法和数论

下面是一些值得一读的算法书和数论书，有些我读过了，有些我正在读，有些放在将来的reading list里。


Introduction to Algorithms
by Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein
MIT Press

这本书的昵称是clrs。一提到算法，大家都会推荐这本书（其实还有aho/hopcroft/ullman的书也是经典）。它在我书架上呆了3年，我到现在还没有认真通读过它（shame on me），我总是被它1200页的厚度吓倒了。所以没有切身体会过它的好。从MIT可以下到Leiserson上这门课的录像。我觉得听课没有自己看书有效率，至少我的专业课在中国是这样，老师顶多起到答疑的作用。


Algorithms
by S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani
Cambridge Univ. Press

这本书很多同学都不知道，因为这本书2006年才面世。我觉得这是算法中最好的书，没有“之一”。就我读过的章节评判，它比上面那本clrs要好。非常inspiring! 还有作者网站上可以免费下载到这本书。12月中Papadimitriou来我们这晃了一次，我在他楼下等了一个下午加一个晚上想让他给我的书签名。这本书的缺点就是有点简略，所以仅仅完成它的第一章我就买了3本书作为补充材料。


下面是数论书籍：

An Introduction to the Theory of Numbers
by G. H. Hardy, E. M. Wright
Oxford Univ. Press

这本书写于1930s，传世佳作。数论好材料，可以体会到数学之美，这本书数学系的同学都应该读一下。哈代也是20世纪有所成就的数学家，他的弟子里有奇葩Ramanujan。天才数学家里短命的很多，Ramanujan只活了37年，Abel只活了29年，真可惜呀。我希望我能活到把我的reading list读完。


A Computational Introduction to Number Theory and Algebra
by Victor Shoup
Cambridge Univ. Press

不要被书名中的introduction迷惑了，读这本砖头需要十足的耐心。我花了整整半个月才推进了150页，和上面那本书一样，书里数学符号有时比文字还多，经常一群不等式，每个不等式里的每个不等关系都要推导一番，有时在一个推导上卡住就要卡一个晚上直到灵感闪现。这也正是数学吸引人的地方吧。数论部分写的非常清晰，算法部分写的有些过于rigorous，代数部分有点抽象。总之这本大部头的书写的很好，我愿成为吾校阅毕此书之第一人。对了，这本书也是可以直接去作者主页免费下载的。
It makes you a man (or woman) with class :)


Algorithmic Number Theory (Volume I: Efficient Algorithms)
by Eric Bach, Jeffrey Shallit
MIT Press

有口碑的一本书，适合计算机系的同学阅读。厚度适中只有300多页。Bibliography非常详细。我是折腾了一阵才私印到的，因为买不到。作者准备写Volume II，但是写了12年了还没写出来。他俩都是Blum的学生，Blum是Marvin Minsky的学生。

还有一本图论的书，据说很经典，还没看

Network Flows: Theory, Algorithms, and Applications
by Ravindra Ahuja, Thomas Magnanti, James Orlin
Prentice Hall

最后，学数论时可以借助Mathematica进行计算，它比Matlab更偏向纯数学而不是工程。利用数论中的性质写程序时，可以用python语言，因为它支持任意精度的数字，非常适合计算大整数，c和c++则需要用额外的库。