纽约时报长文：硅谷的尤达—算法大师Donald Knuth

2019 年 2 月 18 日 算法与数学之美

Donald Knuth，著名计算机科学家，誉满全球的图灵奖获得者，斯坦福大学计算机系荣誉退休教授。作为现代计算机科学的先驱人物，他发明了计算机排版系统 TEX 和 METAFONT，创造了算法分析的领域，在计算机科学及数学领域发表了多部具广泛影响的论文和著作。日前，纽约时报对他进行了一次专访。在这次访谈中，Knuth 博士谈到了他对算法的一些看法，反思了他 50 年来的作品《The Art of Computer Programming》，并表示：“我担心算法变得太过重要。一开始，我们这些计算机科学家担心没有人听我们的，但现在，听我们的人太多了。”

Donald Knuth 在加利福尼亚州斯坦福的家中。他是个臭名昭著的完美主义者，愿意对任何在他的书中发现错误的人给予奖励。

斯坦福大学的计算机科学家 Donald Knuth 与《星球大战》中的尤达略有相似，半个世纪以来，他一直是算法领域的精神导师——尽管他身高 6 尺 4 英寸（约 1 米93），戴着眼镜。

他是《The Art of Computer Programming》一书的作者，这部作品是他的终生工作，共有四卷。第一卷于 1968 年出版，这卷书籍（盒装出售，售价约 250 美元）2013 年被 American Scientist 杂志评选为塑造上世纪科学的书籍，一起被列入的书籍包括《The Autobiography of Charles Darwin》特别版、Tom Wolfe 的《The Right Stuff》、Rachel Carson 的《Silent Spring》以及 Albert Einstein、John von Neumann 和 Richard Feynman 的专著。

《The Art of Computer Programming》出版了一百多万册，是计算机领域的圣经。谷歌研究主管 Peter Norvig 曾说过：“这本书就像一本真正的圣经，它很长，也很全面，没有一本书能像它那样全面。”翻过 652 页，第一卷结束，可以看到后封面上比尔·盖茨的推荐语：“如果你能读懂全部内容，一定要给我发份简历。”

本书开头摘录自《McCall’s Cookbook》：

你们写了上千封信要求我们出版的那本书来啦。我们花了很多年的时间反复检查书里面那些数不尽的食谱，只为给您带来最好的、有趣的、完美的内容。

这本书主要讲算法，尽管 Knuth 博士指出，在 3800 年前的巴比伦刻写板上也能找到算法，但这本书能满足数字时代的需求。Knuth 是一位受人尊敬的算法专家；他的名字与该领域一些最重要的方法关联在一起，例如 Knuth-Morris-Pratt 字符串搜索算法。这个算法是在 1970 年设计的，它可以在文本中查找给定单词或字母的所有匹配内容——例如，当你点击 Command + F 在文档中搜索关键字时采用的就是这种算法。

工作时，现年 80 岁的 Knuth 博士通常穿得像个年轻的极客：上身长袖T恤，外面套件短袖T恤，下身牛仔裤，他在每年这个时候都是这种打扮。在早些年，他总是和机器打交道，写一些原始的二进制编码。

Norvig 博士说：“Knuth 证明了计算机系统实际上可以一直被理解到二进制编码级别。”但如今，随着算法对二进制编码的主宰（和破坏），普通程序员不再有时间去处理那些二进制“垃圾”，而是使用抽象的层次结构和一层又一层的代码，并且还经常使用从代码库找来的一连串代码。但是精英阶层的工程师偶尔还是会深入研究底层代码。

Norvig 博士在加利福尼亚州山景城的一次 Google 旅行小组会议上说：“在 Google，有时我们只是把东西整合在一起，但是更多时候，比如你正在为数十亿用户提供服务，高效很重要。效率提高 10% 就可以创造数十亿美元的价值，为了获得足够高的效率，你必须明白到底发生了什么。”

1963年，加利福尼亚理工学院，在这里Knuth获得博士学位

或许正如 Google 著名科学家 Andrei Broder 和 Knuth 博士以前的一个研究生在会议中所说的那样：“我们想为我们正在做的事情提供一些理论基础。我们不需要轻浮的、草率的或二流的算法。我们不希望其他的算法工程师说，‘你们这些家伙是白痴’”。

