算法概论

出版时间：2009-1  出版社：机械工业出版社  作者：Sanjoy Dasgupta,Christos Papadimitriou,Umesh Vazirani  页数：376  译者：钱枫 注,邹恒明 注  
Tag标签：无  

前言

《算法概论》的前身是加州大学伯克利分校和加州大学圣迭戈分校本科生的算法课讲义。经过十年课堂教学的检验，这本书以其生动有趣的风格、精心挑选的内容和精确严谨的叙述受到了学术界和读者的一致好评。到目前为止，它是Amazon上获得五星的两本算法教材中的一本（另一本是《算法导论》，中文版已由机械工业出版社出版）。算法是计算机科学的灵魂，其复杂与抽象让许多学生望而却步。这本书最显著的特点是生动的写作风格：作者贯穿一条主线，以讲故事的形式将概念娓娓道来，非常易于理解和消化。

内容概要

本书源自加州大学伯克利分校和加州大学圣迭戈分校本科生的算法课讲义，以独特的视角展现了算法设计的精巧技术及魅力。在表达每一种技术时，强调每个算法背后的简洁数学思想，分析其时间和空间效率，运用与其他技术类比的方法来说明特征，并提供了大量实例。　　本书以人类最古老的算法（算术运算）为起点，将各种算法中优美而有代表性的内容囊括书中，并以最前沿的理论（量子算法）结束，构成了较为完整的算法知识体系。　　本书主要特点　　●生动的写作风格：作者贯穿一条主线，以讲故事的形式将概念娓娓道来，非常易于理解和消化。　　●优美地兼顾语言的生动和严谨性：本书中看不到很多数学公式，取而代之的是精确的文字叙述。　　●合理地挑选主题：用300多页的篇幅使读者对这门博大精深的科学有深刻的认识。　　●穿插注解框：内容包括人文历史背景、对复杂概念的进一步阐述、算法的扩展与重要应用等，对正文的叙述进行补充。

作者简介

Sanjoy Dasgupta，拥有加州大学伯克利分校计算机科学博士学位，现为加州大学圣迭戈分校教授，主要研究领域是多维数据的统计分析。他曾是AT&T实验室的高级技术人员。

书籍目录

出版者的话序言Preface方框目录0 Prologue（序论）　0.1 Books and algorithms（书和算法）　0.2 Enter Fibonacci（斐波那契数列）　0.3 Big-O notation（大O记号）　Exercises（习题）1 Algorithms with numbers（数的算法）　1.1 Basic arithmetic（基本算术）　1.2 Modular arithmetic（模运算）　1.3 Primality testing（素性测试）　1.4 Cryptography（密码学）　1.5 Universal hashing（全域散列）　Exercises（习题）　Randomized algorithms：a virtual chapter（虚拟章：随机化算法）2 Divide-and-conquer algorithms（分而治之算法）　2.1 Multiplication（乘法）　2.2 Recurrence relations（递归关系）　2.3 Mergesort（合并排序）　2.4 Medians（中位数）　2.5 Matrix multiplication（矩阵乘法）　2.6 The fast Fourier transform（快速傅里叶变换）　Exercises（习题）3 Decompositions of graphs（图的分解）　3.1 Why graphs?（图论）　3.2 Depth-first search in undirected graphs（无向图中的深度优先搜索）　3.3 Depth-first search in directed graphs（有向图中的深度优先搜索）　3.4 Strongly connected components（强连通分量）　Exercises（习题）4 Paths in graphs（图的路径）　4.1 Distances（距离）　4.2 Breadth-first search（广度优先搜索）　4.3 Lengths on edges（边的长度）　4.4 Dijkstra’s algorithm（Dijkstra算法）　4.5 Priority queue implementations（实现优先队列）　4.6 Shortest paths in the presence of negative edges（带负权的边的图中的最短路径）　4.7 Shortest paths in dags（有向无环图中的最短路径）　Exercises（习题）5 Greedy algorithms（贪婪算法）　5.1 Minimum spanning trees（最小生成树）　5.2 Huffman encoding（赫夫曼编码）　5.3 Horn formulas（Horn公式）　5.4 Set cover（集合覆盖）　Exercises（习题）6 Dynamic programming（动态规划）　6.1 Shortest paths in dags，revisited（回顾：有向无环图中的最短路径）　……7 Linear programming and reductions（线性规划与归约）8 NP-complete problems（NP完全问题）9 Coping with NP-completeness（处理NP完全问题）10 Quantum algorithms（量子算法）Historical notes and further reading（历史注记与扩展阅读）索引注释

