阅读 590

《计算机程序设计艺术》作者高德纳

原文作者:Siobhan Roberts

译者:UC 国际研发 Jothy

写在最前:欢迎你来到“UC国际技术”公众号,我们将为大家提供与客户端、服务端、算法、测试、数据、前端等相关的高质量技术文章,不限于原创与翻译。

编者按:英文原文发表于时代周刊,并非完全计算机领域内容,由于译者水平有限,所以有很多地方理解不当之处,还请指正。


提起算法大师高德纳(Donald Knuth),不得不提他这 50 年来的鸿篇巨制——《计算机程序设计艺术》。

半个世纪以来,斯坦福大学计算机科学高德纳已然成为算法领域的精神指南,他与 Yoda(译者注:《星战》中的尤达大师)略有相似之处 - 虽然他身高 6 英尺 4 英寸,戴着眼镜。

他是“计算机程序设计艺术”的作者,这是一部连续四卷的作品,是他一生的成就。第一卷于 1968 年首次亮相,全卷(以盒装价格约 $250 出售)被 《美国科学家》杂志(American Scientist)2013 版 列入「塑造上个世纪科学的书单」 - 与之比肩而立的是《查尔斯达尔文自传》的特别版,汤姆沃尔夫的《The Right Stuff》,雷切尔卡森的《寂静的春天》和爱因斯坦,冯诺伊曼和理查德费曼等人的著作。

《计算机程序设计艺术》发行超过一百万册,被称为计算机领域的圣经。“就像一本真实的圣经,它漫长而又全面; 没有任何书能如此全面,“谷歌研究院主管彼得诺维格说。652 页之后,第一卷封底以比尔盖茨的评介结束:“如果你能读完此书,你绝对得给我发份简历。”

该卷开篇摘录自《麦考尔的烹饪书》:

这是应你们的数千封信要求而出版的书。我们为其倾注了多年的心血,检查再重新检查无数次,只求为您带来最好、最有趣、最完美的食谱。

书籍内部是算法,它们可以满足数字时代的需求 - 尽管正如高德纳博士所说,算法也可以在 3800 年前的巴比伦片上找到。他是一位备受尊敬的算法主义者,他的名字伴随该领域最重要的作品出现,例如 Knuth-Morris-Pratt 字符串搜索算法。该算法于 1970 年设计,能在文本中找到所有出现的给定单词或字母模式 - 例如,当你按下 Command+F 搜索文档中的关键字时。

高德纳博士现年 80 岁,他总是打扮得像个年轻的极客,正如他踏上漫长探索之旅时一样:上身穿着长袖 T 恤内搭短袖 T 恤,下身搭配牛仔裤,至少在每年的这个时候。早些年,他还使用计算机工作,写着“原始的”代码,玩转着 0 和 1。

“Knuth 明确表示,实际上计算机系统(内部)一直到机器码级别都是可被理解的,”Norvig 博士说。当然,现在随着算法对它的策划(及破坏),普通程序员不再有时间操纵二进制代码,而是使用抽象层次结构,逐层往上的代码结构 - 并且通常使用代码库中的代码链。即便是精英级的工程师偶尔也会深陷其中。

“在谷歌,有时候我们做的,只是把东西放在一起,”Norvig 博士在加利福尼亚州山景城举行的 Google Trips 团队会议上说。“但其他时候,如果你为数十亿用户提供服务,那么高效就显得非常重要。 10% 的效率提升能带来数十亿美元的效益,为了达到最终的效率,你必须明白其中到底发生了什么。”

1963 年,高德纳博士在加州理工学院获得博士学位 | Jill Knuth

或者,正如 Andrei Broder(谷歌杰出科学家,高德纳博士的前研究生)在会上所说:“我们希望为我们正在做的事情提供一些理论依据。我们要的不是轻浮草率甚至二流的算法。我们不想听见其他算法专家说'你们太蠢了'“。

创建于 2016 年的 Google Trips 应用使用了“定向越野算法(orienteering algorithm)”,它可以推荐出适合某天的旅游活动。该团队正致力于“最大限度地提高最糟糕的一天的质量” - 例如,避免将用户送回同一社区,而是让他查看不同的地点。他们从 300 年前瑞士数学家莱昂哈德·欧拉(Leonhard Euler)发明的算法中汲取灵感,欧拉希望绘制一条通过普鲁士城柯尼斯堡(Königsberg)的路线,并满足一次性穿过城中的七座桥。高德纳博士在他论文的第一卷中论述了欧拉的经典问题。(他曾经用欧拉的方法编码了一台由电脑控制的缝纫机。)

