今天我们要介绍一位被誉为“三栖学者”的传奇人物——理查德·卡普（Richard Manning Karp）。他在1985年获得了备受瞩目的图灵奖。 理查德·卡普之所以被称为“三栖学者”，是因为他在多个学科领域都有着深厚的造诣。他在加州大学伯克利分校同时担任电气工程和计算机系、数学系以及工业工程和运筹学系的教授。这种跨学科的聘任在美国大学中实属罕见。卡普获得图灵奖，是因为他在算法设计与分析、计算复杂性理论以及随机化算法等诸多方面作出了开创性的贡献。 理查德·卡普于1935年1月3日出生在马萨诸塞州波士顿的一个犹太裔家庭。父亲是亚伯拉罕·卡普（Abraham Karp），母亲是萝丝·卡普（Rose Karp）。他有三个弟妹，分别是罗伯特（Robert）、大卫（David）和卡罗琳（Carolyn）。卡普在当时主要为犹太人居住的波士顿多尔切斯特社区的一间小公寓里长大。 卡普的父母都是哈佛大学的毕业生。母亲在参加夜校课程后，最终在57岁时获得了哈佛大学的学位。父亲在哈佛大学毕业后，曾有就读医学院的梦想，但由于无力支付学费，最终成为了一名数学教师。卡普本人也就读于哈佛大学，1955年获得学士学位，1956年获得硕士学位，1959年获得应用数学博士学位。此后，他开始在IBM的托马斯·J·沃森研究中心工作。 他从小就展现出广泛的兴趣和过人的聪明才智。在哈佛大学期间，他文理兼修，先后于1955年获得文学学士学位，1956年获得理科硕士学位。随后，他在哈佛大学计算实验室攻读博士，并于1959年取得应用数学博士学位。完成学业后，他在IBM位于Yorktown Heights的沃森研究中心工作了近十年。 20世纪50年代末至60年代，是计算机科学的创立时期，计算机应用开始受到社会重视并逐渐普及。卡普在IBM期间，深入研究了与实际应用密切相关的一系列数学问题，如路径问题、背包问题、覆盖问题、匹配问题、分区问题和调度问题等，取得了许多卓越的成果。这些问题的一个共同特点是，当图中增加一个节点时，需要考察的可能解的数目急剧增加，形成所谓的“组合爆炸”（combinatorial explosion），使计算机的计算量大幅增加，甚至难以实现。 以路径问题中著名的旅行推销员问题为例，在卡普之前，最好的结果是由Rand公司的丹齐格、福格申和约翰逊通过手工和计算机结合的方法求得的49个城市的最佳路线。卡普与他的同事海尔特经过反复研究，提出了一种新的“分枝限界法”（branch-and-bound method）。这种方法使得旅行推销员能周游的城市数达到65个，打破了由Rand公司保持的记录。 分枝限界法是一种构造性的探索方法，能够在整个允许的解空间中进行最优搜索。其核心在于对解集合反复进行分枝，每次分枝时计算最优解的界限。如果某个子集的界限不优于已知的允许解，则抛弃该子集；否则继续分枝，直到子集仅含一个解。尽管分枝限界法本质上是一种策略而非具体算法，但由于其在解决许多问题中非常实用，常被称为“分枝限界算法”，几乎在所有算法书籍中都有介绍。 卡普还研究过最大网络流问题。这个问题涉及一个包含起点和终点的有向图，其中的每条边都有一定的容量限制。可以将这些边想象成管道，在其中流过某种物质，需要求出从起点到终点的最大物流量。这个问题对输油管道、输气管道、公路网、通信网的设计都有重要意义。解决这个问题的第一个算法是福特（L. Ford）和福克森（O. R. Fulkerson）在1956年提出的。其算法要点是从流量0开始，反复寻找所谓的增量路径，这些路径能够注入尽可能大的流量，同时保证所有的边不超出饱和状态，直至无法找到新的增量路径为止。这个算法在多数情况下是有效的，但在某些特殊情况下效率低下，甚至无法得出答案。1969年，卡普和埃德蒙兹（J. Edmonds）合作改进了这个算法，他们提出在寻找增量路径时选择包含边数最少的路径，从而大大提高了算法的效率。改进后的算法运行时间与节点数和边数平方的乘积成正比。 在研究旅行推销员问题的过程中，卡普发现，无论对算法进行何种改进，也无论采用何种更高效的新算法，旅行推销员能周游的城市数虽然不断增加（包括后来采用“多面体组合学”的方法将其转化为线性规划问题，使周游城市数超过300），但解题所需的时间总是问题规模（在这里是城市数）的函数，并且以指数方式增长。这引起了卡普的深思，促使他深入计算复杂性领域进行研究。1967年，正好以色列学者、计算复杂性理论的先驱拉宾（M. Rabin，1976年图灵奖获得者）从希伯莱大学来到IBM沃森研究中心作客座研究员，并与卡普住在同一公寓大楼。他们成了朋友，经常一起上下班，一起散步，拉宾在计算复杂性理论方面的深刻见解给了卡普许多启发。 1968年，卡普离开IBM前往加州大学伯克利分校工作。这里是计算机科学理论的又一个研究中心，库克（S. Cook，1982年图灵奖获得者）、布卢姆（M. Blum，1995年图灵奖获得者）等知名学者当时都在那里，学术气氛十分浓厚。布卢姆是计算复杂性理论的主要奠基人之一，库克则于1971年最早提出“NP完全性”问题。在这样的环境下，卡普对计算复杂性问题的研究日益深入。1972年，卡普发表了他那篇著名的论文《组合问题中的可归约性》（Reducibility Among Combinatorial Problems，见R. E. Miller和J. W. Thatcher所编纂，由Plenum出版社出版的《计算机计算的复杂性》（Complexity of Computer Computations）一书）。卡普的论文发展和加强了由库克提出的“NP完全性”理论。尤其是，库克仅证明了命题演算的可满足问题是NP完全的，而卡普则证明了从组合优化中引出的许多经典问题，包括背包问题、覆盖问题、匹配问题、分区问题、路径问题、调度问题等，都是NP完全问题。只要证明其中任一个问题属于P类，就可以解决计算复杂性理论中最大的一个难题，即P=NP问题。这就是卡普论文的主要贡献和意义。 此外，这篇论文还有其他贡献。其一，卡普规范和统一了计算复杂性理论中的术语，将有多项式时间算法的问题命名为P类问题，这一术语在这篇论文中首次使用，现在已为学术界广泛接受并普遍采用，极大地促进了学术交流。其二，卡普在刻画NP类中的“最困难”问题时，提出了一种不同于库克归约的多项式时间归约方法，称为“多项式时间多一归约”，有时直接被称为“卡普归约”。 除了前述贡献之外，理查德·卡普在组合优化算法的概率分析和随机化算法方面也取得了重要成果。近年来，卡普还致力于并行算法的研究，并有所创新。1996年11月，卡普与他在伯克利的同事库勒（D．Culler）等人在《ACM通讯》（Communications of ACM）上发表了一篇论文，提出了一种名为LogP的并行算法实用模型。这种模型的优点在于能够客观科学地概括分布存储器并行系统的通信开销，因而引起了学术界的广泛关注。我国中科院计算所的学者基于LogP模型设计并实现了一种并行计算模拟器，取得了良好的效果，详情可参阅《计算机研究与发展》1997年9月刊。 卡普因其多方面的贡献，获得了许多荣誉与奖项。除了图灵奖之外，他还在1978年获得了美国运筹学与工业管理学会颁发的兰彻斯特奖（Lanchester Prize），1979年获得美国数学会授予的富尔克森奖（Fulkerson Prize），1990年获得美国运筹学会的冯·诺伊曼理论奖（von Neumann Theory Prize），1995年获得巴贝奇奖（Babbage Award），1996年获得美国科学院授予的全国科学奖章（National Medal of Science）。早在1980年，卡普就已当选为美国科学院院士。 卡普是在1985年10月于科罗拉多州丹佛召开的ACM年会上接受图灵奖的。他的图灵奖演讲题为“组合论、复杂性和随机性”（Combinatorics, Complexity, and Randomness），这是对上述课题的精彩综述，并且提供了一张有关组合优化和计算复杂性理论发展过程的年表，涵盖了从1900年德国数学家希尔伯特提出“23个数学难题”开始，到20世纪80年代中期的进展和成果，具有很高的参考价值。 目前，他还建在，今年89岁。祝老爷子长命百岁，或者长命120岁。