Google Trips 应用程序创建于 2016 年，采用了“定向运动算法”，用于绘制一天的推荐旅游活动。该团队正在致力于“最大限度地让一天看起来不那么糟糕”，例如，避免将用户反复送到同一地区，只是因为看的景点不同。他们从 300 年前的瑞士数学家莱昂哈德.欧拉的算法中得到灵感，欧拉想绘制一条穿越普鲁士城市科尼斯堡的路线，这条路线只穿过科尼斯堡的七座桥各一次。Knuth 博士在他的书的第一卷中阐述了欧拉的经典问题（他曾经将欧拉方法用于控制缝纫机的计算机编码）。

遵循 Knuth 博士的教义有助于避免代码的堆砌。众所周知，他引入了“编码可读性”的概念，强调代码对于人类和计算机都具有好的可读性的重要性，如今这个概念已经成为了共识。Knuth 博士甚至认为，一些计算机程序就像伊丽莎白·毕晓普的诗歌和菲利普·罗斯的《美国牧歌》一样，可读性和普利策文学奖作品并无二致。

他也是一位臭名昭著的完美主义者。xkcd 漫画家、《事物解释者》的作者 Randall Munroe 第一次听说 Knuth 博士，还是别人提到 Knuth 博士会提供奖金给任何在他的书中发现错误的人。Knuth 回忆道，“他们说得到 Knuth 博士的奖金就像获得计算机科学界的诺贝尔奖。”

Knuth 博士具有对自己要求严格、博学等诸多特质，这些特质也解释了为什么他这本书的完成遥遥无期。他和 Google 的联合创始人谢尔盖·布林打赌，布林是否会在他结束自己的作品之前获得博士学位。

算法的曙光

19 岁时，Knuth 博士在《疯狂》杂志上发表了他的第一篇技术论文《The Potrzebie System of Weights and Measures》。在计算机科学这门学科存在之前，他就成为了一名计算机科学家，在克利夫兰的一所学校学习数学，这所学校就是如今的 Case Western Reserve University。他看了学校的 IBM 650 大型机（一台十进制计算机）的示例程序，发现了一些不足之处，就重写了该软件和在课堂上使用的教科书。作为一项辅助项目，他编写计算机程序来执行统计数据，帮助篮球队赢得联赛冠军。

在暑假期间，Knuth 博士编写编译器赚的钱比当教授一年挣的还多。编译器就像一个翻译器，将高级编程语言（类似于代数）转换为低级编程语言（有时是神秘的二进制），并在转换过程中对其改进。在计算机科学中，“优化”确实是一门艺术，Knuthian 有一句名言：“过早的优化是万恶之源。”

最终，Knuth 博士自己成为了“编译器”，他无意中开辟了一个新的领域，并称之为“算法分析”，有个出版商委托他写一本关于编译器的书，这本书最后成为一本他所知道的所有计算机编程方法的集合，成为了一本关于算法的书。

摄于 1981 年，Knuth 正在看 1957 年出版的《疯狂》杂志，这本杂志里有他发表的第一篇技术论文，发表这篇论文的时候他才 19 岁。

《The Art of Computer Programming》1-4卷。比尔·盖茨在推荐语中写道：“如果你能读懂全部内容，一定要给我发份简历。”

“文艺复兴时期，人们开始怀疑算法这个词的起源。” Knuth 博士说道，“早期的语言学家试图通过组合像 algiros [痛苦] + arithmos [数字] 这些词来猜测它的起源。”“事实上，”，Knuth 博士继续说，“在 9 世纪波斯教科书作者 Abū ‘Abd Allāh Muhammad ibn Mūsā al-Khwārizmī 的书中就有这个词的拉丁语。”。1979 年，Knuth 博士去了乌兹别克斯坦，到 al-Khwārizmī’s 的故乡朝圣。

当 Knuth 博士刚开始写作时，他没打算写得这么复杂。不久之后，计算机科学经历大爆炸，所以他重新构思了这部作品并重铸成七卷。现在，他开始分册，把它们分成一系列丛书。接下来要写的是系列 5 的第 4 卷，包含 “backtracking” 和 “dancing links” 算法，原计划出版的时间为圣诞节，但它被推迟到第二年四月出版，因为 Knuth 博士不断发现越来越多有意思的问题，他想把这些问题写进书中。

为了尽早完成这本书，Knuth 博士一直惜时如金。他 55 岁退休，极少参加公众活动，并停止使用电子邮件（至少停止了因公电子邮件）。Andrei Broder 回忆说，即使是在 20 世纪 80 年代早期，Knuth 对时间也管理得非常严格。

