或许你不知道高德纳(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 页的预览版。
在这部分他主要是延伸了第一卷中第一章以及第二章的数学基础,并且加入了他表示在 1960 年代当时的他还不知道的内容。他表示与过去一样,任何首先发现错误以及提出有价值意见的人,他都会寄出奖励。高纳德的奖励是:每指出一个错误,就能得到 2.56 美元,因为 256 美分为 16 进制的 1 美元。这就是高纳德有名的“16 进制奖励”。
此外,高德纳最近还很高兴地宣布,2016 年他在斯坦福的一场讲课,可能是美国大学史上第一场首次用 3D VR LIVE 直播的讲课。
你可以在这段影片中看出,他本人也非常幽默。一开始他就说,这可能是斯坦福有史以来第一场 VR 3D Live 直播讲课,所以他个人觉得应该邀请一些舞者来开场,他也跟在看影片的观众说,如果你想要感受 3D 有多 Cool,或是确认你看的是不是 VR 3D,请你把头低下来。
(Source:影片截图)
你会看到他在 360 度相机下,为大家准备了几本课本。
(Source:影片截图)
虽然画面不是很清楚,不过看起来左边两本是《TAOCP》的日文版、第三本是《TAOCP》英文版,至于第四本……可能是与拼图有关的书,实在看不清楚。
根据高德纳的规划,从他 1992 年退休至今,他实际上只出了第四册 A(而第四册还分成 A、B、C、D 四部!)现在还在努力跟第四册 B 努力奋斗中。而他希望在 2020 年可以完成第五册,看来这个时间表真的拖得有点长。希望今年已 79 岁高龄的大师真的要好好照顾身体,把整套书完成啊!