No.435 第9届图灵奖得主、《计算机编程艺术》作者、算法分析之父:唐纳德·高德纳Donald Ervin Knuth

我做了400多期电台节目了。就像如果你学编程不知道高德纳一样,就好比学物理不知道牛顿,学数学不知道欧拉,学音乐不知道莫扎特,学Delphi不知道Anders Hejlsberg,或者学Linux不知道Linus Torvalds一样。这简直是不可原谅的。他的名声太大了,所以在我做的这个电台的第50期节目中,我就已经专门录了一期介绍他的内容。为了连贯性,这次我还是重新讲一下。我重新听了一下以前的内容,这次讲点不一样的。

斯坦福大学给他搞了一个个人网站,网址如下:www-cs-faculty.stanford.edu/~knuth/ 在这个网站上,有这样一个故事。

linux的发明人说:我一觉醒来,上帝告诉我,我编写了世界上最好的操作系统。

还有一个牛人Richard Stallman,他是GNU开源运动的发起人,目前他不幸得了癌症,我看过他最近的照片,头发已经掉光了,有点感慨万千,当年是多么潇洒的一个人啊。这个Richard Stallman说:我一觉醒来,上帝告诉我,我编写了世界上最好的文字处理软件。也就是那个Emacs。

Donald说:“我没有对你们那么说过!”

显然,他很喜欢这个故事,否则他不会把这个故事放在自己的网上。

说起Emacs,跟他竞争的是一个叫Vim的软件,这个软件的作者,去年也去世了。Vim这个编辑器的作者叫Bram Moolenaar 布拉姆·穆勒纳尔,他于去年,2023年8月3日因病去世,享年62岁。他在Google工作,工作内容是制作Google Calendar。我本来想好好给他做两期节目的,后来就忘记了,等我录完所有的图灵奖得主之后,我想给他录两期Podcast,希望这次不要再忘记了。

本期的主人公,在2006年的时候,也不幸得了癌症,不幸中的万幸运是癌症中最好治疗的几种癌症之一,前列腺癌。他于当年 12 月接受了手术,并在视频自传中表示,“进行了一点放射治疗……作为预防措施,但预后看起来相当不错”。

Donald Ervin Knuth(生于 1938 年 1 月 10 日)是一位美国计算机科学家和数学家。他是斯坦福大学的名誉教授。他是 1974 年 ACM 图灵奖的获得者,该奖被非正式地视为计算机科学的诺贝尔奖。他是至今为止最年轻的获奖者,获奖的时候只有36岁。Knuth 被称为“算法分析之父”。Knuth 是多卷本《计算机编程的艺术》一书的作者。他为算法计算复杂性的严格分析及其系统化的形式数学技术的发展做出了贡献。在此过程中,他还普及了渐近符号。作为一名作家和学者,Knuth 创建了 WEB 和 CWEB 计算机编程系统,旨在鼓励和促进文学编程,并设计了 MIX/MMIX 指令集架构。他强烈反对授予软件专利,并向美国专利商标局和欧洲专利组织表达了自己的观点。

唐纳德·高德纳(Donald Knuth)出生在威斯康星州密尔沃基,他的父亲叫欧文·亨利·高德纳(Ervin Henry Knuth),妈妈名叫路易丝·玛丽·博宁(Louise Marie Bohning)。他自己说他是“中西部路德德国人”。小时候,他爸爸在经营一家小印刷公司的同时也教会记。当高德纳还在密尔沃基的路德高中读书时,他就开始展现了解决问题的聪明才智。比如,他参加了一个比赛,要求寻找“齐格勒的巨型酒吧”里可以重新排列出多少单词;官方发现了 2,500 个这样的单词。高德纳家的地下室里有一本字典,一本未删节的字典,确定每个字典条目是否可以用来重新排列成短语中的字母。他请了几天病假,说自己胃疼,用这本字典,他找出了超过 4,500 个单词,最终赢得了比赛。作为奖励,学校得到了一台新电视和足够的糖果给所有同学吃。

1956年,Knuth获得了俄亥俄州克利夫兰凯斯理工学院(现为凯斯西储大学的一部分)的物理学奖学金。他还加入了Theta Chi兄弟会的Beta Nu分会。在Case学习物理期间,Knuth接触到了IBM 650,这是一款早期的商用计算机。读完计算机手册后,Knuth决定为学校使用的机器重写汇编和编译器代码,因为他相信自己可以做得更好。实际上,他确实做的更好。当IBM这些公司发现,我去,卖了一台机器,竟然给写了一个操作系统,简直就是天才中的天才了。

从此,高德纳本科时就开始给行行色色的公司写各种稀奇古怪的编译器挣外快了。他卖给别人时收一两千美元,那些公司拿了code,加工一下卖出去就是上万上十万。想想那可是60年代初啊,高德纳写编译器写多了,顺带就搞出了个Attribute Grammar和LR(k),大大地造福后人啊。

LR 在计算机科学中通常指的是“LR 分析法”(LR parsing),是一种自底向上的语法分析方法。它是由 Donald Knuth 和 Vaughan Pratt 等人发明的。LR 分析法被广泛应用于编译器的设计与实现中,用于将源代码转换成语法树或其他形式的中间表示。

