:Not, der mit Richard A. Karp, einem der Entwickler von TCP verwirrt ist.

Richard Manning Karp (geboren am 3. Januar 1935) ist ein Computerwissenschaftler und rechenbetonter Theoretiker an der Universität Kaliforniens, Berkeley, der für die Forschung in der Theorie von Algorithmen bemerkenswert ist, für die er einen Turing-Preis 1985, Die Medaille von Benjamin Franklin in der Informatik und Erkenntnistheorie 2004 und dem Kyoto Preis 2008 erhalten hat.

Lebensbeschreibung

Geboren Abraham und Rose Karp in Boston, Massachusetts, hat Karp drei jüngere Geschwister: Robert, David und Carolyn. Er hat Universität von Harvard aufgewartet, wo er sein Vordiplom 1955, sein Magisterabschluss 1956 und sein Dr. in der angewandten Mathematik 1959 erhalten hat.

Er hat angefangen, am Forschungszentrum von Thomas J. Watson von IBM zu arbeiten. 1968 ist er Professor der Informatik, Mathematik und Operationsforschung an der Universität Kaliforniens, Berkeley geworden. Abgesondert von einer 4-jährigen Periode als ein Professor an der Universität Washingtons ist er an Berkeley geblieben. Von 1988 bis 1995 und 1999 zur Gegenwart er ist auch ein Forscher am Internationalen Informatik-Institut in Berkeley gewesen, wohin er zurzeit Algorithms Group führt.

Richard Karp wurde dem Nationalen Orden der Wissenschaft verliehen, und war der Empfänger des Preises von Harvey von Technion und der 2004-Medaille von Benjamin Franklin in der Informatik und Erkenntnistheorie für seine Einblicke in die rechenbetonte Kompliziertheit. 1994 wurde er als ein Gefährte der Vereinigung eingeweiht, um Maschinerie Zu schätzen. Er ist der Empfänger von mehreren Ehrengraden.

Arbeit

Er hat viele andere wichtige Entdeckungen in der Informatik und Operationsforschung im Gebiet von kombinatorischen Algorithmen gemacht. Seine aktuellen Hauptforschungsinteressen schließen bioinformatics ein.

1971 er co-developed mit Jack Edmonds der Algorithmus von Edmonds-Karp, für das Max-Fluss-Problem in Netzen, und 1972 zu beheben, hat er eine merkliche Zeitung in der Kompliziertheitstheorie veröffentlicht, "Reducibility Unter Kombinatorischen Problemen", in dem er 21 Probleme bewiesen hat, NP-complete zu sein.

1973 haben er und John Hopcroft den Algorithmus von Hopcroft-Karp, dennoch die schnellste bekannte Methode veröffentlicht, um maximalen cardinality matchings in zweiteiligen Graphen zu finden.

1980, zusammen mit Richard J. Lipton, hat Karp den Lehrsatz von Karp-Lipton bewiesen (der beweist, dass, wenn GESESSEN, durch Stromkreise von Boolean mit einer polynomischen Zahl von Logiktoren, dann die polynomischen Hierarchie-Zusammenbrüche zu seinem zweiten Niveau gelöst werden kann).

1987 er co-developed mit Michael O. Rabin der Schnur-Suchalgorithmus von Rabin-Karp.

Turing Preis

Sein Zitat für den Turing-Preis war wie folgt:

:For seine ständigen Beiträge zur Theorie von Algorithmen einschließlich der Entwicklung von effizienten Algorithmen für das Netz fließen und andere kombinatorische Optimierungsprobleme, die Identifizierung der polynomisch-maligen Berechenbarkeit mit dem intuitiven Begriff der algorithmischen Leistungsfähigkeit, und, am meisten namentlich, Beiträge zur Theorie der NP-Vollständigkeit. Karp hat die jetzt normale Methodik eingeführt, um Probleme zu beweisen, NP-complete zu sein, der zur Identifizierung von vielen theoretischen und praktischen Problemen als rechenbetont schwierig seiend geführt hat.

Links

• Zeitschrift ACM Crossroads, die von Richard Karp interview/bio ist
• Die Hausseite von Karp an Berkeley