[电子书] 算法导论(第2版/中文版/英文版，包括笔记、练习等) 2007-01-25

本帖隐藏的内容需要回复才可以浏览

来源：点击进入
转载日期：2010-01-19

前言（Preface）

第一部分（Part I） 基础（Foundations）

    第一章 计算中算法的角色（The Role of Algorithms in Computing）
    第二章 开始（Getting Started）
    第三章 函数的增长率（Growth of Functions）
    第四章 递归（Recurrences）
    第五章 概率分析与随机化算法（Probabilistic Analysis and Randomized Algorithms）

第二部分（Part II） 排序与顺序统计（Sorting and Order Statistics）

    第六章 堆排序（Heapsort）
    第七章 快速排序（Quicksort）
    第八章 线性时间中的排序（Sorting in Linear Time）
    第九章 中值与顺序统计（Medians and Order Statistics）

第三部分（Part III） 数据结构（Data Structures）

    第十章 基本的数据结构（Elementary Data Structures）
    第十一章 散列表（Hash Tables）
    第十二章 二叉查找树（Binary Search Trees）
    第十三章 红-黑树（Red-Black Trees）
    第十四章 扩充的数据结构（Augmenting Data Structures）

第四部分（Part IV） 高级的设计与分析技术（Advanced Design and Analysis Techniques）

    第十五章 动态规划（Dynamic Programming）
    第十六章 贪婪算法（Greedy Algorithms）
    第十七章 分摊分析（Amortized Analysis）

第五部分（Part V） 高级的数据结构（Advanced Data Structures）

    第十八章 B-树（B-Trees）
    第十九章 二项式堆（Binomial Heaps）
    第二十章 斐波纳契堆（Fibonacci Heaps）
    第二十一章 不相交集的数据结构（Data Structures for Disjoint Sets）

第六部分（Part VI） 图算法（Graph Algorithms）

    第二十二章 基本的图算法（Elementary Graph Algorithms）
    第二十三章 最小生成树（Minimum Spanning Trees）
    第二十四章 单源最短路径（Single-Source Shortest Paths）
    第二十五章 全对的最短路径（All-Pairs Shortest Paths）
    第二十六章 最大流（Maximum Flow）

第七部分（Part VII） 精选的主题（Selected Topics）

    第二十七章 排序网络（Sorting Networks）
    第二十八章 矩阵运算（Matrix Operations）
    第二十九章 线性规划（Linear Programming）
    第三十章 多项式与快速傅里叶变换（Polynomials and the FFT）
    第三十一章 数论算法（Number-Theoretic Algorithms）
    第三十二章 字符串匹配（String Matching）
    第三十三章 计算几何学（Computational Geometry）
    第三十四章 NP-完备性（NP-Completeness）
    第三十五章 近似算法（Approximation Algorithms）

第八部分（Part VIII） 附录：数学背景（Mathematical Background）

    附录A 求和（Summations）

    附录B 集合，等等。（Sets, Etc.）

    附录C 计数与概率（Counting and Probability）

参考文献（Bibliography）

索引（Index）

来源：点击进入
2009-05-15

长期以来，我对于是否要在博客上写非技术类的东西取决不下。同是从0开头学习技术，一定会遇到许多相似的问题，我把它们记下来，还会给人以帮助。但是非技术类的东西，写了也是给自己看的，在没有从“对小我的思考”转变为“对大我的思考”之前(看了刘未鹏的博客后的感触)，我不需要别人的理解和同情。再者，即使面对面交流，也不能保证使一个人完全理解另一个人，更何况活的思考变成死的文字。然而今天，我只是想把憋在心里的话写出来。人的层次并不相同，譬如许多计算机专业的学生在进入大学之前已能熟练编程，而我其时还连光驱和光盘都弄不清楚。我只是也想在这里说说自己一直放在心里没有说的话，来我博客的朋友请略过这一篇。

事情源于一次对比。最近学习网络流算法，啃了国内一本知名的算法教材好几天，通过不断重复倒是熟记了很多基本概念，但是记住的概念越多，心里的问号越多。对于算法学习来说，死记硬背算法是很低效的。我于是翻开《算法导论》，交叉学习。看了《算法导论》几页，发现两本书讲解方式上有非常大的不同，简单对比如下：《算法导论》中，第26章讲网络流算法，总共用了35页(翻译过来的中文版)，使用了10组演示图片，总共使用了64行伪代码；国内的那本知名教材，讲解同样内容的网络流算法，用了40页，4张图片，没有一张图片是用来演示算法执行流程的，最让我吃惊的是，在40页的算法讲解中，C++代码超过了20页！