Knuth 博士通常在周五上午约见学生，在这之后他便在人工智能学科创始人 John McCarthy 的实验室度过夜晚，在这里他可以使用空闲的计算机。随着数字出版的出现，Knuth 博士对他心爱的书在书页上的样子感到不满，他承担了创建 TeX 计算机排版系统的任务，现在这一系统仍然是所有科学出版物的形式的黄金标准。有些人认为这是 Knuth 博士对世界最大的贡献，也是自 Gutenberg 以来人类对印刷术最大的贡献。

这条长达十年的迂回之路发生在用户之间共享计算机的时代，那时，在大多数人都睡觉的晚上，计算机跑得更快。因此，Knuth 博士的作息开始日夜颠倒，他把作息时间调整了 12 个小时，并将约见学生的时间改为周五晚上 8 点到午夜。Broder 博士回忆说：“当我告诉我的女朋友周五晚上不能做任何事情，因为周五晚上 10 点，我必须和我的导师见面时，她想，‘这件事太愚蠢了，真的是太愚蠢。’

当 Knuth 出现时，他一定会 100% 投入到当前的事情中。微软研究院董事总经理Jennifer Chayes 说：“和他在一起你会很高兴。”“他在社区里是最棒的。如果说有个人在某种程度上既温暖又有深度，那这个人就是 Don。”

Knuth 与字体设计师 Hermann Zapf 讨论字样。许多人认为 Knuth 博士在 TeX 电脑排版系统上的工作，是自 Gutenberg.CreditBettmann的Getty Images 以来对排版最大的贡献。

拜访 Knuth 的星期天

Knuth 住在斯坦福，允许周日来访。他这一天的时间很独特，通常他的空闲时间是从下午 1 点到到 4 点（称为 “modulo nap time” ），他会进行一场神圣的每日仪式。他很早就起床，去帕洛阿尔托的第一路德教堂，在这里他给人们上一门“Sunday” 学校课程。在开车回家时，他会对数学进行一些哲学上的思考。

“我永远不可能全都知道，”他说，“如果我对问题的答案一无所知，或者我什么都知道，生活将会糟糕得多。”然后他带我们参观了他加州现代风格的房子，这所房子是他和他的妻子 Jill 在 1970 年建造的，Jill 是一名平面设计师。他的办公室里乱七八糟地堆放着成堆的 USB 线，还装饰着 Jill 设计的情人节心形艺术品。最令人印象深刻的是音乐厅，环绕着他定制的 812 管风琴。在这天的最后，我们开了一场益智派对，并喝了啤酒。

拼图和游戏，写一本关于超现实数的中篇小说，写一部 90 分钟的多媒体音乐白日梦——“幻想启示录”，这些都是他真正感兴趣的东西。他的书有一部分名为“谜题与真实世界”。他把这里的一段发给了艺术家 Martin Demaine 和计算机科学家 Erik Demaine，因为他用到了他们的“algorithmic puzzle fonts”。他们是俩父子，都在麻省理工学院。

“我很激动，”Erik Demaine 说。“能出现在这本书里面真是荣幸。”他提到了 Knuth的另一句名言，这句鼓舞人心的话是两年一度的 “FUN with Algorithms” 会议的座右铭：“快乐也许是一直以来的主要目标。”

“但是后来，” Demaine 博士说，“这个领域崛起并且追求实际应用。”工程师、科学家和艺术家们正在联合起来解决现实世界的问题，如蛋白质折叠、机器人技术、安全气囊等问题，他们使用 Demaine 父子的数学折纸设计方法来将纸片和连杆折叠成不同的形状。

当然，算法繁琐性会导致现实问题。人类编写的算法正解决着越来越难的问题，但是会出现存在错误和偏见的代码，这些已经足够麻烦了。更令人担忧的也许是那些不是由人类编写的算法，即机器通过学习后编写的算法。

程序员仍然训练机器，关键是，他们会给机器输入数据。（数据是偏见和错误的新领域，并且这里的错误和偏见更难被发现和修正）。然而，正如麻省理工学院媒体实验室研究员 Kevin Slavin 所说：“我们现在正在编一些自己看不懂的算法。这是一个独一无二的时代，我们受制于那些源于我们，但是我们并不理解的思想、行动所支配。”正如 Slavin在TED 中提到的那句话，“如果你是一个算法，那你将有光明的未来。（“It’s a bright future, if you’re an algorithm.”）”

1999 年，Knuth 博士在家办公