Page 304 - 信息的脉络

·信息的脉络·
与罗勃特·派克，罗伯特·格瑞史莫共同主导了 Go 语言的开发。
19. 尼古拉斯·沃斯（Niklaus Wirth）

贡献领域：程序设计语言设计、程序设计。
获奖年份：1984 年。
凭借一句话获得图灵奖的 Pascal 之父，让他获得图灵奖的这句话就是他提出

的著名公式：“算法 + 数据结构 = 程序”。

20. 理查德·卡普（Richard M. Karp）

贡献领域：算法理论，尤其是 NP- 完全性理论。
获奖年份：1985 年。

主要贡献有两点：其一，对计算复杂性理论中的术语进行了规范和统一。把
有多项式时间算法的问题命名为 P 类问题，就是卡普在这篇论文中首次采用的，
已为学术界所接受并普遍采用，这为学术交流带来了很大的好处。其二，卡普在
刻画 NP 类中的“最困难”问题类时，提出了与史提芬·古克归约不同的另一种归
约方法，称作“多项式时间多一归约”，有时直接把它叫做“卡普归约”。

21. 约翰·霍普克罗夫特（John Hopcroft）

罗伯特·塔扬（Robert Tarjan）

贡献领域：算法和数据结构的设计与分析。
获奖年份：1986 年。

罗伯特·塔扬以在数据结构和图论上的开创性工作而闻名。他的一些著名的
算法包括，塔扬最近共同祖先离线算法，塔扬的强连通分量算法以及 Link-Cut-
Trees 算法等。其中 Hopcroft-Tarjan 平面嵌入算法是第一个线性时间平面算法。
塔扬也开创了重要的数据结构，如斐波纳契堆和 splay 树（splay 发明者还有
Daniel Sleator）。另一项重大贡献是分析了并查集。他是第一个证明了计算反阿克

曼函数的乐观时间复杂度的科学家。
霍普克罗夫特的研究领域是理论计算机科学。他将计算机科学萌芽阶段的零
散结果总结为具有整体性的系统知识，提出用渐近分析作为衡量算法性能的主要

指标，成为当今计算机科学的一大支柱。
22. 约翰·科克（John Cocke）

贡献领域：编译理论，大型系统的体系结构，及精简指令集（RISC）计算机

• 288 •