【转】张 建中老师谈算法7

我要吃章鱼丸子

影响算法世界的十位大师Posted on 2016年4月18日 by 张 建中
原文网址http://zhangjianzhong.blog.kepu.cn/20160418161460.html
数学技术之算法概论篇（7）
; x! m1 O& ?, l* a

5.影响算法世界的十位大师

大家熟知，任何时代，任何领域，无名英雄总比有名英雄多的多。所以，这里从众多算法大师中筛选出的十位大师，他们是众多算法大师的代表，既非全部，也非最大，仅供参阅。从对十位大师的简短介绍中不难看出，他们的杰出贡献多集中在新算法、程序语言及它们的普及、教育和推广等方面，只涉及算法中的部分领域，远非算法的全部。

入选这一名单的十位算法大师是：

Don E.Knuth（美）高德纳，《计算机程序设计艺术》的作者；

Edsger Wybe（荷兰）Dijkstra算法（最短路径算法）发明者；

George Dantzing（俄国）运筹学大师；

James Cooley（美）用于数字信号处理技术的快速傅利叶变换（FFT）算法发明者；

John Backus（美）FORTRAN之父，又提出规范描编程语言语法的Backus-Naur Form(BNF)；

Jon Bentley（美）《编程珠玑》（Programming Pearls）的作者，精于软件工程；

Nicklaus Wirth（瑞士）PASCAL之父，提出了“算法+数据结构=程序”；

Robort Sedgewick（美）　算法讲解大师；

Tony Hoare（英）　快速排序算法（Quick Sort）发明者；

Udi Manber（美）　Google副总裁，首席算法官。

下面，对这十位大师分别进行一些简单介绍。

1. Don E.Knuth

伟大的智者——Don E.Knuth，中译名：高德纳(1938-)，算法和程序设计技术的先驱者。

他的经典著作《计算机程序设计艺术》被誉为算法中“真正”的圣经，像KMP和LR(K)这样令人不可思议的算法，在此书比比皆是。难怪连Bill Gates都说：“如果能做对书里所有的习题，就直接来微软上班吧！”对于Don E.Knuth本人，一生中获得的奖项和荣誉不计其数，包括图灵奖，美国国家科学金奖，美国数学学会斯蒂尔奖（AMS Steel Prize），以及发明先进技术荣获的极受尊重的京都奖（Kyoto Prize）等等，写过19部书和160余篇论文，每一篇著作都能用影响深远来形容。Don E.Knuth也被公认是美国最聪明的人之一，当年上大学的时候，常写些各种各样的编译器来挣外快，只要是他参加过的编程比赛，总是第一名，同时也是世上少有的编程达到40年以上的程序员之一。他除了是技术与科学上的泰斗外，更是无可非议的写作高手，技术文章堪称一绝，文风细腻，讲解透彻，思路清晰而且没有学究气，估计这也是《计算机程序设计艺术》被称为圣经的原因之一。

2. Edsger Wybe Dijkstra

谦逊的长者——Edsger Wybe Dijkstra，1930年出生于荷兰阿姆斯特丹，2002年逝世于荷兰纽南。

他在祖国荷兰获得数据和物理学学士，理论物理博士学位，2000年退休前一直是美国Texas大学的计算机科学和数学教授。以发现了图论中的最短路径算法（Dijkstra算法）而闻名于世，1972年因为ALGOL第二代编程语言而获得图灵奖。“Go To Statement Considered Harmful”(EWD215)也是被广为传颂的经典之作。除了科学研究之外，他最喜欢做的事情就是教学，被人称作“一天教学24小时”的教授。且不说Dijkstra算法对计算科学，网络科学发展的深远影响，单从他在1972年获得图灵奖时的演讲“The Humble Programmer”就不得不肃然起敬，在获得计算机科学中至高无上的奖项时，Edgs Wybe Dijkstra仍然谦称自己不过是一个普通的程序员，何等胸襟，举世之中能有几人可比。

3. George Dantzig

