Richard M. Karp

Richard M. Karp
Richard Karp 2009

Richard Manning Karp (* 3. Januar 1935 in Boston, Massachusetts) 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.

Inhaltsverzeichnis

Biographie

Nach der Boston Latin School besuchte er die Harvard University, wo er 1955 seinen Bachelor in Literatur, 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) und Rajeev Motwani (Gödel-Preis 2001).

Auszeichnungen (Auswahl)

Schriften

Weblinks

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

Wikimedia Foundation.

См. также в других словарях:

  • Richard M. Karp — Richard Karp Richard Karp, né en 1935 à Boston dans le Massachusetts, est un informaticien américain, connu pour ses recherches en théorie de la complexité. Il a reçu le prix Turing en 1985 pour ces travaux. Né de Abraham et Rose Karp à …   Wikipédia en Français

  • Richard Karp — Richard Manning Karp, né en 1935 à Boston dans le Massachusetts, est un informaticien américain, connu pour ses recherches en théorie de la complexité. Il a reçu le prix Turing en 1985 pour ces travaux. Né de Abraham et Rose Karp à Boston, Karp a …   Wikipédia en Français

  • Richard Karp — Saltar a navegación, búsqueda Richard Karp Richard Manning Karp (Boston, (Estados Unidos), 3 de enero de 1935) es un científico de la computación, conocido por su investigación en teoría de algoritmos, por lo que recibió el …   Wikipedia Español

  • Karp — ist der Familienname folgender Personen: Bob Karp (1911–1975), amerikanischer Comictexter Carol Karp (geborene Carol van der Velde; 1926–1972), US amerikanische mathematische Logikerin Guido Karp (* 1963), deutscher Fotograf Marcia Karp (* 1942) …   Deutsch Wikipedia

  • Richard Karp — ist der Name folgender Personen: Richard A. Karp (* 1944), amerikanischer Informatiker Richard M. Karp (* 1935), amerikanischer Informatiker Diese Seite ist eine Begriffsklärung zur Unterscheidung mehrerer mit demselben Wort bezeichne …   Deutsch Wikipedia

  • Richard Karp — Infobox Scientist name = Richard Manning Karp image width = caption = birth date = January 3, 1935 birth place = Boston, Massachusetts death date = death place = residence = citizenship = nationality = American ethnicity = field = Computer… …   Wikipedia

  • Karp-Rabin-Algorithmus — Der Rabin Karp Algorithmus ist ein Suchalgorithmus für Texte, der von Michael O. Rabin und Richard M. Karp entwickelt wurde. Der Algorithmus sucht nach einem Muster, z. B. einer Zeichenkette, innerhalb einer anderen Zeichenkette mit Hilfe von… …   Deutsch Wikipedia

  • Karp-Lipton theorem — The Karp–Lipton theorem in complexity theory states that if the boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then :Pi 2 , = Sigma 2 , and therefore mathrm{PH} , = Sigma 2 ,.That… …   Wikipedia

  • Karp's 21 NP-complete problems — One of the most important results in computational complexity theory was Stephen Cook s 1971 demonstration of the first (practically relevant) NP complete problem, the boolean satisfiability problem. [cite book|author = Stephen Cook|year =… …   Wikipedia

  • Richard J. Lipton — Infobox Scientist image width = 150px name = Richard J. Lipton box width = birth date = Sept 6, 1946 birth place = death date = death place = residence = citizenship = nationality = ethnicity = field = computer science work institutions = Yale… …   Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»