64行伪代码和超过20页的C++代码，这巨大的反差，使我对国内那本教材非常失望和惋惜。这让我想到霍金引用过的一句话，大意是书中每一条物理公式会使读者的数量减少一半，同样，对于讲解算法的书，代码的行数是与书的可读性成反比的。代码是非常有个人特色的，看到与自己风格不同的代码，不自觉就会产生一种排斥的心理。更不用说我们国内教材中的代码：风格混乱，字体难看，纸张低劣，印刷错误。最让我痛苦的是，完整的代码被切割得很碎，配合着讲解算法的需要，这里撒一小块，那里撒一小块，我经常为了一个莫名其妙的变量和函数调用到处在前面的书页中找它的意义，或者根据上下文去猜它的意义。代码中不可避免地要用到如栈、队列、链表等这些基本数据结构，为了能集中精力讲算法，这些数据结构的实现代码是不应该贴上来的，所以只好杜撰一些名称，用惯了STL，我对这些不遵守STL中的约定的代码非常反感。一边看书我一边提醒自己，知道这些代码表示什么意思就行了，没必要对这些代码这么认真。我想，作者的初衷是为了实用，我仔细读了些代码，感觉作者对算法的实现是非常精简的，代码的细节也处理的很好，但是很可惜，代码中有太多的细节了，一门生僻的伪代码又会加重读者的负担，两难的选择。

如果说这本教材让我感到惋惜，那么其它的教材，书店里铺天盖地的基础教程、入门教程，就让人愤怒了。尽管电子工业出版社和机械工业出版社不断推出让人一看就想买下来的书，这却对教材没有产生任何的影响。回想我大学时候的教材，C、C++、数据结构、算法，其中充斥着大量风格糟糕的代码：没有缩进，没有注释、变量名一律abcd或者汉语拼音。我当时痛苦地写着这样的代码，在我上C++课时看到老师在黑板上写下intanIntVar;这样的语句时，我为这个变量名兴奋了好久。随着写的代码多了起来，与非教材类的经典技术书籍的接触多了起来，我对大学的教材和课堂的失望和反感也与日俱增。大学里那些理论性强的专业课的教材，很多地方明明几句话就可以点透的东西，却啰哩啰嗦晦涩难懂的讲上一大堆，在需要仔细讲解的时候，却往往又一句话带过，似乎唯恐不能炫耀其高超的水平。那些艰涩的文字，读完很多遍才发现也不过就是那么回事，真让人觉得，采用这种方式讲解的目的，就是因为对真正的难题束手无策，才专门在这些小问题上大做文章。既没有数学的简洁直接，又不通俗，一句话：入的貌似很深，出的绝对不浅。

这些烂教材和烂书导致了一个更严重的后果：真正好的教材被忽视了。而今，一提起“教材”这个词语，我们的印象就是一堆内容陈腐、讲解死板、形式僵化、专门用来应付考试的垃圾纸。这使得那些教材中十分珍贵的精华被一起当成了垃圾，考完试就随手抛掉。这对任何一方，都是巨大的浪费。

事实上，大学的专业课教材有些并不比那些经典著作省钱。为什么我们在课堂上就只能看到那些纸张低劣的教材，既然自己没有好的，为什么不“拿来”更好的？

上面这些只是我的牢骚，我刚上大学时对计算机是个白痴，经常被一大堆名词弄的晕头转向，上很多课，我看不到这和计算机有什么联系，老师也从不讲开的这些课都有什么用，所以经常逃课，等到知道逃的课很有用的时候，那门课已经考完试了，所以积累了不少牢骚。但我也在网上看到很多的对我极有启发的博客，看到很多文笔非常优秀的技术作家，牢骚归牢骚，我还是充满了希望的。只是感觉，需要时间。

来源：点击进入
2008-03-06 04:51:35      　　来自: etone           

