前不久,2020图灵奖今日出炉,龙书作者 Alfred Vaino Aho 和 Jeffrey David Ullman 获奖,作为计算机界的最高荣誉,图灵奖获得者及其成果对计算机学科意义非凡,以前只是大概知道几个人,今天,特地翻了翻维基,看看得奖的都有谁。

最为知名的获奖者

肯·汤普森 Ken Thompson

丹尼斯·里奇 Dennis M. Ritchie

肯·汤普森与丹尼斯·里奇设计了 B 语言、C 语言,之后用 C 语言重写了 UNIX。

如今,汤普森老当益壮,又主导了 Go 语言的开发。

这两位可能比图灵还出名

艾兹格·迪科斯彻 Edsger Dijkstra

他的贡献有:

  • 提出“goto有害论”
  • Dijkstra最短路径算法
  • 提出信号量和PV原语
  • 解决了“哲学家聚餐”问题
  • 银行家算法的创造者
  • 第一个Algol 60编译器的设计者和实现者
  • THE操作系统的设计者和开发者
  • 被西方学术界称为“结构程序设计之父”和“先知”

学数据结构告诉你他是图灵奖得主,学操作系统时又不止一次告诉你他是图灵奖得主,学程序设计还要提醒你他是图灵奖得主。简直是图灵奖界的劳模。

姚期智 Andrew Chi-Chih Yao

最先提出量子通信复杂性,基本上完成了量子计算机的理论基础,之后提出分布式量子计算模式,成为分布式量子算法和量子通讯协议安全性的基础。

研究方向包括计算理论及其在密码学和量子计算中的应用。在三大方面具有突出贡献:

  • 创建理论计算机科学的重要次领域:通讯复杂性和伪随机数生成计算理论;
  • 奠定现代密码学基础,在基于复杂性的密码学和安全形式化方法方面有根本性贡献;
  • 解决线路复杂性、计算几何、数据结构及量子计算等领域的开放性问题并建立全新典范

唯一的华人获奖者,进入清华姚班是无数学子的梦想

罗伯特·塔扬 Robert Tarjan

他的一些著名的算法包括:

  • 最近共同祖先离线 Tarjan 算法

  • 强连通分量 Tarjan 算法

  • Hopcroft-Tarjan 平面嵌入算法,第一个线性时间平面算法。

数据结构:

  • 斐波纳契堆
  • splay 树(splay 发明者还有Daniel Sleator)
  • Link-Cut-Tree

另一项重大贡献是分析了并查集。他是第一个证明了计算反阿克曼函数的乐观时间复杂度的科学家。

别人可能不熟悉,但 OIer 一定知道他

高德纳 Donald E. Knuth

  • TeX 排版软件
  • 《计算机程序设计艺术》计算机科学理论与技术的经典巨著
  • 舞蹈链(Dancing Links)
  • KMP 算法的“K”
  • LR解析理论(LR parsing theory)、克努斯-莫里斯-普拉特模式(Knuth-Moris-Pratt pattern)等

高老爷子的个人主页 https://www-cs-faculty.stanford.edu/~knuth/

另外出名的几位

LISP 语言, α-β 搜索:约翰·麦卡锡 John McCarthy

“汉明距离”和“汉明重量”: 理查德·卫斯里·汉明 Richard Hamming 美国计算机协会(ACM)的创立人之一

快速排序算法:东尼·霍尔 C. Antony R. Hoare 霍尔逻辑

堆排序算法和 Floyd-Warshall 算法: 罗伯特·弗洛伊德 Robert W. Floyd 前后断言法的创始人,的创始人之一,FPL语言发明者之一,FPL 用来编写计算机语言的语法分析程序。

diffie-hellman密钥交换算法 惠特菲尔德·迪菲 Whitfield Diffie 马丁·赫尔曼 Martin Hellman 非对称加密的开创者

RSA加密算法:罗纳德·李维斯特 Ronald L. Rivest 阿迪·萨莫尔 Adi Shamir 伦纳德·阿德曼 Leonard M. Adleman

万维网 蒂姆·伯纳斯·李 Tim Berners-Lee 在 1989 年发明了万维网,1991 年,他做出第一个图形界面网页浏览器,1994 年,他确定了超链接的标准。

TCP/IP 协议 文特·瑟夫 Vinton G. Cerf 罗伯特·卡恩 Robert E. Kahn 罗伯特·卡恩发明了 TCP 协议,并与文特·瑟夫一起发明了 IP 协议,这两个协议成为全世界因特网传输资料所用的最重要的技术。

面向对象编程 奥利-约翰·达尔 Ole-Johan Dahl 克利斯登·奈加特 Kristen Nygaard 开发了最早的面向对象的程序设计语言 SIMULA-I 和 SIMULA-67,首次引入了面向对象程序设计语言的基本概念。

算法+数据结构=程序: 尼古拉斯·沃斯 Niklaus Wirth 还是Pascal 之父

BNF 范式:彼得·诺尔 Peter Naur ALGOL 60 语言

关系型数据库:埃德加·科德 Edgar F. Codd

其他(摘自维基百科)

仅仅大致整理,不严谨

艾伦·凯 Alan Kay Smalltalk 被公认为历史上第二个面向对象的程序设计语言,和第一个真正的集成开发环境。

约翰·巴克斯 John Backus 他提出了BNF(用来定义形式语言语法的记号法),发明函数式编程这个概念及实践该概念的计划生育语言,被誉为“Fortran 语言之父”。

肯尼斯·艾佛森 Kenneth E. Iverson 建立了 APL 语言。

