TAOCP-box-624x463

或许你不知道高德纳(Donald Ervin Knuth)是谁,甚至可能没有读过他的著作,但是事实上任何资工科系的学生,现在学校里所念的课本,内容多少都是他的著作翻译以及翻译的再翻译;甚至可以说,整个计算机史如果没有他,可能现在的演算法走向就会完全不一样。

高德纳,斯坦福大学的计算机系荣誉退休教授,是现代计算机科学及现代数学的大师级人物,尤其在演算法领域可说为后人奠定了基础。现代学习演算法中有一个字串搜索演算法“Knuth–Morris–Pratt”,就是他与学生的合作发明。

他早在 1962 年还是研究生时就已经从事程序设计,而他攻读博士学位的时候,就有人找他撰写程序设计相关的书籍,但当时他课业繁忙,一直到 1968 年,才开始出版著作,也就是至今被程序设计史上列为经典的《计算机程序设计艺术》(The Art of Computer Programming)。

《TAOCP》被美国科学家期刊列为与相对论、博奕论、量子力学等重量级学术作品并驾齐驱的科学史上最重要著作,李开复也说过,要把资料结构、演算法、数据库、操作系统原理、离散数学等基础课程学好,就去练习 TAOCP 里的题目。甚至比尔·盖兹 1995 年的时候还建议新鲜人“如果你能读懂整套书,请发给我你的履历。”

《TAOCP》一书的出版过程也是计算机书籍出版史上的一个传奇,前面说在 1962 年就有出版社跟他约稿,当时他回答课业繁忙,4 年之后出版社问他书写得怎么样,他回答“才写了三千多页……”让编辑大吃一惊,他们只想要出一本计算机基础书,但是高纳德把这本书的规格提高到前所未有的高度。

而这三千多页的内容,仅仅只是整套《TAOCP》的一章。

而从 1968 年到 1973 年,这本书出到了第三部,在这期间他已经是斯坦福大学的教授,而这三部书也被计算机界视为经典之作。1974 年他才 36 岁,就以这套书获得美国计算机界最高成就的图灵奖,为至今最年轻的获奖者。不过,就在这时候,他宣布要暂时停笔,不写了。理由是当时的“排版工具太烂,无法表现书中的演算法之美”。

于是,接下来的 10 年,他花时间设计了一套论文排版系统 TEX,这个系统专门针对适合学术写作和数学式的排版设计;并且设计了一个字体设计系统 METAFONT。值得一提的是,高纳德的想法处处与众不同,TEX 的版本开发并不像一般 Windows 2.0、3.0 这样一路往上累进,而是使用圆周率来当版本开发的代号,TEX3、TEX3.1、TEX3.14……这样一路往下,不断逼近圆周率以趋近完美。

到了 1992 年,高德纳宣布从斯坦福大学退休,并且从此不收 Email,理由是希望专心完成整套《TAOCP》。整套《TAOCP》预计共有七册,每册主题如下:

  • 第一册基础演算法(Fundamental Algorithms)

第一章基本观念(Basic concepts)

第二章资讯结构(Information structures)

  • 第二册半数值演算法(Seminumerical Algorithms)

第三章随机数(Random numbers)

第四章算数(Arithmetic)

  • 第三册排序与搜索(Sorting and Searching)

第五章排序(Sorting)

第六章搜索(Searching)

  • 第四册组合演算法(Combinatorial Algorithms),准备中(至 2009 年 4 月已出版 5 个分册),测试版本已上载到 Knuth’s 的网站)

第 4A 卷列举与回溯(Enumeration and Backtracking)

第七章组合的搜索(Combinatorial searching)

第 4B 卷图形与网络演算法(Graph and Network Algorithms)

第七章续(continued)

第 4C 及 4D(可能)卷最佳化与递回(Optimization and Recursion)

第七章续(continued)

第八章递归(Recursion)

  • 第五册造句演算法(Syntactic Algorithms),计划中(预计 2020 年完成)

第九章语句扫瞄(Lexical scanning)

第十章剖析技术(Parsing techniques)

  • 第六册与上下文无关语言理论(Theory of Context-Free Languages),计划中
  • 第七册编译器技术(Compiler Techniques),计划中

就跟许多不按牌理出牌的大师一样,高德纳的兴趣很广,从音乐到小说艺术都有。但他最爱的还是程序设计的艺术,以及“做到完美”的信念。

最近高德纳在他的网站上发布了他最近的写作进度,并且披露了最近写到 4B 的部分内容,提供了 52 页的预览版

T客邦配图

在这部分他主要是延伸了第一卷中第一章以及第二章的数学基础,并且加入了他表示在 1960 年代当时的他还不知道的内容。他表示与过去一样,任何首先发现错误以及提出有价值意见的人,他都会寄出奖励。高纳德的奖励是:每指出一个错误,就能得到 2.56 美元,因为 256 美分为 16 进制的 1 美元。这就是高纳德有名的“16 进制奖励”。

此外,高德纳最近还很高兴地宣布,2016 年他在斯坦福的一场讲课,可能是美国大学史上第一场首次用 3D VR LIVE 直播的讲课。

你可以在这段影片中看出,他本人也非常幽默。一开始他就说,这可能是斯坦福有史以来第一场 VR 3D Live 直播讲课,所以他个人觉得应该邀请一些舞者来开场,他也跟在看影片的观众说,如果你想要感受 3D 有多 Cool,或是确认你看的是不是 VR 3D,请你把头低下来。

影片截图 T 克邦配图

(Source:影片截图)

你会看到他在 360 度相机下,为大家准备了几本课本。影片截图

(Source:影片截图)

虽然画面不是很清楚,不过看起来左边两本是《TAOCP》的日文版、第三本是《TAOCP》英文版,至于第四本……可能是与拼图有关的书,实在看不清楚。

根据高德纳的规划,从他 1992 年退休至今,他实际上只出了第四册 A(而第四册还分成 A、B、C、D 四部!)现在还在努力跟第四册 B 努力奋斗中。而他希望在 2020 年可以完成第五册,看来这个时间表真的拖得有点长。希望今年已 79 岁高龄的大师真的要好好照顾身体,把整套书完成啊!

19 2 收藏


直接登录

推荐关注