　　我对《算法导论CLRS》的态度一直是有所保留的。虽然早在国内的时候，这本书一直被推崇为经典。但我那时就觉得它对算法的描述不好。一段费解的伪码，加上一大段费口舌的解释。我觉得本可以做得更好。
　　
　　后来知道，这是典型的美国本科生用书，美国的本科教材，大抵很罗嗦，都是厚重的大部头书。教授们生怕稍有简略，学生们就不懂；而美国的小本们，也傻呵呵的认为书头越重，自己越了不起。
　　
　　这书中的大段解释，也确是一番好意，就怕哪个不懂。可要真是老老实实的读下去，分散注意要超过传达信息。
　　
　　这本书我读的最快乐的部分，就是每章的chapternotes。也就是在一章的末尾，介绍这一章提到的各种内容是何时、被谁、怎样引入计算机科学的。不看这部分，总觉得学的就是书上的死学问。而这些引用出处却为我们理清了算法研究的历史脉络，各个经典结果的师承关系。读这些为我带来了巨大的乐趣。也建议读此书的人千万不要放过这一部分，这些引用的结果就是算法研究的里程碑。
　　
　　对于算法的伪码描述，倒不必太仔细了。不能指望在算法课上学习编程，算法本来就是很纯粹的数学对象，它的设计思想完全依托于背后的数学结构，它运作的机制以及它的美，也都来自它的数学，可是书上那些模仿C和Pascal的语句，让算法的数学之美沦为一段机械代码。读者辛苦的把自己的思维变成机器，读懂了这些代码，但并不会直接带来对算法本身的领悟。就像一个人懂得了打牌的游戏规则，但并不意味着他就会打牌了，因为他可能依旧不通晓牌理。对算法的学习也要从问题本身的数学结构入手，理解解决此种结构问题的算法它的设计思想，掌握分析具有各种结构特征的算法的数学工具，学习怎样发现问题的结构并从中推出问题的下界（lower bound）。这些才是学习算法的根本。
　　
　　《算法导论》的最大成就，也就在于它的选材。它筛选出来的结果，每一个都当之无愧的算是计算机科学的根基或里程碑。在所有的算法教材中，这一点《算法导论》被公认是作的最好的。结构也组织的合理。尽管它的讲解，对这些经典结果的呈现，都不是我最满意的方式。但明珠纵然暗投也终究是明珠，《算法导论》覆盖的内容，可作为算法最好的教学大纲，是算法课的原型。这是它不容抹煞的历史地位。

相关评论：

　　除了“它对算法的描述不好。一段费解的伪码，加上一大段费口舌的解释。我觉得本可以做得更好。 ”之外，其他的评论都可认为是“极力推荐”之词了。
　　
　　“一段费解的伪码，加上一大段费口舌的解释。”，嗯哼？也许我可以同意“本可以做得更好”，但我更非常关心的是，是否已经有人做得比他们好了呢？:-)

　　对于算法的伪码描述，倒不必太仔细了。不能指望在算法课上学习编程，算法本来就是很纯粹的数学对象，它的设计思想完全依托于背后的数学结构，它运作的机制以及它的美，也都来自它的数学，可是书上那些模仿C和Pascal的语句，让算法的数学之美沦为一段机械代码。
　　
　　not really, 我相信对很多cs的小孩来说，对伪代码的理解速度远远超过对数学概念。
　　其实个人一直觉得算导上的伪代码写的简洁明快，不想看前面的分析了一看伪代码立马理解了。。。

　　我同意lz的看法，我买了算法导论第二版的中文版，由潘金贵等译。
　　但看了以后，感觉没有大家所推荐的那么好。
　　因为可读性不佳。讲的比较难懂。
　　我由此对网络上的各种推荐都持保留态度，后来也发现，许多人对书籍的推荐，不是来自自己的思考和自己的体验，而是copy所得。有一个人将一篇推荐写的不错，于是后面就有很多人跟着说，嗯，不错，好书，经典！
　　这是很不负责任的态度。
　　不好意思，有点离题。

　　你傻冒啊
　　chapter notes和算法没关系，说的些杂七杂八的东西
　　它对算法的描述哪儿不好了？
　　几乎每段都加了注释，它并不专注于什么语言
　　为了便于理解，有的地方直接用的english描述的
　　
　　通常一个麻烦的算法，它都分步讲解
　　从core到crust
　　
　　你看看严婆婆的那个书
　　那个描述的好吗？
　　算法啊
　　算法啊
　　弄了那么多语言细节
　　明明一个a不等于b可以判断的东西
　　非要写一堆
　　
　　这个书，你没看完，别瞎说

