理查德·卡普

1985年图灵奖得主

理查德·卡普（Richard Karp），1935年1月3日出生于美国马萨诸塞州波士顿，1985年图灵奖得主，美国国家科学院院士，美国国家工程院院士，加州大学伯克利分校教授。

人物经历

1935年1月3日，理查德·卡普出生于美国马萨诸塞州波士顿。

1955年，获得哈佛大学数学学士学位。

1956年，获得哈佛大学应用数学硕士学位。

1959年，获得哈佛大学应用数学博士学位。

1959年—1968年，任职于IBM（国际商业机器公司）沃森研究中心。

1968年—1994年，担任加州大学伯克利分校计算机科学和工业工程与运筹学教授。

1973年—1975年，担任加州大学伯克利分校电气工程与计算机科学系计算机科学副主席。

1980年，当选为美国国家科学院院士。

1980年—1994年，担任加州大学伯克利分校数学系教授。

1985年，获得图灵奖。

1985年—1986年，担任伯克利数学科学研究所计算复杂性项目联合主席。

1988年—1995年，担任美国加州伯克利国际计算机科学研究所研究员。

1992年，当选为美国国家工程院院士。

1999年，被任命为加州大学伯克利分校计算机科学、数学和生物工程教授，同年被任命为美国加州伯克利国际计算机科学研究所研究员。

2001年—2003年，担任美国数学及其应用研究所理事会主席。

2001年—2004年，担任美国国家科学院第34分部创始主席。

2012年—2017年，创建西蒙斯计算理论研究所并担任所长。

主要成就

科研成就

理查德·卡普对算法理论做出了持续贡献，开发了网络流和其他组合优化问题的有效算法，用算法效率的直观概念识别多项式时间可计算性。对np完备性理论的贡献：引入了标准的方法来证明问题是np完全的，致使较多理论和实际问题得以识别。

20世纪70年代早期，理查德·卡普与埃德蒙兹和约翰·霍普克罗夫特合作，为两个有关网络的问题开发了有效的算法：二部图匹配问题，关于如何匹配网络中的节点对，以及网络流问题，关于找到通过网络的最佳路径。在20世纪80年代，为了解决为什么许多np完全问题似乎很容易在来自现实世界的输入上解决的问题，他开发了算法的概率分析领域，该领域旨在了解算法的平均预期性能如何。他还在研究包含随机性的算法，以及在点对点网络中定位数据的问题上做出了基础性贡献。在20世纪90年代初，理查德·卡普进入了计算生物学领域并做出了贡献。

据2023年9月AMiner平台数据，理查德·卡普已发表学术论文336篇，论文被引58263次，H-Index：93。

[1]Sylvia Ratnasamy，Paul Francis，Mark Handley，Richard M Karp，Scott Shenker.A scalable content-addressable network[J].Computer Communication Review，2001.

[2]David Culler，Richard Karp，David Patterson，Abhijit Sahay，Klaus Erik Schauser，Eunice Santos，Ramesh Subramonian，Thorsten von Eicken.LogP： towards a realistic model of parallel computation[J].ACM Transactions on Accessible Computing （TACCESS），1993.

[3]John E. Hopcroft，Richard M. Karp.An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs[J].SIAM Journal on Computing，1973.

[4]Jack Edmonds，Richard M. Karp.Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems[J].Journal of the ACM，1972.

[5]Michael Held，Richard M. Karp.The traveling-salesman problem and minimum spanning trees： Part II[J].Mathematical Programming， Series B，1971.

人才培养

理查德·卡普于1986年获得加州大学伯克利分校杰出教学奖。

据2023年9月美国计算机协会数据，理查德·卡普在加州大学伯克利分校和华盛顿大学指导了近40名博士生。

荣誉表彰

社会任职

理查德·卡普1964年至1965年担任密歇根大学电气工程客座副教授，1995年至1999年担任华盛顿大学计算机科学教授和分子生物技术兼职教授。

个人生活

理查德·卡普喜欢阅读和下棋。他对数学从小就喜爱，小时候，他喜欢随机分析棒球，或者在头脑中计算四位数的乘法，十年级时，他曾假装生病，待在家里解决几何问题。

人物评价

理查德·卡普是算法设计、分析和计算复杂性领域的世界领导者（Richard Karp is a world leader in algorithm design and analysis and computational complexity）。（富兰克林研究所评）

78岁的理查德·卡普仍然保持着活跃的研究生涯，在塑造计算机科学这门学科方面，他所做的贡献几乎比其他任何理论计算机科学家都要多（Nearly 60 years later， Karp， who at 78 still maintains an active research career， has done more than almost any other theoretical computer scientist to shape the discipline）。（西蒙斯基金会于2013年评）

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省