本书评作者尹一通,豆瓣大神etone,文章首发于豆瓣,见:https://book.douban.com/review/1319514/

谈谈我自己读这套书的心得,抛砖引玉。

首先要清楚这套书的定位:它是古典的算法分析的工具书。   

1. 古典(classic)体现在模型和问题上

模型就是顺序算法(sequential algorithms)的经典模型。大名鼎鼎的MIX并非是个程序设计语言这么简单,而是一个计算模型:即标准指令集RAM。这是个非常经典、也非常符合现实的上界(upper bounds)模型。    该书涉及到的问题是计算机科学诞生之初就自然面对的几个基本的算法和数据结构的问题。时至今日,这些问题还在应用中扮演着重要角色;在很多研究课题中,它们是基础或原型。   

2. 算法分析是此书的核心

TAOCP并没有综述算法设计(design of algorithms)的各种思想;也没有介绍证明问题下界(lower bounds)的各种技巧;也并没有对问题、模型、复杂度这些专题作出体系性的阐述。可以说,TAOCP的几乎所有的篇幅都放在了对具体算法的性能分析上,并把这条路走到了极致。   

3. 工具书

这最有争议,因为毕竟还有习题。一些介绍也饶有趣味,不太符合大家对工具书的“枯燥”成见。

把TAOCP看作工具书还是教材,关系到怎么去读这本书。   

1. 该顺着读还是跳着读?

个人认为,没有哪本专业书是不能跳着读的。但前提是你对整个书的结构比较清楚,对它的内容也一定程度地熟悉。知道自己想要查阅的部分。如果是初学者,则不建议这么做,至少要老老实实把第一章顺序读下来。可是,TAOCP并不是给初学者看的。

2. 初学者适合读TAOCP吗?

不太建议。但也要看如何定义初学者——吾生而有涯,而知也无涯。一定程度上,每个人都是初学者。读 TAOCP的前提,就是自己至少比较清楚轻重缓急,可以大概判断哪些是根本,哪些已过时,哪些是炫技。根据每个人的需要,都有各自的具体情况,但至少心里要有点数。如果读书时觉得前路茫茫,完全不知道哪里重要。那么去正经地选一门算法基础课才是更应该做的。   

3. MIX值得用心学吗?

这要首先清楚Knuth为什么要在这个讲算法的书里搞出个MIX。个人理解,原因有三。其一,如上所述,计算模型;其二,作者个人的审美品味;其三,用于描述算法的语言。第一条里MIX是桥梁作用,确保数学上的严谨,同时也足以代表现实中典型的计算机体系结构。第二条是美学意义。第三条的作用等于伪码。算法用MIX写一遍,这是为了确保上界算法在模型内的严谨性。整个书都没有用MIX模型来证明任何下界,因此除了确保严谨性,MIX没有在数学上起到实际的用途。因此,过分钻研MIX对于理解书中算法没有太多帮助,但如果纯粹只是个人兴趣则另说。   

4. 习题该怎么对待?

TAOCP是为数不多的计算机专著里面能出如此多高水平习题的了。如果有大块时间,能做一做当然最好不过。如果只是一般的查阅,习题并非必要。不过,有的习题本身就是经典问题,如果正文里没有找到想要的东西,不仿看看习题。   

5. 如何读正文里的算法分析?

TAOCP里面的算法分析,算是古典算法分析里面的原教旨主义。始作俑者就是Knuth本人,后面还有 Sedgewick和Flajolet等一干人等给他发扬光大。这一派的作风可以说分毫必究,连常数都不放过。但数学工具却无外乎初等的《具体数学》的工具。这是很好很强大的东西,掌握好了,无论研究还是工作都很方便。但其实TAOCP的数学都不算太难,仔细倒是真的。因此,如果时间不是特别充裕,对书中结构的了解,要比具体分析步骤重要。这些经典内容多少年就没变过,每次有用时都可以回来查查看,每查一次说不定会有新的收获。   

6. TAOCP的不足。

前面已经提过了,下界介绍得不够。下界结果,大多数只在章节结束的讨论部分引用一下。卷3的查找(searching)一章,一些近些年的下界方面的新进展都没有被引用,Knuth可能没有想到,数据结构这个经典方向这么多年来都在不温不火地前进着,尤其是下界。类似的也有卷2的随机数(random numbers)一章,可以说连上界都过时,错过了去随机(derandomization)的黄金时代。好在其他章节这么多年来无甚进展,没怎么过时。

许多人对TAOCP的推崇是无条件的,其中难免有人云亦云的成分。其实大可不必,读的人尽管放轻松。这么说不是因为TAOCP不值得推崇,而是就算把一切溢美之词都抛于脑后,随着岁月流逝,反复地阅读,你也一定会越来越喜欢这部书。它的魅力经得起时间考验。

书评作者

尹一通
南京大学计算机科学与技术系副教授。2009年博士毕业于耶鲁大学,获得计算机科学PhD。同年回到本科母校南京大学任教。尹一通的研究方向是理论计算机科学(Theoretical Computer Science),具体研究兴趣包括随机算法、数据结构复杂性等。在理论计算机科学高水平国际会议FOCS/SODA/ICALP发表十余篇论文。在南京大学开设《随机算法》《组合数学》两门课程,自2013年以来为上海交通大学致远计划ACM班开设《概率与计算》暑期课程。在博士求学期间,尹一通以etone为笔名在豆瓣网站发表了一系列计算机专业书评。

更多参考观点

关于更多国内外高手针对“TAOCP是否值得阅读以及如何阅读”的观点请参考【如何阅读《计算机程序设计艺术》】