Niklaus Wirth 是一位著名的编程语言设计师。只要学过一点计算机的人，应该都听过“数据结构 + 算法 = 程序”这个公式吧？这个公式的提出者正是瑞士的计算机科学家尼克劳斯·沃思（Niklaus Wirth），他不仅发明了多种对编程界影响深远的语言，还提出了结构化程序设计的革命性概念。凭借这些成就，他在1984年获得了图灵奖，是目前唯一一位获得这个奖项的瑞士学者。 Wirth 的母校是苏黎世联邦理工学院（ETH），在欧洲乃至全球都有很高的声誉。1967年，他回到母校，1968年成为教授，一直到1999年退休。在 ETH 期间，他发明了多种编程语言，其中最著名的就是 Pascal。 尼克劳斯·沃思（Niklaus Wirth）于1934年2月15日出生在瑞士北部靠近苏黎世的温特图尔（Winterthur）。他的父亲瓦尔特是一位地理学教授。沃思从小就喜欢动手动脑，他最大的爱好是组装飞机模型。中学毕业后，沃思进入了享有盛名的苏黎世联邦理工学院（ETH），并于1958年获得学士学位。 之后，沃思跨越大西洋，前往加拿大的拉瓦尔大学深造，这所大学位于魁北克，与圣劳伦斯河对岸的魁北克市隔河相望。他于1960年获得了硕士学位。随后，沃思又移居美国加利福尼亚，在加州大学伯克利分校继续深造，并于1963年获得博士学位。 毕业后，沃思受聘于刚刚成立的斯坦福大学计算机科学系。斯坦福大学以其高门槛著称，那为何会看中这位来自欧洲的小伙子呢？原来在20世纪50年代末和60年代初，沃思已经在计算机领域取得了相当引人注目的成就。在苏黎世联邦理工学院时，他曾听过瑞士计算机先驱斯帕塞（A.P. Speiser）的课，并使用过由斯帕塞开发的计算机ERMETH；在拉瓦尔大学时，他学习了数值分析，并使用过Alvac III E计算机；在伯克利，他先是有机会使用Bendix G-15计算机，后来又参与了为IBM 704开发NELIAC编译器的项目。 在撰写博士论文时，沃思决定对Algol 60语言进行改进，并以此作为自己的研究课题，从而设计了他的第一个编程语言——Euler。尽管Euler在实用性上还有不足，但其学术价值极高，为编译器系统设计奠定了良好的基础。也正因为如此，斯坦福大学对沃思产生了兴趣。同时，国际信息处理联合会（IFIP）也注意到了Euler语言，并邀请沃思参与Algol语言的完善和扩充工作。 在参与Algol语言工作组时，沃思提出了一份建议书，经过霍尔（Tony Hoare）等人的修改和完善后，这份建议书得以通过，这就是后来的Algol W语言。1966年，Algol W在斯坦福大学的IBM 360计算机上成功实现并正式应用。 在这个过程中，还有一个有趣的小插曲：当时IBM 360只提供汇编语言和FORTRAN语言，沃思和他的学生认为这两者都不适合作为设计编译器的工具。于是，沃思花了两个星期时间设计了一种新的语言，用于描述Algol编译器，并用了四个月时间在宝来公司的B-5000计算机上完成了交叉编译程序，而他的一个学生则将其移植到IBM 360上。这些额外的工作大大加快了Algol W编译器的开发，同时催生了一个新的语言——PL 360。虽然PL 360最初只是作为辅助工具开发的，但它后来在许多地方得到了应用，取得了意想不到的成功。 Algol W和PL 360的成功奠定了尼克劳斯·沃思（Niklaus Wirth）作为世界级编程语言大师的地位，使他一举成名。但沃思是个具有强烈爱国心的人，成名后，他谢绝了斯坦福大学的挽留，于1967年回到祖国瑞士，先在苏黎世大学任职，但第二年便回到了他的母校苏黎世联邦理工学院（ETH）。 在ETH期间，沃思设计并实现了PASCAL语言（Philips Automatic Sequence CAlculator Language的缩写），这在CDC 6600计算机上开发成功。PASCAL在数据结构和过程控制结构方面都有很多创新。对于前者，除了常见的整型、实型和布尔型数据外，PASCAL还增加了字符型、子域类型、记录结构类型、文件类型、集合类型和指针类型；对于后者，除了保留了无条件转移的GOTO语句外，还增加了if-then-else、case、while、repeat和for等多种控制结构，还允许使用with语句处理记录变量的分量。可以说，现代编程语言中常用的数据结构和控制结构大多数都是由PASCAL语言奠定基础的，因此它在编程语言的发展史上具有承上启下的重要里程碑意义。 有趣的是，沃思开发PASCAL的初衷是为了有一个适合教学的语言，并没有想到它会在商业上得到广泛应用。但一经推出，由于它的简洁明了以及提供的丰富的数据结构和控制结构，PASCAL为程序员提供了极大的便利与灵活性。此外，它特别适合用于微处理器组成的计算机系统，因而大受欢迎，广泛流传。在C语言问世前，PASCAL是风靡全球、最受欢迎的语言之一，创下了发行拷贝数最多的世界纪录。沃思的学生菲力浦·凯恩（Phillipe Kahn）从ETH毕业后，在美国加利福尼亚州创办了一家软件公司，仅PASCAL一项就卖出了超过100万个拷贝，成为百万富翁。 1971年，沃思基于其在开发编程语言和编程实践中的经验，在4月份的《ACM通讯》（Communications of the ACM）上发表了论文《通过逐步求精方式开发程序》（Program Development by Stepwise Refinement），首次提出了“结构化程序设计”（structured programming）的概念。这个概念的核心是：不要求一步就编写出可执行的程序，而是分若干步进行，逐步求精。第一步编写出的程序抽象度最高，第二步的程序抽象度有所降低……最后一步的程序即为可执行的程序。虽然这种方法看似复杂，实际上却有很多优点，使程序更易读、易写、易调试、易维护，并且更易于保证其正确性和验证其正确性。结构化程序设计方法，又称为“自顶向下”或“逐步求精”法，在程序设计领域引发了一场革命，成为程序开发的标准方法，特别是在后来发展起来的软件工程中得到了广泛应用。有人评价说沃思的结构化程序设计概念“完全改变了人们对程序设计的思维方式”，这并不夸张。1983年1月，ACM在纪念《ACM通讯》创刊25周年时，从其1/4个世纪发表的大量论文中评选出25篇“具有里程碑意义的研究论文”，沃思的这篇论文就是其中之一。 PASCAL的成功和结构化程序设计思想的巨大影响并没有让沃思停下继续研究与开发的脚步。20世纪70年代中期，为适应并发程序设计的需要，沃思成功开发了一个广泛应用的语言——Modula。Modula除了提供并发程序设计功能外，还引入了模块概念（这也是该语言命名为Modula的原因）以及“进程”（process）这一重要概念。Modula特别适合于书写系统程序。 但比Modula更重要的是它的第二个版本Modula-2。1976年，沃思再次赴美，到Xerox公司的Palo Alto研究中心参与Alto计算机的设计与开发工作。Alto是世界上第一个具有图形用户界面的个人计算机系统（可惜Xerox公司没有将其商品化，而Apple公司学去了技术并推出了Macintosh）。沃思回到瑞士后，参考Alto的经验，设计并开发了Lilith个人计算机系统。为了与Lilith的体系结构相配合，沃思决定在Modula的基础上开发新版本，即Modula-2。Modula-2相比Modula，语法更加简洁，更加注重界面设计和模块的可重用性。它有三个编译单元，即程序模块、定义模块和实规模块。在定义模块中，只给出模块外部交互所需的信息，而在实规模块中，则给出模块内部实现的详细信息。这样的安排既提高了可读性，又有助于分别编译。Modula-2在优美性和简洁性上更进一步。Lilith的操作系统、图形软件包、数据库系统、网络协议套件、文件服务器等基本系统和大量应用模块全都用Modula-2开发。世界上已经开发了近百个Modula-2的编译系统，北美和欧洲的许多大学已用Modula-2代替PASCAL作为计算机系本科生的第一门程序设计课程。 Modula-2的标准化工作早在1984年由英国开始进行，ISO则于1987年对其进行标准化，并采用由IBM维也纳实验室提出的VDM-SL和经过沃思本人扩充的BNF（即EBNF）表达语言的语法与语义，在形式化方面达到了新的水平。在Lilith项目中，沃思坚持将计算机体系结构、语言和操作环境三者统一考虑，实行集成化、一体化设计的成功经验是具有革命性的创举，使这个项目在计算机科学史上占有重要地位。 后来，沃思致力于一个新的计划，即Oberon计划。Oberon是一个将程序设计语言和操作系统结合在一起的、面向单用户的个人工作站系统。沃思认为，在因特网日益普及的情况下，未来联网的计算机主要将是个人工作站，因此如何使个人工作站功能更加强大、更加方便使用是一个重要课题。沃思将这个计划命名为Oberon，因为Oberon是希腊神话中的仙境之王和女神Titania的丈夫。沃思的目标是使Oberon语言超越PASCAL和Modula，并设计出功能更强大的操作系统和编译器。1992年，他写了两本书向读者推荐Oberon，由此可见他对这个计划的重视。 ACM不仅在1984年授予沃思图灵奖，还在1987年授予他“计算机科学教育杰出贡献奖”。另一个重要的国际学术组织IEEE也给予过沃思两项荣誉：1983年的Emanual Piore奖和1988年的计算机先驱奖（Computer Pioneer Award）。1992年，加州大学伯克利分校还将沃思命名为“杰出校友”。 沃思是在1984年10月于旧金山举行的ACM年会上接受图灵奖的。他在颁奖典礼上发表了题为“从程序设计语言设计到计算机建造”（From Programming Language Design to Computer Construction）的图灵奖演说，回顾了自己在计算机领域的工作。 在演讲中，沃思强调了程序设计语言简洁性的重要性，并讨论了语言所需的硬件和软件环境（因为他一直很重视语言的实现问题）。他还介绍了设计Modula-2和Lilith的经验，指出第一手经验和选择良好开发工具的无比价值。 我见过的另一个Pascal语言的来历，是布莱兹·帕斯卡尔（Blaise Pascal，1623-1662），法国十七世纪著名的思想家。他一生体弱多病，只活了三十九岁，但他留下了不朽的著作和思想遗产。他的主要著作是《外省通信》和《思想录》。前者被认为是法国古典主义散文的奠基之作，后者则在哲学和宗教领域提供了丰富的探讨，是思想伟大的明证。 帕斯卡尔在《思想录》中有一句名言：“思想形成人的伟大。” 他说：“人不过是一根苇草，是自然界最脆弱的东西；但他是一根能思想的苇草。用不着整个宇宙都拿起武器来才能毁灭他；一口气、一滴水就足以致他死命了。然而，纵使宇宙毁灭了他，人却依然要比致他死命的东西更高贵得多；因为他知道自己要死亡，以及宇宙对他所具有的优势，而宇宙对此却是一无所知。” 帕斯卡尔还说：“能思想的苇草——我应该追求自己的尊严，绝不是求之于空间，而是求之于自己的思想。我占有多少土地都没有用；因为在空间上，宇宙囊括并吞没了我，有如一个质点；但由于思想，我却囊括了宇宙。” 我希望大家能有机会读一下这本书，做一根有思想的苇草。

图灵奖得主