高德纳传奇

号称计算机领域经典必读的著作你都读过哪些，例如《计算机程序设计艺术》系列？近日，这套书的作者高德纳（Donald Knuth）在接受纽约时报采访时，谈到了自己对于这部已投入五十载心血作品的反思。

自幼便显露非凡智力的算法大师高德纳，是美国著名计算机科学家、斯坦福大学电脑系荣誉教授，36  岁便凭借未完的《计算机程序设计艺术》捧走图灵碗，曾是最年轻的图灵奖获得者。他被誉为现代计算机科学的鼻祖、算法领域的精神导师，在计算机科学及数学领域发表了多部影响力深远的论文和著作，同时还是  TeX 和 Metafont 排版系统的发明人，更与 Edsger Wybe Dijkstra  并称为我们这个时代最伟大的计算机科学家。除了写书，高德纳同时还是一位音乐家、作曲家、管风琴设计师……

作为一个不折不扣的完美主义者，高德纳近乎偏执地对自己提出了严苛的要求——精益求精的作品、严密的时间安排，乃至文学层面的追求，甚至曾以排版工具太差破作品之美为由宣布歇笔。这也导致《计算机程序设计艺术》的下一册迟迟“难产”，已然拖过了原定计划中的“圣诞”之期。关于完结，更是预留了未来二十五年。如今已是  80 高龄的他，继续玩技术、玩音乐、玩游戏、写小说——做一切“快乐”的事。

最后，套用一句高德纳自传开头的话：“Donald Knuth 真的仅仅是一个人吗？”

以下为译文：

近乎偏执的完美主义者

半个世纪以来，斯坦福大学的计算机科学家 Donald Knuth 已然成为算法领域的精神领袖。说起他的外貌，倒是与星球大战中的尤达颇有几分相似，只不过他身高 6 英尺 4 英寸（约 1.93 米），还戴了副眼镜。

Donald Knuth 在加利福尼亚州斯坦福的家中 | 图片来源：纽约时报Brian Flaherty
他是个众所周知的极端完美主义者，甚至愿意为任何指出他的书中错误的人支付报酬。

他是《The Art of Computer  Programming》（中译本《计算机程序设计艺术》）一书的作者，该书共有四卷，也是他一生的杰作。第一卷首发于 1968 年，2013  年该合集（售价约为 250 美元）被《美国科学家（American Scientist）》杂志评选为 20  世纪最重要的科学类专著，一起被入选该书单的还包括《The Autobiography of Charles  Darwin》（达尔文自传）的特别版、汤姆·沃尔夫的《太空英雄》（The Right Stuff）、雷切尔卡逊的《寂静的春天》（Silent  Spring）以及阿尔伯特·爱因斯坦、约翰·冯·诺伊曼和理查德·费曼的专著。

《计算机程序设计艺术》出版了一百多万册，是计算机领域的圣经。Google 的研究主管 Peter Norvig  曾评论称：“这本书就像一本真正的圣经，内容很长而且很全面，其他书籍都无法比拟。”该书的第一卷一共有 652  页，书的后封面上还印有比尔·盖茨的推荐语：“如果你能够看懂这本书的所有内容，那么欢迎给我发来简历。”

《计算机程序设计艺术》1-4 卷 | 图片来源：纽约时报 CreditBrian Flaherty

第一卷开头有一段摘录自《McCall's Cookbook》的话：

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

这本书讲的是数字时代的基石——算法，尽管 Knuth 博士认为算法早在 3800 年前就诞生于巴比伦的石板上。Knuth  是一位受人尊敬的算法专家，他的名字与该领域一些最重要的发展息息相关，例如 Knuth-Morris-Pratt 字符串搜索算法。该算法设计于  1970 年，它可以在文本中查找所有给定的单词或任何字母组合——例如，在你按下 Command + F  的时候来查找文档中的关键字时，采用的就是这种算法。

如今，Knuth 博士已然 80 岁高龄了，但工作时的他每每穿得像个年轻的极客：长袖 T 恤外套一件短袖 T 恤，再配上条牛仔裤，每年这个时候他都是这种打扮。早些年，他总是和机器打交道，写一些原始的二进制代码。

Norvig 博士说：“Knuth  证明了，整个计算机系统，一直到机器代码级别的所有内容都是可理解的。”当然，随着现在算法越来越深入日常的方方面面，普通程序员不再有时间去“摆弄”那些二进制的东西，而是整天与各种抽象的层次结构和一层又一层的代码打交道，经常要把从各个代码库中拿来的代码串在一起。但是，真正优秀的工程师偶尔还是会深入研究底层代码。