遵循高德纳博士的学说有助于保持睿智。他以引入“文学编程”的概念而闻名,强调编写人类和计算机可读代码的重要性 - 这一概念现在看起来几乎是天方夜谭。高德纳博士甚至认为,有些计算机程序就像伊丽莎白·毕晓普的诗和菲利普罗斯的《美国牧歌》一样,是可以评得上普利策奖的文学作品。

他也是臭名昭着的完美主义者。xkcd 漫画家兼《Thing Explainer》作者兰德尔 · 门罗(Randall Munroe)第一次听说高德纳博士是从一群计算机科学领域的学者口中,据称高德纳博士会为发现书中勘误的人支付奖金。正如门罗先生所回忆的,“大家将这样的一个错误检查视为计算机科学界的诺贝尔奖。”

高德纳博士的严格标准,文学和其他方面的成就,足以解释为什么他的人生并不止于此。他和谷歌的联合创始人谢尔盖 · 布林(Sergey Brin)以及以前的学生(姑且这么称呼)打了个赌:布林能否在高德纳博士完成他的著作之前完成他的博士学位。

算法的曙光

在 19 岁那年,高德纳博士在 Mad 杂志上发表了他的第一篇技术论文《The Potrzebie of Weights and Measures》。在计算机科学这个学科存在之前,他先成为了一名计算机科学家,并在现在的克利夫兰凯斯西储大学研究数学。他查看了学校的 IBM 650 大型机——一台十进制计算机上的示例程序,发现了程序漏洞,重写了软件以及教科书。他还做了一个为篮球队统计数据的小项目,编写了一个助力篮球队赢得联赛的程序 - 由此获得了 Walter Cronkite 授予的“电子教练”称号。

暑假期间,高德纳博士通过开发编译器赚的钱比当教授一年的收入还多。编译器就像翻译器,将高级编程语言(类似代数)转换为低级编程语言(有时是神秘的二进制),并在理想情况下提升性能。在计算机科学中,“优化”着实是一门艺术,克诺斯谚语中也有言曰:“过早优化是万恶之源。”

最终高德纳博士自己成了编译器,他不经意间创建了一个新的领域,并称之为“算法分析”。一位出版商聘请他写一本关于编译器的书,但最终成书涵盖了博士掌握的所有计算机编程知识 - 一本关于算法的书。

1981 年,高德纳博士正在阅读 1957 年的 Mad 杂志,该杂志出版了他的第一篇技术文章。 彼时他才 19 岁。| Jill Knuth

《计算机程序设计艺术》第 1-4 卷。 “如果你能读完整篇文章,请给我一份简历,”比尔盖茨写道 | 纽约时报 Brian Flaherty