运筹学大师——George Dantizig可谓是由父亲一手培养出的天才。

George的父亲是俄国人，曾在法国师从著名的科学家Henri Poincare。他曾经这样回忆自己的父亲：“在我还是个中学生时，他就让我做几千道几何题……解决这些问题的大脑训练是父亲给我的最好礼物。这些几何题，在发展我分析能力的过程中，起了最最重要的作用。”在伯克利学习的时候，有一天George上课迟到，只看到黑板上写着两个问题，他只当是课堂作业，随即将问题抄下来并做出解答。六个月后，这门课的老师——著名的统计学家Jerzy Neyman——帮助他把答案整理了一下，发表为论文，George这才发现自己解决了统计学领域中一直悬而未决的两个难题。George后来在运筹学建树极高，获得了包括“冯.诺伊曼理论奖”在内的诸多奖项。他在Linear programming and extensions一书中研究了线性编程模型，为计算机语言的发展做出了不可磨灭的贡献。

4. James Cooley

推动时代前进的人——James Cooley(1926-)，美国数学家，哥伦比亚大学数学博士。

以他所创造的快速傅立叶变换(FFT)而著名，不能不说是意义极其重大，FFT的数学意义不光在于使大家明白了傅立叶变换计算起来是多么容易，而且使得数字信号处理技术取得了突破性的进展，对于现在的网络通信，图形图像处理等等领域的发展与前进奠定了基础。傅立叶变换的意义在于将电能变为了工业的命脉，而FFT的意义更是在于他推动了整个社会信息化的进程。在IBM研究中心主要从事数字信号处理的研究一直到1992年退休，同时他还是IEEE的数字信号处理委员会的成员。1980年获得ASSP’s Meritorious Service Award，1984年获得ASSP Society Award以及IEEE Centennial Medal。

5. John Backus

FORTRAN之父——John Backus，早年在Hill School学习的时候因为讨厌学习，成绩一踏糊涂而不得不在暑假补课。1943年他在父亲的要求下到维吉尼亚大学学习化学，随后参军、照顾头部受伤的伤员、在医学学校学习治疗，可是最后又都放弃了。不过还好，战后Backus进入纽约哥伦比亚大学学习数学，并于1949年毕业。在毕业前夕，他跑到了麦迪逊大街的IBM计算机中心参观。事情凑巧，和导游聊天的时候Backus谈到自己正在找工作，在导游的鼓励下，他和中心一位主管的面谈，成为了一名IBM的程序员。在IBM，Backus的才华得到了施展，发明了人类历史上第一个高级语言——FORTRAN。接着，又提出了规范描述编程语言语法的Backus-Naur Form(BNF)。这位当年的“差生”终于被整个计算机世界肯定——美国计算机协会于1977年授予John Backus图灵奖。

6. Jon Bentley

实践探索先锋——Jon Bentley，1974年获得了斯坦福大学的学士学位，1976年获得北卡罗莱纳大学的硕士和博士学位。毕业后在卡耐基梅隆大学教授了6年计算机科学课程，1982年进入贝尔实验室。2001年退休后加入了现在的Avaya实验室，他还曾作为访问学者在西点军校和普林斯顿大学工作。他的研究领域包括编程技术、算法设计、软件工具和界面设计等等。

他写过三本编程书籍，其中最著名的就是涵盖从算法理论到软件工程各种主题的Programming Pearls(《编程珠玑》)，这其实是他发表过的文章的合集。在这些文章里，Bentley从工程实现的角度出发，为程序员们提供了一个个艰难问题的解决方案，犹如一颗颗闪闪发亮的珍珠。Bentley的珍珠超出了可靠工程学的范畴，利用他的洞察力和创造力为那些恼人的问题提供了独特而巧妙的解决方案。

7. Nicklaus Wirth

Pascal之父——Nicklaus Wirth，1934年出生于瑞士，1963年在加州大学伯克利分校取得博士学位。