在加利福尼亚州山景城举行的 Google Trips 团队会议上，Norvig 博士说：“在  Google，有时我们只是把东西整合在一起，但是更多时候，如果你为数十亿用户提供服务，那么效率就很重要了。效率提高 10%  就可以创造数十亿美元的价值，为了获得足够高的效率，你必须了解底层的工作原理。”

Knuth 博士在加州理工学院
他于 1963 年获得了该校的博士学位，图片来源：Jill Knuth

Andrei Broder 是 Google 杰出的科学家，也曾是 Knuth  博士的研究生，他在会议期间表示：“我们希望为我们正在做的事情提供一些理论基础依据。我们不希望我们的算法变得轻浮、草率或二流。我们不希望其他算法主义者说，‘你们这些家伙是白痴’”。

Google Trips 是一款创建于 2016  年的应用，它采用了“定向算法”，用于绘制一天的推荐旅游活动。该团队正致力于“最大限度地提高某一次旅行活动的质量”（https://ai.google/research/pubs/pub46479），例如避免仅仅因为景点不同就将用户反复送到同一地区。他们从瑞士数学家莱昂哈德·欧拉（Leonhard  Euler） 300  年前提出的算法中汲取灵感。欧拉希望绘制一条穿越普鲁士城市柯尼斯堡的路线，并保证这条路线只穿过科尼斯堡的七座桥各一次。Knuth  博士在其论文的第一卷中论述了欧拉的经典问题。 （他曾经将欧拉方法编写了一套用于控制缝纫机的计算机程序）。

遵循 Knuth 博士的学说有助于避免代码的堆砌。众所周知，他引入了“文学编程（literate  programming）”的概念，强调编写人类和计算机皆可阅读的代码的重要性， 尽管如今这个概念看起来似乎有点过于感性。Knuth  博士甚至认为，有些计算机程序就像伊丽莎白·毕晓普的诗歌和菲利普·罗斯的《美国牧歌》一样，其可读性可以与普利策文学奖作品相媲美。

同时，Knuth 博士也是一位不折不扣的完美主义者。xkcd 漫画家、《万物解释者》（Thing Explainer）的作者  Randall Munroe 第一次听说 Knuth 博士，还是听其他计算机科学人士提及 Knuth  博士愿意给那些从他的书中发现错误的人支付奖金。Munroe 回忆道，“人们看这笔奖金就像看计算机科学界的诺贝尔奖一样。”

Knuth 博士严格的标准以及在文学等方面的追求，也恰恰说明了为什么他倾注毕生心血的这一作品的完成依然遥遥无期。他曾与 Google  联合创始人谢尔盖·布林（广义上来讲布林也是他之前的学生）打赌，看布林是否可以在 Knuth 博士完成他的作品之前获得博士学位。

算法的曙光

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

1981 年，Knuth 博士正在读 1957 年出版的《疯狂》杂志，里面有他发表的第一篇技术论文，发表这篇论文时他年仅 19 岁。图片来源：Jill Knuth

Knuth  博士利用暑假期间编写编译器赚的钱比当教授一年挣的还多。编译器就像一个翻译器，将高级编程语言（类似于代数）转换为低级编程语言（有时是神秘的二进制），在理想情况下还可以在此过程中对程序本身进行改进。在计算机科学中，“优化”是一门艺术，这一点可以从另一句  Knuth 式的名言中看出来：“过早优化乃万恶之源。”

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

谈及“算法”一词，Knuth 博士表示：“文艺复兴时期，人们开始怀疑算法这个词的起源。早期的语言学家试图猜测这个词的起源，认为它是从  algiros [痛苦] + arithmos [数字] 派生出来的词汇。事实上，这个名词起源于九世纪的教科书作者，波斯人 Abū ‘Abd  Allāh Muhammad ibn Mūsā al-Khwārizmī（拉丁语名字是 Algorithmi）”。1979  年，不达目的誓不罢休的 Knuth 博士更是专程前往乌兹别克斯坦，到 al-Khwārizmī’s 的故乡朝圣。

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

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

Knuth 博士通常在周五上午约见学生，但后来他把会见时间改到了晚上，因为他可以利用这漫漫长夜在人工智能学科创始人 John  McCarthy 的实验室中使用空闲的计算机。随着数字出版业务的推行，Knuth 博士对其心血的最终呈现效果甚是不满，转而创立 TeX  计算机排版系统，直到现在，该系统仍然是所有科学出版物的黄金标准。有人认为这是 Knuth  博士对世界的最大贡献，也是自古腾堡（Gutenberg，德国活版印刷发明人）以来人类对印刷术贡献最大的人。