1958年,Knuth创建了一个程序来帮助他学校的篮球队赢得比赛。他为球员分配“数值”,以衡量他们得分的概率,这是一种新颖的方法,后来被《新闻周刊》和《哥伦比亚广播公司晚间新闻》报道。

Knuth是凯斯研究所《工程与科学评论》的创始编辑之一,该杂志于1959年荣获国家最佳技术杂志奖。随后,他从物理学转向了数学,并于1960年从凯斯获得了两个学位:理学学士学位,以及同时获得的理学硕士学位,学院认为他的工作异常出色。这也是有史以来该校第一位发本科毕业证的时候,同时发了硕士学位的人。

1963年,他在加州理工学院师从数学家马歇尔·霍尔(Marshall Hall),拿到了数学博士学位,毕业论文题目是《有限半场和射影平面》。年仅25岁,就进入了加州理工学院数学系,用了仅三年时间就攻读完博士学位。毕业后留校担任助理教授,28岁时晋升为副教授。30岁那年,他转投斯坦福大学计算机系,成为正教授。从31岁开始,他开启了撰写历史性经典之路:《计算机编程艺术》。虽然他计划撰写7卷,但仅出版了三卷就已经轰动全球,让他荣获了计算机科学界的最高奖项——图灵奖!时年38岁!他的著作与牛顿的《自然哲学的数学原理》并列,成为“世界历史上最伟大的十种科学著作”之一。相信学过数据结构和编译原理的同学们都知道KMP算法和LR(K)算法有多么不可思议,然而在他的著作中这样的算法比比皆是!在计算机科学领域,他以理论家的身份为人所知。但是,他也在其他领域取得了惊人的成就。像Tex这样的排版软件,便是他的杰作。此外,还有Metafont等,也被广泛应用于世界各地。

高德纳其实还是开源运动的先驱。虽然他没有象Richard Stallman那样八方奔走,但他捐献了好多作品,都可以在网上看到,比如著名的Mathematical Writing,MMIXWare,The Tex Book等,更不用说足以让他流芳百世的Tex了。写的Tex到86年就不再更新了,因为已经没有bug了,更新已经没有必要。如果谁能找到bug,还附带2^n美分奖励。大家知道2的n次方吧,如果bug太多,微软+Apple+Google的市值加起来也不够赔的,但是牛人么,bug比较少,再加上谁拿到支票也不会真的兑换那些钱,毕竟那是Knuth亲笔签名的支票啊,所以,他并没有真的付出多少钱。

Knuth获得图灵奖时为36岁。估计他可能是历史上最年轻的图灵奖获得者,甚至有可能永远把这个记录保持下去。相比之下,其他获得图灵奖的人当时一般都是五十几岁或者六十几岁。

他很早就提前退休,为的是集中精力把巨著The Art of Computer Programming写完。中文版的这本书,第一版是吉林大学的教授苏运霖翻译的,苏教授写过一篇文章来介绍当时的情况。白天挖防空洞,晚上翻译,由于那个年代特别有自信,认为翻译外国的书纯粹是崇洋媚外。苏教授由于此前翻译过外国计算机的一些课程,还得受排挤打压。搞得翻译这本书要偷偷的进行,只有两个人知道。他负责整体的翻译,另一个人负责检查与抄写。要夜深人静了,才能翻译,怕让别人知道他又在崇洋媚外。

他一生共培养了二十多名博士生,并宣誓不再接受更多的学生。如今,他指导的那些博士生也都成为了学界的佼佼者。其中,R. Sedgewick(普林斯顿算法课程的领头人)撰写了著名的教材《Algorithms in C/C++/Java》等,每个版本都包含五个部分。

尽管他不再担任博士生导师,但他有一个奇妙的承诺:在定期的讲座中,他会提出新的难题。如果有人能在规定的时间内解决任何一个问题,他将亲自为那个人的博士论文签名!

除了《计算机编程艺术》,他的其他著作和论文数不胜数,其中包括《具体数学》等名著。自从1977年起,他担任斯坦福大学的Fletcher Jones计算机科学教授,并兼任电气工程教授。1990年,斯坦福大学特授予他“计算机科学艺术教授”的非凡头衔,以表彰他在该领域的特殊贡献!

他荣获的其他奖项和荣誉太多以至于数不胜数:美国国家科学院院士,美国艺术与科学院院士,美国工程院院士,法国科学院外籍院士,挪威科学院外籍院士……他还获得了美国数学会的Steele奖,瑞典皇家科学院的Adelskold奖,以色列工学院的Harvey奖,IEEE的冯诺依曼奖,东京高科技奖等,共计数十个!

同时,他还被授予了二十多所大学的荣誉博士学位。早在1970年,他就在国际数学大会上做过特邀报告。

0 0 投票数
文章评分
订阅评论
提醒

0 评论
最旧
最新 最多投票
内联反馈
查看所有评论
0
希望看到您的想法,请您发表评论x
滚动至顶部