　　1、
　　  这是典型的美国本科生用书，美国的本科教材，大抵很罗嗦，都是厚重的大部头书。教授们生怕稍有简略，学生们就不懂；
　　  而美国的小本们，也傻呵呵的认为书头越重，自己越了不起。
　　----------------
　　前面第一段说得很对，总结出特点来了，可惜你当它是缺点；
　　后一段更显你的偏激，臆想连篇。
　　////////////////
　　2、
　　  这书中的大段解释，也确是一番好意，就怕哪个不懂。可要真是老老实实的读下去，分散注意要超过传达信息。
　　----------------
　　  你完全可以跳过去，只看你需要的，毕竟尊重大多数人是人家的民主思想所在，你显然习惯了中国国情，属于高高在上的或自认为的精英份子吧
　　适合你的才是正确的，不然就全是在浪费，那些不懂的人根本就不应该学这些东西，这本书应该是只为你这样的精英服务才对，这是你的逻辑吗？
　　
　　我觉得，好的书就应该啰嗦点，这样适合大部分人，让大部分不至于因为理解能力稍有偏差就受到打击而放弃，大多数人能进步才是最大的功劳。
　　你觉得是啰嗦，其实正是它对大多数人的尊重，对我们来说，是详尽。

　　  我觉得还行, 语言相当的优美精练. 至于大段大段的解释, 你不想看就直接跳过去呗.
　　  最让我晕的就是那一个接一个的证明, 看得我头好大, 可是如果不把它看懂的话, 就没法理解的深刻, 郁闷!

　　我同意lz的看法，我买了算法导论第二版的中文版，由潘金贵等译。
　　　　但看了以后，感觉没有大家所推荐的那么好。
　　　　因为可读性不佳。讲的比较难懂。
　　　　我由此对网络上的各种推荐都持保留态度，后来也发现，许多人对书籍的推荐，不是来自自己的思考和自己的体验，而是copy所得。有一个人将一篇推荐写的不错，于是后面就有很多人跟着说，嗯，不错，好书，经典！
　　　　这是很不负责任的态度。
　　　　不好意思，有点离题。
　　----------------------------------------------------------------------------------------
　　
　　翻译的书，我从不认为是可以读懂的书。
　　所以请不要用翻译的书来评价原著。
　　谢谢。

　　国外的书 需要耐心阅读 对如算法新手 这本书 需要的是耐心读下去  慢慢的 你就会发现越来越舒服~~

　　我很同意你的观点，应该是“有保留的推荐”。
　　因为我感觉 这本书还可以写的更好。它给我的感觉就像是潘爱民翻译的《计算机网络》一书。但是还有不足，无法使我拍案叫绝。可是那本自顶向下的网络书就会使我拍案叫绝。 “ 这本书我读的最快乐的部分，就是每章的chapternotes。也就是在一章的末尾，介绍这一章提到的各种内容是何时、被谁、怎样引入计算机科学的。不看这部分，总觉得学的就是书上的死学问。”以前没有体会，做科研之后，发现确实如此。 读那些原文文章，比读教科书更加有益。

　　恩，，最近正在读这本书，也说说我的观点：
　　首先，“有保留的推荐”我是支持的，我觉得本书最精彩的部分就是一大段大段的解释，但是最让人容易分散注意力的也是这一大段大段的解释。不管怎么说，我看起来分散注意力的时候居多。
　　第二，本书应该可以写的更好，如果对每个算法刚开始能用最通俗易懂的语言来描述它，然后再对他进行解释和论证，那样会更好，这样这本书的使用范围会更广。
　　第三，国内很多大学本科根本就没有算法课（除开一些重点高校外），只有数据结构课程，上了研究生才开了算法课，但是算法导论里面的数学的东西我们在本科的时候都学过了，现在研究生再回过头来看算法导论，里面很多数学的东西早就忘得一干二净，看起书来自然感觉很不爽，这种课程安排方式导致知识脱节，很难真正把学过的东西用上，其实本科学的数学的知识只有在研究生才真正得到应用，但是很不幸，到了研究生我们已经把数学忘了。所以我觉得在本科阶段三年级或者四年级的时候应该要开算法导论这本科，或者我们自己应要看起来了。

