【AI】一文了解72名图灵奖获得者的成就(3)

东尼·霍尔 C. Antony R. Hoare 贡献领域：程序设计语言的定义与设计 他设计出了快速排序算法、霍尔逻辑。 快速排序算法，经典的排序算法，是对冒泡排序的一种改进。 霍尔逻辑，是东尼·霍尔开发的形式系统，这个系统的用途是为了使用严格的数理逻辑推理来替计算机程序的正确性提供一组逻辑规则。 埃德加·科德 Edgar F. Codd 贡献领域：数据库系统，尤其是关系型数据库 在 IBM 工作期间，首创了关系模型理论。他一生中为计算机科学做出了很多有价值的贡献，而关系模型，作为一个在数据库管理方面非常具有影响力的基础理论，仍然被认为是他最引人瞩目的成就。 史提芬·古克 Stephen A. Cook 贡献领域：计算复杂度 因其在计算复杂性理论方面的贡献，尤其是在奠定 NP 完全性理论基础上的突出贡献而荣获 1982 年度的图灵奖。他整理了 NP 完备性的目标，亦产生了古克定理——布尔可满足性问题是 NP 完备的证明。因为其论文开启了 NP 完备性的研究，令这个范畴于之后的十年成为计算机科学中最活跃和重要的研究。 肯·汤普森 Ken Thompson 丹尼斯·里奇 Dennis M. Ritchie 贡献领域：UNⅨ 操作系统和C语言 肯·汤普森与丹尼斯·里奇设计了 B 语言、C 语言，之后用 C 语言重写了 UNIX，安装于 PDP-11 的机器之上。不仅如此，2006 年，汤普森进入 Google 工作与罗勃特·派克，罗伯特·格瑞史莫共同主导了 Go 语言的开发。 尼古拉斯·沃斯 Niklaus Wirth 贡献领域：程序设计语言设计、程序设计 凭借一句话获得图灵奖的 Pascal 之父，让他获得图灵奖的这句话就是他提出的著名公式：“ 算法+数据结构=程序 ”。 理查德·卡普Richard M. Karp 贡献领域：算法理论，尤其是 NP-完全性理论 主要贡献有二，其一就是对计算复杂性理论中的术语进行了规范和统一。把有多项式时间算法的问题命名为 P 类问题，就是卡普在这篇论文中首次采用的，已为学术界所接受并普遍采用，这为学术交流带来了很大的好处。 其二是卡普在刻画 NP 类中的“最困难”问题类时，提出了与史提芬·古克归约不同的另一种归约方法，称作“多项式时间多一归约”，有时直接把它叫做“卡普归约”。 约翰·霍普克罗夫特 John Hopcroft 罗伯特·塔扬 Robert Tarjan 贡献领域：算法和数据结构的设计与分析 罗伯特·塔扬 以在数据结构和图论上的开创性工作而闻名。他的一些著名的算法包括，塔扬最近共同祖先离线算法 ，塔扬的强连通分量算法 以及 Link-Cut-Trees 算法等。其中 Hopcroft-Tarjan 平面嵌入算法是第一个线性时间平面算法。 塔扬也开创了重要的数据结构如：斐波纳契堆和 splay 树（splay 发明者还有Daniel Sleator）。另一项重大贡献是分析了并查集。他是第一个证明了计算反阿克曼函数的乐观时间复杂度的科学家。 霍普克罗夫特的研究领域是理论计算机科学。他将计算机科学萌芽阶段的零散结果总结为具有整体性的系统知识，提出用渐近分析作为衡量算法性能的主要指标，成为当今计算机科学的一大支柱。 约翰·科克 John Cocke 贡献领域：编译理论，大型系统的体系结构，及精简指令集（RISC）计算机的开发。 科克又主持了一个 801 计算机项目，801 计算机原是为每小时能处理 100 万次呼叫的全数字电话交换机设计的专用机。 但实现中被发展为一种具有小指令集、每个指令都是单地址、有固定格式、以流水线方式重叠执行、指令高速缓存和数据高速缓存则分开并互相独立的一种超级通用小型机。 科克对编译器的代码生成技术进行了深入研究，提出了一系列优化方法，如过程(Procedure)的集成、循环(loop)的变换、公共子表达式(common subexpression)的消除、代码移动(code motion)、寄存器定位、存储单元重用等等，编译器的质量大大提高，使编译技术发展到一个新阶段。 伊凡·苏泽兰Ivan Sutherland 贡献领域：计算机图形学 伊凡·苏泽兰作为计算机图形学之父和虚拟现实之父，发明的电脑程序“画板”是人们“曾经编写过的程序中最重要的一份程序”。 事实上，这是有史以来第一个交互式绘图系统。这也是交互式电脑绘图的开端。但还要花十多年以后，电脑业和工程界才真正体会到苏泽兰和电脑程序“画板”带来的划时代变革。 威廉·卡亨 William Morton Kahan 贡献领域：数值分析 卡亨，在 Intel 工作期间，主持设计与开发了 8087 芯片，成功地实现了高速、高效的浮点运算部件。 目前，以 80x86 为 CPU 的计算机，若需完成科学与工程计算方面的课题，有些需配置 8087 这种数学协处理器。一些著名的数学软件包，也必须在配有 8087 数学协处理器的机器上才能运行，因在浮点运算标准的制定上的贡献而获得图灵奖。