“文艺复兴时期,这个词(Algorithm)的起源比较令人疑惑,”博士表示。“早期的语言学家试图通过制造像 algiros[痛苦] + arithmos[数字]这样的组合来推测它的产生。”事实上,高德纳博士继续说,该词最早发现于 9 世纪的波斯教科书(作者 Abū'AbdAllāhMuhammadibn Mūsāal-Khwārizmī),拉丁语译为 Algorithmi。高德纳博士从未半途而废,他于 1979 年前往乌兹别克斯坦 al-Khwārizmī 的祖先家园进行朝圣。

最初高德纳博士只打算简单写一篇文章。但不久之后,计算机科学迎来了大爆炸,因此他重新构想,并将该项目重铸为七卷,每个子卷称为分册。下一个部分“第 4 卷,第 5 册”,包括“回溯(backtracking)”和“舞蹈链(dancing links)”,原计划于圣诞节发布。后来推迟到明年 4 月,因为他不断寻求呈现越来越多不可抗的问题。

为了最优化达成目的,高德纳博士始终严格规划他的时间。他 55 岁时退休,严格限制自己的公开活动并不再使用电子邮件(至少是官方的)。安德烈 · 布罗德回忆说,即使在 1980s,时间管理也是他作为教授的鲜明特征。

高德纳博士通常在周五早上约见学生,然后在约翰 · 麦卡锡( John McCarthy,人工智能创始人)的实验室度过他的夜晚,以便自由访问计算机。随着数字出版业务的发展,高德纳博士心爱的书在页面上的效果令人震惊,他已经完成了创建 TeX 计算机排版系统的使命,该系统仍然是所有形式的科学传播和出版的黄金标准。有人把它当成高德纳博士对世界的最大贡献,以及自古腾堡(Gutenberg)以来对排版的最杰出贡献。

这个长达十年的绕道发生在人人拥有计算机的时代,并且每天晚上加速运作,而彼时大多数人都在睡觉。高德纳博士的生活是日夜颠倒的,他将自己的日程安排调整了 12 个小时,并将学生预约调整为从周五晚上 8 点至午夜结束。布罗德博士回忆说:“当我告诉我的女朋友我们周五晚上不能做其他事情,因为星期五晚上 10 点我必须见到我的导师时,她表示,'这真的太太太愚蠢了吧。(This is something that is so stupid it must be true.)' ”

然而,一旦高德纳决定亲临现场,他必定百分百投入。“呆在他身边实在振奋人心,”微软研究院董事总经理詹妮弗 · 夏雷斯(Jennifer Chayes)说: “他是社区中的佼佼者。如果有一种优化功能兼有温暖与深度,那么非他莫属。”

高德纳博士与字体设计师 Hermann Zapf 讨论字体。 许多人认为高德纳博士在 TeX 计算机排版系统上的工作是自古腾堡以来对排版的最杰出贡献 | Bettmann,来自 Getty Images

与算法学家共处的周日

高德纳博士住在斯坦福,会在周日接待一位“访客”。他的这一天过得非常特别 - 一般他的空闲时间是“模除午睡时间(modulo nap time)”,即下午 1-4 点的神圣日常仪式。他很早就出发去 Palo Alto’s First Lutheran Church,为一群站立式听众提供周日课程。在开车回家的路上,他也会进行数学相关的哲学思考。

“我不可能无所不知,”他说。“如果我一无所知或者无所不知,那我的生活会更糟。”接着,他带我们游览了他的“加州现代”房子,该房子由他和他的妻子吉尔于 1970 年建成。他的办公室里堆满了 U 盘以及来自平面设计师 Jill 的情人节心形艺术装饰。最令人印象深刻的是音乐室,环绕着他自制的 812 管道管风琴。拼图派对上的啤酒宣告了这一天的结束。

谜题和游戏 - 写一部关于研究之美的小说,谱写一段 90 分钟的多媒体音乐幻想,“Fantasia Apocalyptica” - 是真正让他技痒的事情。他的书有一节题为“拼图与真实世界(Puzzles Versus the Real World)”。由于引用了艺术家 Martin Demaine 的团队和 Erik Demaine(二者皆为麻省理工学院的计算机科学家)的“算法拼图字体”,因此博士还将摘录 email 给了他们。

“我很激动,”Erik Demaine 说。“能够出现在书中是我的荣幸。”他引用了高德纳的另一名言,同时也是两年一度的“FUN with Algorithms”会议鼓舞人心的座右铭:“快乐也许始终是主要目标。”

不过,Demaine 博士说,这个领域变得实用了。工程师,科学家和艺术家正在联手解决现实世界的问题 - 蛋白质折叠,机器人技术,安全气囊 - 使用 Demaines 的数学折纸设计,如何将纸张和链接折叠成不同的形状。

当然,所有的算法都会与现实相关联。人类编写的算法是为了解决越来越难的问题,但编写带有 bug 和 bias 的代码 - 十分令人不安。或许更令人担忧的是,不是人类编写的算法,而是机器学习人类编写的算法。

程序员仍然训练机器,并且至关重要的是,它提供了数据来源。(数据是 bias 和 bug 的新领域,且这些 bias 和 bug 更难找难修复)。然而,正如 M.I.T. 媒体实验室研究附属机构的 Kevin Slavin 所说:“我们正写着人类难以阅读的算法。这是历史上一个独特的时刻,我们受到一系列物理学的思想、行动和努力的影响,这些物理学源于人类但却难被人类理解。”正如斯拉文经常所说的,“如果你是一个算法学家,那么你的前途一片光明。”

1999年,高德纳博士在家中的办公桌 | Jill Knuth

几点说明 | 纽约时报 Brian Flaherty

如果你精通高德纳的算法,那就更是如此。“今天,程序员使用高德纳和其他人开发的算法组件,然后将它们与所需的所有其他东西结合起来,”Google 的 Norvig 博士说。

“对于 A.I. 也是如此。相组合的部分会根据数据自动组合在一起,而不由程序员完成。你希望 A.I. 能基于数据组合组件以得到结果。但是你必须明确该使用哪些组件。可能每个组件都是高德纳的论文或书中所提到的,因为这是最佳解决方案。”

幸运的是,高德纳博士始终坚持不懈。他认为还需要 25 年才能完成《计算机程序设计艺术》,尽管自 1980 年左右以来这个时间一直不变。可能某些章节只是某种算法的变换,或者作为某个结尾页面? “绝对不会!”高德纳博士说道。

“我担心算法在世界上变得过于突出,”他补充说。“最初计算机科学家担心无人倾听,而现在我担心有太多人在听。”


英文原文:

www.nytimes.com/2018/12/17/…


好文推荐:

《JavaScript DOM编程艺术》作者谈:原型代码与生产代码之间的矛盾

“UC国际技术”致力于与你共享高质量的技术文章

欢迎关注我们的公众号、将文章分享给你的好友


关注下面的标签,发现更多相似文章
评论