如果说有一个人因为一句话而得到了图灵奖，那么这个人应该就是Nicklaus Wirth，这句话就是他提出的著名公式“算法 + 数据结构 = 程序”。这个公式对计算机科学的影响程度足以类似物理学中爱因斯坦的“E = MC2”——一个公式展示出了程序的本质。Nicklaus Wirth，取得博士学位后直接被斯坦福大学聘到刚成立的计算机科学系工作。在斯坦福大学成功的开发出Algol以及PL360后，爱国心极强的Nicklaus Wirth于1967年回到祖国瑞士，第二年在他的母校苏黎世工学院他创建与实现了Pascal语言-——当时世界上最受欢迎的语言之一。后来他的学生Philipe Kahn毕业后和Anders Hejlsberg(Delphi之父)创办了Borland公司靠Turbo Pascal起家，很快成为了将Borland发展成为全球最大的开发工作厂商，这一切都不得不说要归工于Pascal语言的魅力。Pascal已经影响了整整几代的程序员，Nicklaus Wirth的思想还将会继续指引现在和以后的程序员前进的方向。

8. Rebort Sedgewick

算法的讲解者——Robert Sedgewick，斯坦福大学获得博士学位，普林斯顿大学的计算机科学教授。

Robert Sedgewick是Adobe Systems的一名主管，也曾作为访问学者在Xerox PARC、IDA和INRIA工作。他的著作包括Algorithmin C、Algorithmin C++、Algorithmin Java等系列书籍，这些都再版多次。“没有人能够将算法和数据结构解释得比Robert Sedgewick更清楚易懂了！”很多读过他著作的程序员这样说。他善于通过数学方法评估和预测算法性能，设法发现算法、数据结构的通用机制，例如使用逼近方法寻找更快速更高效的算法。另外，他还将算法和图形学结合起来，例如使用可视化方法评估算法效率，算法的图形化模拟，用于出版物的高质量算法表现方法等等。

9. Tony Hoare

计算机领域的爵士——Tony Hoare，1934年出生于英国，1959年博士毕业于俄罗斯莫斯科国立大学，获得语言机器翻译专业学士学位。1960年发布了使他闻名于世的快速排序算法（Quick Sort），这个算法也是当前世界上使用最广泛的算法之一。

Tony Hoare在取得博士学位后，就职于Elliott Brothers，领导了Algol 60第一个商用编译器的设计与开发，由于其出色的成绩，最终成为该公司首席科学家。从1977年开始，Tony Hoare博士任职于牛津大学，投身于计算系统的精确性的研究、设计及开发。因其对Algol 60程序设计语言理论、互动式系统及APL的贡献，1980年被美国计算机协会授予“图灵奖”。1999年在牛津大学退休后，Tony Hoare博士被微软剑桥研究院聘请担任高级程序员，从事微软剑桥研究院研究生成果的工业化应用以及协助其它研究人员进行服务于软件产业及用户的长期基础研究项目。2000年因为其在计算机科学与教育上做出的贡献被封为爵士。

10. Udi Manber

首席算法官——Udi Manber，国际公认的算法大师，在线信息搜索引擎的先驱，曾是美国亚利桑那大学的计算机专业的教授，他提出的UDI测试已经成为衡量搜索引擎质量的评估标准。

首席算法官，世界上还有如此奇怪的职位？但是对于Amazon乃至Google来说，这一点也不奇怪。Udi Manber，这位前Amazon的“首席算法官”，现在是Google负责工程事务的副总裁。他研究WWW的应用程序、搜索以及隐藏在这背后的算法设计。在此期间，他与其他人共同开发了Agrep、Glimpse和Harvest等Unix上的搜索软件。1998年，Udi成为了Yahoo的首席科学家。2002年，Amazon创造性地给了Udi“首席算法官”的职位，和Udi为Amazon的“Search Inside the Book”搜索项目所做的工作相得益彰。Udi还因为他所著的Introduction to Algorithms——A Creative Approach而被大家称道。

. s% g/ X; {/ Z
. P8 ^6 g1 c. T8 ]3 h