这是本很新的书,06年末发行,07年才慢慢出现于人们的视野。我在08年初得知这本书,那会我还很奇怪:都什么年月了,怎么还有人写算法教材——这么“经典”的工作,不是上个世纪就被人做完了吗。
读了这本Algorithms,我才知道:这才是我心中的算法书,我等待这样一本书已经很多年了。它的确当得起这个名字。
书的三位作者:Sanjoy Dasgupta, Papadimitriou, Umesh Vazirani。
其中,Umesh堪称计算机理论界的第二名师(第一名师是他自己的导师Manuel Blum),他带过的学生们犹如一个理论计算机科学新生代的全明星队。另一个作者Papadimitriou可算是理论界的第二名笔(第一非Knuth莫属),他的书Computational Complexity和Combinatorial optimization堪称理论计算机科学最好读的专业书,他业余还写了本小说"Turing"。第三个作者Dasgupta是个算法方向的研究者,他最年轻,本身就是Umesh的学生,相比前面二位也没什么噱头——可他注定要因这本Algorithms而被载入计算机科学的史册。
在这本书之前,算法的经典教材首推CLRS的算法导论。算法导论让人印象深刻的,是它内容的全面翔实,还有它一千两百页的厚度。
而见到这本Algorithms时,你会震惊于它的薄。我从亚马逊收到这本书时,还以为拿错了包裹。
可读过之后,你就会折服于它的美。
这是一本可以给人带来巨大阅读乐趣的专业书籍。作者娓娓道来,又惜墨如金。用极精炼的语言,为我们指明了一条通向那些美丽算法的线索。我要由衷地说:这本书不仅仅是一些结果的集合,更是一段美好的旅程。我对书中涉及的内容已然熟悉,但读过之后仍感收获良多,对算法这门学问又多了些认识。真的是,写书当如是。
对我来说,算法的教与学有两个困难的地方:
其一,我们学习了那些经典的算法,除了赞叹一下设计的巧思,但总难免问上一句:怎么想到的?对学生来说,这可能是最费解、也最让人窝火的地方。我们下再多的功夫去记忆书上的算法、去分析这些算法的效率,却终究不能理喻得到这些算法的过程。心理盘算着:给我一个新问题,让我设计个算法出来,我能行吗?答案是:不知道。
可这偏偏又是极重要的,无论作研究还是实际工作,一个计算机专业人士最重要的能力,就是解决问题——解决那些不断从理论模型、或者从实际应用中冒出来的新问题。
其二,算法作为一门学问,有两条正交的线索。一个是算法处理的对象:数、矩阵、集合、串(strings)、排列(permutations)、图(graphs)、表达式(formula)、分布(distributions),等等。另一个是算法的设计思想:贪婪、分治、动态规划、线性规划、局部搜索(local search),等等。这两条线索几乎是相互独立的:同一个离散对象,例如图,稍有不同的问题,例如single-source shortest path和all-pair shortest path,就可以用到不同的设计思想,如贪婪和动态规划;而完全不同的离散对象上的问题,例如排序和整数乘法,也许就会用到相同的思想,例如分治。
两条线索交织在一起,该如何表述。对学生而言,不同离散对象的差别是直观的——我们已经惯于在一章里面完全讲排序、而在另一章里面完全讲图论算法;可是对算法而言,设计思想的差别是根本的,因为这是从问题的结构来的:不同离散对象上面定义的问题,可以展现出类似的结构,而这结构特征,就是支持一类算法的根本,也是我们设计算法的依据。
坦率的说,之前还没有哪一本算法书很好的解决这两个困难,就连算法导论在这两个问题上也都做得不好。传统的算法书,大多注重内容(content)的收录,但却忽视思维过程的展示(exposition),因此我们学习了经典的算法,却费解于得到算法的过程;而且算法教材对于内容的编排多是枚举式的(enumerative),这多少是受了the art of computer programming的影响——可那是本工具书而不是教材,因此我们一提到算法课,就想起了排序、哈希、最短路径……这些题目(topics),却没有一个统一的线索在心中。
这本Algorithms,在短短的篇幅内,做到了。
三位作者可谓野心勃勃,几乎是胆大妄为。他们对传统算法教学思路的颠覆和背叛可谓前所未有。刚拿到目录的时候,我就替他们捏了一把汗,觉得这哪里像一本“正经”的算法书。可读下来,却不由得佩服——算法书早该这么写了。
他们并没有要全面的收录各种各样的算法,他们做的事情是理清了一条算法这门学问的线索。因此填鸭式的内容灌输不是这本书的目的;对结构的精心安排,对问题的数学结构的剖析、从而推出一个算法的过程的讲解,都体现除了这本书真正的用心:它要让学生获得最大程度的启发,要训练学生独立解决问题的能力。
我觉得这才是教育的真正目的,也是算法课应该追求的目标。
说完了种种溢美之词,也来补充一下这本书的不足。这样一本精炼的算法书,为了它道理的清晰、为了它的美,必然会放弃一点对面面俱到的追求。如果我用这本书来教一门算法课的话,我会增加一点以下的内容:
1. 数据结构。
这本书对数据结构没有单独的章节,都是在某个数据结构被一个算法用到的时候讲一下,例如priority queue之于Dijkstra's algorithm。这种做法体现了作者的观点:这门课完全就是关于algorithms,数据结构对于算法而言就只是个工具。如果同一个系还能开出一门很强的data structures课,这么做当然很好,各有侧重。但若是我来上课,肯定会提一下数据结构的一些重要思想,例如hashing,和他们的数学背景。因为对于一些实际问题,数据结构已不再是个工具,可能就是问题本身。
2. 几个没有被此书涉及到的算法设计和分析的工具:对手论证(adversarial argument),matroid,平摊分析(amortized analysis)。
3. 书中每个算法问题目前最好的上下界(upper bounds, lower bounds)。
对于一本书而言,让它记录这些不太现实,因为除非上下界已经紧了,也许出版的第二天就会有更好的上界或下界(其实这事已经发生了,书最结尾historical notes提了一句整数乘法的fastest known algorithm,结果现在这个结果已经被刷新了)。但老师上课的时候,应该跟学生们讲一下这个内容,让学生心里有这个“上下界”和"open problem"的概念,也晓得算法不是死知识,而是正在发生中的事。
4. 讲一点比贪婪、动态规划等等更加“现代”的算法设计的思想,例如spectral analysis, metric embedding, rapid mixing of markov chain等等。
也提一点当下的实际问题(例如google或豆瓣想解决的问题)面临的一些新的考虑,例如非经典的现实的计算模型:考虑内外存的I/O模型,面对海量数据输入的streaming model,海量数据的sub-linear algorithms等等。这些现实模型上的算法需要重新设计去面对新的考量。
我理解Algorithms这本书没有收录这些内容的原因。越是新的东西老的越快,没有人希望自己的书很快过时。但上课不妨出一些这样的case studies,时髦的东西学生肯定会很感兴趣,这些新东西的粗糙也可以锻炼学生实际解决问题的能力。
5. 除了这本Algorithms作为教材,补充读物可以在CLRS算法导论和Kleinberg和Tardos的算法设计(这也是本顶新的书)之间选择一本。我个人推荐后者。
算法之美
您对该书评有什么想说的?
对“算法之美”的回应
其二,算法作为一门学问,有两条正交的线索。一个是算法处理的对象:数、矩阵、集合、串(strings)、排列(permutations)、图(graphs)、表达式(formula)、分布(distributions),等等。另一个是算法的设计思想:贪婪、分治、动态规划、线性规划、局部搜索(local search),等等。这两条线索几乎是相互独立的:同一个离散对象,例如图,稍有不同的问题,例如single-source shortest path和all-pair shortest path,就可以用到不同的设计思想,如贪婪和动态规划;而完全不同的离散对象上的问题,例如排序和整数乘法,也许就会用到相同的思想,例如分治。
此书中文版已经出了
http://www.douban.co
这本书似乎没附带习题答案啊?各位谁有答案?
计算理论的研究、在思想和方法论上一直没有特别大的突破、很多书主要是介绍技巧、有的书还会进一步介绍这个技巧是怎么来的、但在设计思想上、依然约定俗成地遵循传统的思维范式、这个范式、如果从毕德格拉斯/欧几里德算起、已经有数千年的历史、从图灵/哥德尔/冯诺依曼算起、也已经有百年左右的历史:大家对这个范式已经非常习惯了、非常自然、连公理化一下都不需要了:):)
这个思维范式的特征、就是通过强制割裂显意识和潜意识的关系、来实现显意识的可计算化、进而制定算法、最后通过机器来执行这个算法
这个思维范式的成果之一、就是我们现在大量使用的计算设备、和背后的一整套计算理论(可扩展至含元数学理论)、更一般地、包括认识论中的公理化方法论
这个思维范式的局限性之一、就是我们现在所有的计算设备和计算理论(广义的人工智能)、和实际的人类自然智能相比、在方式上大相径庭、在解决问题的能力上也相差很多:形式系统的不完备性不仅仅表现在"不可计算确定"的定理的存在、更重要的是:形式系统由于过度依赖"公理化边界"和"计算确定"、从而造成计算能力的大幅度下降
连续统假设、在公理集合论上可等效选择公理等、在认识论层面可等效为潜意识是显意识的强包含关系(布劳威尔):连续统假设可看作是在理性计算的边界对于非理性世界的一种"感觉"。类似地:目前的计算理论、其计算能力是自然数量级的、不是实数量级的;而人类的自然计算能力、就其本质来说、至少是实数量级的(我个人认为也至多是实数量级的:):))
打个比方:当八部地龙、尼尔杨或诅咒(假设诅咒弹吉它)唱歌的时候、如果从他们的手上看、是G-G-C-D的和声结构、如果反映在一个听众或是演唱者本人的脑子里、就远远不是G-G-C-D的(可数)和声结构、而是丰富的多的(不可数)音乐感觉:从这个意义上看:目前的计算理论的计算能力、只是全部计算能力在显意识平面的投影、是"凝固然后显现"的感觉、是"压扁-简化"的感觉:只有把脑子里的感觉凝固(简化)了、手上才会出现相应的和声位置
目前的计算理论的水平、相当于只看到啦尼尔杨的手、而没有看到尼尔杨的脑:我们刻画出了尼尔杨手上的几十个把位、总结出一些和声进行的规律、并把尼尔杨目前已经创作出来的全部歌曲转化为MP3放在网络上:):)、所以如果想要再进一步的话、目前的计算理论就比较难了
但是不是就完全不可能呢?我想还是可能的:计算理论是可以发展的。如何产生具有实数量级的计算能力?我的初步想法"分布式人机混合计算系统":通过制定算法和制作机器来固化人类的理性计算能力、然后通过人和机器的强耦合来绕开传统计算系统的局限性、从而提高整个人机混合系统的计算能力:在这样的人机混合系统面前、或许一些传统的难题(如NP完全问题)将会有完全不同的、更好的解决办法。因特网是目前互联性最好的网络、所以第一步是先要做网站聚集人气(集中式耦合)、然后是发布节点进行协同计算(分布式耦合)、但是其他的具体措施还一点都不知道:):):):):)
《Algorithms》热门书评
-
算法之美
485有用 7无用 etone 2008-03-14
这是本很新的书,06年末发行,07年才慢慢出现于人们的视野。我在08年初得知这本书,那会我还很奇怪:都什么年月了,怎么还有人写算法教材——这么“经典”的工作,不是上个世纪就被人做完了吗。读了这本Algorithms,我才知道:这才是我心中的算法书,我等待这样一本书已经很多年了。它的确当得起这个名字。...
-
CLRS不应该是《Algorithms》的补充读物
41有用 2无用 [已注销] 2008-11-26
CLRS不应该是《Algorithms》(这本书会不会简称为DPV?)的补充读物,而应该是学习算法的主要入门教材。换句话说,《Algorithms》并不适合初学者阅读,因为它的简洁精炼,因为它的教学背景,也因为它的undercurrents。DPV不是传统意义上的算法教材,许多算法的经典内容在这里都...
-
原课程主页
13有用 0无用 让心飞一会儿 2012-03-04
Umesh V. Vazirani 06年berkeley 以这本书为教材开设的algorithms课程主页http://www-inst.eecs.berkeley.edu/~cs170/fa06/算法书不是用来看的,是用来学的...
-
翻译有点问题
12有用 0无用 corpsefire 2009-08-18
虽然读起来比较通顺,不过有些地方把意思弄错了。比如第152页"在find(K)之后执行find(I)",原文为"find(I) followed by find(K)",正好弄反了再比如104页“按照顶点的post值的降序,简单地对图顶点执行深度优先搜索即可”...
-
写给自己的算法读书笔记
4有用 0无用 轩雨筱纯爷们儿 2013-12-05
第0章 本章较为简短,没有深入系统地涉及某些内容。主要以Fibonacci数列的例子,让我体会了递归和递推思想的差别。针对Fibonacci数列例子直接递归解法中涉及的重复计算,优化出递推方式,展示了思考问...
书名: Algorithms
作者:
出版社: McGraw-Hill Science/Engineering/Math
出版年: 2006-9-13
页数: 336
定价: $ 60.46
装帧: Paperback
ISBN: 9780073523408