　　个人倒觉得，学理工科的话，数学这东西倒是像吃饭要筷子喝水要杯子一样，自然而然的事。不能寄希望于学完数学然后再学其它需要数学的东西，要用点搬点也许更加有效率和直观。其实不少把算导翻烂的，根本就是高中生。。。需要的时候，就去学吧，谁让咱忘了呢：）

　　这书中的大段解释，也确是一番好意，就怕哪个不懂。可要真是老老实实的读下去，分散注意要超过传达信息。
　　　　
　　　　这本书我读的最快乐的部分，就是每章的chapternotes。也就是在一章的末尾，介绍这一章提到的各种内容是何时、被谁、怎样引入计算机科学的。不看这部分，总觉得学的就是书上的死学问。而这些引用出处却为我们理清了算法研究的历史脉络，各个经典结果的师承关系。读这些为我带来了巨大的乐趣。也建议读此书的人千万不要放过这一部分，这些引用的结果就是算法研究的里程碑。
　　　　
　　　　对于算法的伪码描述，倒不必太仔细了。不能指望在算法课上学习编程
　　---------------------------------------
　　谢谢上面的话:)
　　1、我觉得看理科的书最重要是形象化的过程。例如，算法要看数据是怎么搬动的。算法就是研究数据变动的。
　　2、从更显浅的层次一层层的剖析。计算机的结构依据就是层结构。

chinakr

来源：点击进入
2009-11-24 22:41:44      　　来自: jyo     (活在数字时代)      

　　这本书和国内学者编写的算法教材有些差别。
　　
　　首先，就像其他国外教材一样，该书讲解的很细致，习惯国内教材的读者可能觉得写得有点罗嗦，不过个人感觉很适合自学。
　　
　　其次，每一章节最后都附有延伸阅读的建议，对于深入学习很有帮助。
　　
　　最后，本书对算法的讲解使用的是伪码，不存在编程语言方面的障碍。不过，我建议如果能将书中的伪码都改成自己熟悉的语言，并上机运行通过，那对算法的理解帮助时很大的。

相关评论：

　　很好的一本书，非常锻炼思维，里面的伪代码都字斟句酌，十分严谨。但是对于从事工程项目意义不大

　　当年数学不认真学，打开看了N多公式，吓到了。

来源：点击进入
2006-12-18 14:09:28      　　来自: Wilson

　　勿庸置疑，这是一本很好的书；但同时也是一本很厚的书。一千多页的文字读完之后，实在感觉有点累。呵呵，当然收获也是很多的了，不过第一感觉还是累
　　
　　　　首先说一下这本书的大概内容，给手里没有这本书的同志们。如作者在"To the student"中所说，这本书给我们的是"anenjoyable introduction to the field ofalgorithms"。本书包括数据结构，算法设计等方面的内容，是以"step bystep"的方式讲解的，也提供了详细严谨的数学说明。书里的算法是用混和pascal和c风格的伪码描述的。作为"Introduction"，这本书的大部分内容都适合作为本科教材，不过同时也是一本算法和算法证明的工具书。68元1200页，真的不贵。
　　
　　　　看这本书的前提：有一定程序设计经验，了解比如链表之类的初级数据结构知识；再有高等数学的基础就够了，本科教材嘛。按照出版社的说法："具备初步编程经验的人也可读懂"。
　　
　　　　至于本书的英语水平，这可能是很多人关心的。我感觉这本书大部分的叙述都很简单明了，大概六级的水平就可以很通顺的阅读。一开始可能不太习惯，看了1/3之后就好了，基本上习惯了作者的思路，阅读几乎没有障碍，偶尔查个单词。最后一部分感觉好像换了作者，经常用些我不认识的形容词......不过，如果不认识就跳过去也不影响阅读。
　　
　　　　总体的感觉，这本书的风格主要有两个特点：一是重证明，二是重启发。

cici16320

好东西哦，支持一下

goodzhengcheng

dsfffffffffffffffffffffff

chinakr

找工作必看

tyria

谢谢，楼主分享。