章节摘录

插图：

用户评论 (总计38条)

•   书含有原版的全英文，其中在一些段落加入了注释，这本书也是几个大牛的杰作，适合算法比较好的人学习来看，注释版挺好的，这样能让读者读到几个人的理解，又因为有原文的存在不会让读者陷入迷途
•   此书比较深入浅出。。适合看《算法导论》感到吃力的哥们们，我对这本书的编排很喜欢，不是按枯燥的数据结构一章章的排，而是就一类问题缓缓展开着叙述，很适合我不足就在于机械工业出版社的纸张，太薄，无法做笔记，很容易穿。。
•   这本书是我的第一本算法书，对于了解算法，开始研究算法问题很有帮助。
•   收到就发现书角折了好多页，真心疼……书还是不错的！
•   很不错的一本书，内容详细，细节比较多。
•   很推荐 虽然是英文的 但看的时候并不吃力。。讲的很细。。
•   太给力了，书也不错，哈哈
•   强烈推荐，超级好书
•   没损坏，感谢零下20度送货的阿姨~
•   一直想看原版，终于买到了。翻了翻，发现质量还不错！
•   讲解非常精辟
•   速度很快，书籍很好。
•   sf! fantastic!
•   很难的啊，我是不太懂的啊
•   挺好的，差不多看完了
•   本来想学习英文的，买了之后太难了，也没看
•   这是一本适合入门的书，但却不失深度以及广度，读来让人兴趣盎然。我认为，认真读完这本书，并且思考每章后面的习题后，会对算法有一个很好的大局观。当然要掌握算法，只靠这一本书是不够的，不过算作最佳入门是当之无愧的。有一位网友的书评写比我的好得太多，由于字数限制，转载其中的大部分如下：＝＝＝＝＝＝＝＝＝转自豆瓣中 etone师兄的评论：很经典　　这是本很新的书，06年末发行，07年才慢慢出现于人们的视野。我在08年初得知这本书，那会我还很奇怪：都什么年月了，怎么还有人写算法教材——这么“经典”的工作，不是上个世纪就被人做完了吗。　　　　读了这本Algorithms，我才知道：这才是我心中的算法书，我等待这样一本书已经很多年了。它的确当得起这个名字。　　　　书的三位作者：Sanjoy Dasgupta, Papadimitrijou, Umesh Vazirani。　　　　其中，Umesh堪称计算机理论界的第二名师（第一名师是他自己的导师Manuel Blum），他带过的学生们犹如一个理论计算机科学新生代的全明星队。另一个作者Papadimitriou可算是理论界的第二名笔（第一非Knuth莫属），他的书Computational Complexity和Combinator...ial optimization堪称理论计算机科学最好读的专业书，他业余还写了本小说"Turing"。第三个作者Dasgupta是个算法方向的研究者，他最年轻，本身就是Umesh的学生，相比前面二位也没什么噱头——可他注定要因这本Algorithms而被载入计算机科学的史册。　　　　在这本书之前，算法的经典教材首推CLRS的算法导论。算法导论让人印象深刻的，是它内容的全面翔实，还有它一千两百页的厚度。　　　　而见到这本Algorithms时，你会震惊于它的薄。我从亚马逊收到这本书时，还以为拿错了包裹。　　　　可读过之后，你就会折服于它的美。　　　　这是一本可以给人带来巨大阅读乐趣的专业书籍。作者娓娓道来，又惜墨如金。用极精炼的语言，为我们指明了一条通向那些美丽算法的线索。我要由衷地说：这本书不仅仅是一些结果的集合，更是一段美好的旅程。我对书中涉及的内容已然熟悉，但读过之后仍感收获良多，对算法这门学问又多了些认识。真的是，写书当如是。这本Algorithms，在短短的篇幅内，做到了。　　　　三位作者可谓野心勃勃，几乎是胆大妄为。他们对传统算法教学思路的颠覆和背叛可谓前所未有。刚拿到目录的时候，我就替他们捏了一把汗，觉得这哪里像一本“正经”的算法书。可读下来，却不由得佩服——算法书早该这么写了。　　　 　他们并没有要全面的收录各种各样的算法，他们做的事情是理清了一条算法这门学问的线索。因此填鸭式的内容灌输不是这本书的目的；对结构的精心安排，对问 题的数学结构的剖析、从而推出一个算法的过程的讲解，都体现除了这本书真正的用心：它要让学生获得最大程度的启发，要训练学生独立解决问题的能力。　　　　我觉得这才是教育的真正目的，也是算法课应该追求的目标。　　　　　　说完了种种溢美之词，也来补充一下这本书的不足。这样一本精炼的算法书，为了它道理的清晰、为了它的美，必然会放弃一点对面面俱到的追求。如果我用这本书来教一门算法课的话，我会增加一点以下的内容：　　　　1. 数据结构。　 　这本书对数据结构没有单独的章节，都是在某个数据结构被一个算法用到的时候讲一下，例如priority queue之于Dijkstra's algorithm。这种做法体现了作者的观点：这门课完全就是关于algorithms，数据结构对于算法而言就只是个工具。如果同一个系还能开出一门 很强的data structures课，这么做当然很好，各有侧重。但若是我来上课，肯定会提一下数据结构的一些重要思想，例如hashing，和他们的数学背景。因为 对于一些实际问题，数据结构已不再是个工具，可能就是问题本身。　　　　2. 几个没有被此书涉及到的算法设计和分析的工具：对手论证(adversarial argument)，matroid，平摊分析(amortized analysis)。　　　　3. 书中每个算法问题目前最好的上下界(upper bounds, lower bounds)。 　　　　4. 讲一点比贪婪、动态规划等等更加“现代”的算法设计的思想，例如　　5. 除了这本Algorithms作为教材，补充读物可以在CLRS算法导论和Kleinberg和 阅读更多 ›
•   亚马逊上面显示中文版的 结果确实英文版的
•   派送速度快，杭州特能（名字很囧）久闻大名的书，内容尚不多言，单从印刷排版来讲，十分不错，可以阅读畅快。拿到手的时候发现写注释的正是《算法之道》的作者，曾随手翻阅过，读完这本再决定是否要再仔细阅之。如果硬要挑些不满，字号略小...
•   英文内容，加上适当的中文注解，易读，经典
•   英文版的理解起来还是有难度的，同时注释的地方并不是很全面，需要配合其他的书籍一起来理解。
•   但是 激励我要好好看下去。哪怕一个一个查单词我也会看下去的。
•   非常好！给力。赞一个
•   太深奥了，建议买中文版
•   与算法导论的风格完全不同，原来算法还可以写的这么有趣！
•   書的內容很好，符合演算法之重點主題。
•   大师的杰作，没得说，好好读就是了
•   强烈推荐，内容很好，并且主要是看原版英文，意思无差别。
•   个人感觉这个版本不是很好
•   读了这本书，让我对算法有了新的认识。并不是只有一般算法书中有的那些经典算法能称得上是算法，我们从小学开始学的加减乘除何尝不是算法呢？作者想讲述的是真真正正的算法的思想，并不是简单机械的算法分析。注释也非常好，并不是对原文的赘述，而是简单说明后的延伸，既能帮助你理解为能看懂的部分，又可以是你对这个算法有一些原著中没有提及的认识。... 阅读更多
•   这本书是比较偏理论的算法研究的，amazon能够非常快速送货到家，让我直接就可以阅读，不再像去书店购买那么麻烦，非常感谢！
•   经典的算法书籍
•   原版好书
•   上课用的，买来基本上没看过
•   喜欢英文版的
•   去掉注释
•   是算法方面的好书
•   英文原版+注释，很强大