datasheet

Leiphone雷锋网

文章数:8431 被阅读:25404165

账号入驻

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

2018-12-21
    阅读数:

▲点击上方 雷锋网 关注

文 | 王雪佩

来自雷锋网(leiphone-sz)的报道

雷锋网AI科技评论按:Donald Knuth,著名计算机科学家,誉满全球的图灵奖获得者,斯坦福大学计算机系荣誉退休教授。作为现代计算机科学的先驱人物,他发明了计算机排版系统 TEX 和 METAFONT,创造了算法分析的领域,在计算机科学及数学领域发表了多部具广泛影响的论文和著作。

日前,纽约时报对他进行了一次专访。在这次访谈中,Knuth 博士谈到了他对算法的一些看法,反思了他 50 年来的作品《The Art of Computer Programming》,并表示:“我担心算法变得太过重要。一开始,我们这些计算机科学家担心没有人听我们的,但现在,听我们的人太多了。” 关于纽约时报的撰文,雷锋网 AI 科技评论编译整理如下:

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 博士在家办公

    一些笔记

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

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

Knuth 一直在坚持完成他的作品,他估计还需要 25 年才能完成《The Art of Computer Programming》,尽管自 1980 年他就已经在做这件事情。“会不会有一章,或者有一页谈到会写算法的算法?”“当然不会!”Knuth 表示。

“我担心算法变得太过重要。”他补充道,“一开始,我们这些计算机科学家担心没有人听我们的,但现在,听我们的人太多了。” 

来源:https://www.nytimes.com/2018/12/17/science/donald-knuth-computers-algorithms-programming.html?smid=tw-nytimesscience&smtyp=cur

- END -

今日起,参与#向2019微信公开课PRO版发起提问#活动互动,即有机会赢精美大奖!点击去提问


  ◆  


推荐阅读


2018,华米高歌猛进的一年

腾讯加入智能音箱大战,是否为时已晚?

ofo线上排队退款用户超1000万;SpaceX将融资5亿美元

凉凉!Google中国版搜索引擎被内部“毙了”



关于「AI投研邦」


雷锋网旗下会员组织,聚焦AI+10大领域 :AI+汽车(智能驾驶)、AI+教育、AI+金融、AI+智慧城市、AI+安防、AI+医疗等。仅剩199个早鸟席位,欢迎加入。



                                                 

About Us 关于我们 客户服务 联系方式 器件索引 网站地图 最新更新 手机版

站点相关: TI培训

北京市海淀区知春路23号集成电路设计园量子银座1305 电话:(010)82350740 邮编:100191

电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2018 EEWORLD.com.cn, Inc. All rights reserved