这项任务花了他十年的时间，彼时还处于用户共享计算机的时代，而在大多数人都在睡觉的夜晚，计算机跑得更快。因此，Knuth  博士改成了夜间工作，将日程安排调整了 12 个小时，开始了日夜颠倒的生活，并将与学生的约见改为周五晚上 8 点到午夜。Broder  博士回忆称：“当我告诉我的女朋友周五晚上我没空，因为周五晚上 10 点我必须和我的导师见面时，她接连感叹‘不可思议、难以理解’。”

然而，当 Knuth 出现时，他一定会百分之百的投入。微软研究院的一名总监 Jennifer Chayes  说：“和他在一起你会很愉快。他是社区中的佼佼者，你可曾幻想过如果优化功能（optimization  function）也可以兼具温暖和深度该多好。那么 Knuth 就是让这一设想成真的人。”

Knuth 与字体设计师 Hermann Zapf 讨论字体。许多人认为 Knuth 博士在 TeX 电脑排版系统上的工作是自古腾堡以来人类对印刷术最大的贡献。图片来源：Getty Images/ Bettmann

周日拜访小记

Knuth 博士住在斯坦福，他同意我们在周日拜访他。他为此花费了一整天的时间，这很不寻常——通常他的空闲时间只有下午 1 点到 4  点的“modulo nap time”时段，就像他每天的神圣仪式一样。周末他会很早就起床，去 往 Palo Alto  的第一路德教堂，并在这里上一节课，课上挤满了站立的人群。在开车回家的途中，他会对数学进行一些哲学上的思考。

1999 年，Knuth 博士在家办公 | 图片来源：Jill Knuth

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

一些笔记 | 图片来源：纽约时报Brian Flaherty

拼图和游戏、写一本关于超实数的小说、创作一部 90  分钟的多媒体音乐白日梦《幻想曲启示录》等——这些都是他真正感兴趣的东西。他的书有一部分名为“谜题与真实世界”。他通过电子邮件将摘录发送给了艺术家  Martin Demaine 和计算机科学家 Erik Demaine（他俩是父子，都在麻省理工学院），因为 Knuth  博士用到了他们的“算法解谜字体”（algorithmic puzzle fonts）。

对此，Erik Demaine 表示：“我很激动，能出现在这本书中是一种荣幸。”他提到了 Knuth 的另一句名言（这句鼓舞人心的话是两年一度的“算法的乐趣”会议的座右铭）：“快乐也许是一直以来的主要目标。”

但 Demaine 博士还表示，“这个领域追求实际应用。工程师、科学家和艺术家正在联手解决现实问题，比如蛋白质折叠、机器人技术、安全气囊等，他们使用 Demaines 的数学折纸设计方法来将纸片和连杆折叠成不同的形状。”

当然，所有算法的繁琐性都会导致现实问题。人类编写的算法虽然可以解决越来越难的问题，但也产生了带有 bug 和偏见的代码，这些已经够麻烦了。更令人担忧的也许是并非人类编写的算法，而是机器通过学习后编写的算法。

程序员仍在训练机器，而且关键在于过程中向机器输入的数据（数据是偏见和bug的新领域，而且该领域中的 bug  和偏见更难被发现和修正）。然而，正如麻省理工学院媒体实验室研究员 Kevin Slavin  所言：“我们现在正在编写一些连自己都看不懂的算法。这是一个独一无二的时代，因为我们受到一系列物理学的思想、行动和努力的影响，这些物理学源于人类，但人类却无法理解。”正如  Slavin 常说的那样，”如果你是一个算法，那你将拥有光明的未来（It's a bright future, if you're an  algorithm.）。“

“如果你是一个精通 Knuth 算法的人，那么你的未来将更加光明。”Norvig 博士补充道，“如今，程序员使用 Knuth 和其他人已经完成的内容作为他们算法的组成部分，然后把这些内容与他们需要的其他内容相结合。”

“AI 也是一样，只是这些组合将会基于数据自动完成，而不是由程序员来完成。你希望 AI  能够根据数据将之前的内容组合起来，并得到良好的结果。但是你必须决定这些内容是什么。可能所有内容都出自 Knuth  作品的某一页或某一章节，因为这是完成某些任务的最佳方式。”

幸运的是，Knuth 博士仍在坚持不懈地努力。他觉得还需要25年时间才能完成《计算机程序设计艺术》，尽管自 1980 年以来他就一直在做这件事。那么会不会有一章，或者有一页会讨论到会写算法的算法？Knuth博士对于这一点的答案是：“肯定不会！”

他解释道：“我担心算法变得太过重要。最初计算机科学家担心没有人听我们说话。但现在，我担心听我们话的人太多了。 ”

原文：https://www.nytimes.com/2018/12/17/science/donald-knuth-computers-algorithms-programming.html

本文转自：数学与人工智能