芭芭拉·利斯科夫 Barbara Liskov 领导了多个重要项目,包括第一个支持数据抽象的面向对象编程语言 CLU 的设计与实现,第一个支持分布式程序实现的高级语言 Argus,面向对象数据库系统Thor,还有最近的Byzantine分布式容错系统。 其中,CLU 语言对现代主流语言如 C++/Java/Python/Ruby/C# 都有比较深远的影响。而她从这些实际项目中提炼出来的数据抽象思想,已经成为软件工程中最重要的精髓之一。


查理士·巴赫曼 Charles W. Bachman 主持设计与开发了最早的网状数据库管理系统IDS,积极推动与促成了数据库标准的制定

詹姆斯·尼古拉·格雷 James Gray 在事务处理技术上的创造性思维和开拓性工作

迈克尔·斯通布雷克 Michael Stonebraker 在关系数据库管理系统(RDBMS)和数据仓库(DWH)的创建、开发和改进方面的基础工作而闻名于世。


查尔斯·萨克尔 Charles Thacker 帮助设计、制造第一款现代 PC

约翰·科克 John Cocke 主持了一个 801 计算机项目。对编译器的代码生成技术进行了深入研究,提出了一系列优化方法。

伊凡·苏泽兰 Ivan Sutherland 计算机图形学之父和虚拟现实之父

威廉·卡亨 William Morton Kahan 主持设计与开发了 8087 芯片,成功地实现了高速、高效的浮点运算部件。

费尔南多·考巴脱 Fernando J. Corbató 研制了世界上第一个分时系统 CTSS

道格拉斯·恩格尔巴特 Douglas Engelbart 鼠标之父,人机交互的先锋,开发了超文本系统、网络计算机,以及图形用户界面的先驱;并致力于倡导运用计算机和网络,来协同解决世界上日益增长的紧急而又复杂的问题。

弗雷德里克·布鲁克斯 Frederick P. Brooks,Jr. 主持与领导了被称为人类从原子能时代进入信息时代的标志的 IBM/360 系列计算机的开发工作


艾伦·纽厄尔 Allen Newell 赫伯特·西蒙 Herbert A. Simon 给“物理符号系统” 下了定义,提出了“物理符号系统假说”,成为人工智能中影响最大的符号主义学派的创始人和代表人物。

爱德华·费根鲍姆 Edward Feigenbaum 拉吉·瑞迪 Raj Reddy 证明了实现智能行为的主要手段在于知识,在多数实际情况下是特定领域的知识,从而最早倡导了"知识工程”,并使知识工程成为人工智能领域中取得实际成果最丰富、影响也最大的一个分支。

犹大·伯尔 Judea Pearl 提出概率推理与因果关系推理的演算模式,是人工智能领域基础性的贡献。

莱斯利·瓦伦特 Leslie Valiant 在机器学习、计算复杂度理论、并行和分散计算等领域都有突出贡献


史提芬·古克 Stephen A. Cook 因为其论文开启了 NP 完备性的研究。

理查德·卡普 Richard M. Karp 一就是对计算复杂性理论中的术语进行了规范和统一。 其二是提出了“多项式时间多一归约”,有时直接把它叫做“卡普归约”。

约翰·霍普克罗夫特 John Hopcroft 将计算机科学萌芽阶段的零散结果总结为具有整体性的系统知识,提出用渐近分析作为衡量算法性能的主要指标,成为当今计算机科学的一大支柱。

尤里斯·哈特马尼斯 Juris Hartmanis 理查德·斯特恩斯 Richard E. Stearns 对“香农公式”开展了深入的研究,其结果就是那篇著名的论文“论算法的计算复杂性”,这篇论文开辟了计算机科学的一个新的研究领域,即“计算复杂性”,并奠定了它的理论基础。

曼纽尔·布卢姆 Manuel Blum 发表了论文《递归序列的计算复杂性》,论文中首次使用了“计算复杂性” 这一术语,由此开辟了计算机科学中的一个新领域。


迈克尔·拉宾 Michael O. Rabin 达纳·斯科特 Dana S. Scott 共同发表了“有限自动机与其判定性问题”的论文,提出了非确定自动机的观点

罗宾·米尔纳 Robin Milner 提出了形式化逻辑系统的数学模型,实现了他称之为LCF的一个系统——“可计算函数的逻辑”。另一方面的贡献是关于并发计算(concurrent computing)和并行计算(parallel computing)。

巴特勒·兰普森 Butler W. Lampson 解决计算机文件系统和分布式系统的技术问题上有许多突出的贡献。例如提出“原子事务”(atomic transaction)的概念、提出采用“三明治式的提交协议”(sandwich commit protocol)提高系统可靠性的方案等等。

阿米尔·伯努利 Amir Pnueli 在计算机科学中引入时序逻辑的开创性的研究工作,和其在编程语言和系统验证方面的突出贡献。

法兰西斯·艾伦 Frances E. Allen 致力于研究并行计算机的编译问题

爱德蒙·克拉克 Edmund M. Clarke 艾伦·爱默生 Allen Emerson 约瑟夫·斯发基斯 Joseph Sifakis 模型检查理论基础

莎菲·戈德瓦塞尔 Shafi Goldwasser 希尔维奥·米卡利 Silvio Micali 共同开创了可证明安全性领域的先河,奠定了现代密码学理论的数学基础。

莱斯利·兰伯特 Leslie Lamport 发表的论文《分布式系统内的时间、时钟事件顺序》; 为“并发系统的规范与验证”研究贡献了核心原理。