Richard Manning Karp (* 3. Januar 1935 in Boston) ist ein amerikanischer Informatiker. Er ist verantwortlich für bedeutende Erkenntnisse in der Komplexitätstheorie. 1985 erhielt er für seine Forschungsarbeit auf dem Gebiet der Theorie der Algorithmen den Turing Award, 2008 erhielt er den Kyoto-Preis.

Leben

Nach der Boston Latin School besuchte er die Harvard University, wo er 1955 seinen Bachelor in Mathematik, 1956 seinen Master in Mathematik und 1959 seinen Ph.D. in Angewandter Mathematik erwarb. Anschließend arbeitete er bis 1968 im IBM Thomas J. Watson Research Center. Daneben war er 1962 auf Teilzeitbasis wissenschaftlicher Assistent an der New York University, 1964 bis 1965 außerordentlicher Gastprofessor für Elektrotechnik an der University of Michigan, 1965 bis 1968 außerordentlicher Gastprofessor und ordentlicher Gastprofessor für Elektrotechnik am Polytechnic Institute of Brooklyn (in Teilzeit) und 1967 bis 1968 außerordentlicher Professor für Industrial Engineering und Management Engineering an der Columbia University (in Teilzeit). 1968 wurde er Professor für Informatik, Mathematik und Operations Research an der University of California, Berkeley. Von einer vierjährigen Periode als Professor an der University of Washington (1995 bis 1999 als Professor für Informatik und Lehrbeauftragter für molekulare Biotechnologie) abgesehen, blieb er seither in Berkeley, wo er neben der Universität auch am International Computer Science Institute und zeitweise auch am Mathematical Sciences Research Institute tätig ist bzw. war.

Karp gehört oder gehörte dem redaktionellen Beirat zahlreicher Zeitschriften an, darunter das Journal of Computer and System Sciences und die Proceedings of the National Academy of Sciences, an. Daneben war er im Fachbeirat des Max-Planck-Instituts für Informatik und beriet IBM Research, Hewlett-Packard, die Computer Professionals for Social Responsibility, das International Institute for Applied Systems Analysis und das Center for Discrete Mathematics and Theoretical Computer Science. Er war im Aufsichtsrat des Weizmann-Instituts für Wissenschaften und des Institute for Mathematics and its Applications sowie im Vorstand des Miller Institute for Basic Research in Science und leitete u. a. die Computer Science Planning Group des National Research Council und die Sektion Computer and Information Sciences der National Academy of Sciences.

1971 entwickelte Karp mit Jack Edmonds den Edmonds-Karp-Algorithmus zur Lösung des Max-Flow-Problems in Netzwerken. 1972 veröffentlichte er einen Artikel, in dem er die NP-Vollständigkeit einer Reihe von graphentheoretischen Problemen nachwies, darunter das Hamiltonkreisproblem, das Cliquenproblem und das Rucksackproblem. Diese wurden bekannt als Karps 21 NP-vollständige Probleme. 1973 entwickelte er mit John E. Hopcroft den Algorithmus von Hopcroft und Karp zur Bestimmung einer größten Paarung in bipartiten Graphen. 1987 entwickelte er gemeinsam mit Michael O. Rabin den Rabin-Karp-Algorithmus zur String-Suche. Zu seinen Forschungsschwerpunkten gehören kombinatorische und parallele Algorithmen, Bioinformatik und Netzwerke.

Zu Karps rund 40 Doktoranden gehören Narendra Karmarkar (Fulkerson-Preis 1988), Phillip Gibbons (Paris-Kanellakis-Preis 2019) und Rajeev Motwani (Gödel-Preis 2001).

Auszeichnungen (Auswahl)

Schriften

Commons: Richard Karp – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

  1. ↑ Frederick W. Lanchester Prize. informs.org (Institute for Operations Research and the Management Sciences), archiviert vom Original am 2. Oktober 2015; abgerufen am 16. Februar 2016 (englisch).
  2. ↑ Honorary Degrees Awarded Since 1954 - Senate. carleton.ca, abgerufen am 12. März 2015.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.