Richard Karp

Richard Karp Bild in der Infobox. Richard Karp im Jahr 2009. Biografie
Geburt 3. Januar 1935
Boston
Name in der Muttersprache Richard Manning Karp
Staatsangehörigkeit amerikanisch
Ausbildung Harvard
Harvard School of Engineering und angewandte Wissenschaften ( in )
University of California, Berkeley
Aktivitäten Mathematiker , Informatiker , Universitätsprofessor
Andere Informationen
Arbeitete für Universität von Kalifornien in Berkeley , Universität von Washington
Bereiche Berechenbarkeitstheorie ( in ) , Bioinformatik
Mitglied von Vereinigung für Computermaschinen
Amerikanische Akademie der Künste und Wissenschaften
Amerikanische Philosophische Gesellschaft Amerikanische
Vereinigung zur Förderung der Wissenschaft
Amerikanische Akademie der Wissenschaften (1980)
Nationale Akademie der Ingenieurwissenschaften der Vereinigten Staaten (1992)
Akademie der Wissenschaften (2002)
Supervisor Anthony Oettinger
Auszeichnungen Turing-Preis (1985)
Primärarbeiten
Ein einfacher Algorithmus zum Auffinden häufiger Elemente in Strömen und Beuteln ( d )

Richard Manning Karp (geboren am3. Januar 1935in Boston in Massachusetts ) ist ein amerikanischer Forscher, der für seine Forschungen zur kombinatorischen Optimierung und Komplexitätstheorie bekannt ist . Er erhielt den Turing - Preis in 1985 für seine Arbeit.

Biografie

Richard Karp ist der Sohn von Abraham und Rose Karp.

Er trat die Harvard University , wo er erhielt Bachelor-Abschluss in 1955 , seinen Grad des Meisters in 1956 , und sein Ph.D. in der angewandten Mathematik in 1959 .

Anschließend arbeitete er für IBM im Thomas J. Watson Research Center.

In 1968 wurde er Professor für Informatik und Mathematik an der University of California in Berkeley , wo er danach blieb, mit Ausnahme für einen Zeitraum von vier Jahren als Professor an der University of Washington .

Er war unter anderem der Thesis Director von Narendra Karmarkar , Noam Nisan und Rajeev Motwani .

Funktioniert

Richard Karp hat hauptsächlich in Algorithmen und Komplexitätstheorie gearbeitet . Zu seinen wichtigen Beiträgen gehören die folgenden.

Derzeit interessiert er sich für Bioinformatik .

Auszeichnungen und Anerkennung

Beim Turing-Preis wurde er wie folgt zitiert: „Für seine fortgesetzten Beiträge zur Algorithmus-Theorie, einschließlich der Entwicklung effizienter Algorithmen für Netzwerke und anderer kombinatorischer Optimierungsprobleme, der Identifizierung der Berechenbarkeit in Polynomzeit mit dem intuitiven Begriff des effizienten Algorithmus und darüber hinaus Alles in allem seine Beiträge zur Theorie der NP-Vollständigkeit . Karp führte die jetzt klassische Methodik ein, um zu beweisen, dass ein Problem NP-vollständig ist, wodurch es möglich wurde, viele praktische und theoretische Probleme als schwierig zu berechnen zu identifizieren. ""

Quelle

Anmerkungen und Referenzen

  1. https://www.kyotoprize.org/wp/wp-content/uploads/2016/02/24kA_lct_EN.pdf
  2. "  Turing Prize Citation  " über die Association for Computing Machinery
  3. (en) „  Richard Karp  “ auf der Website des Mathematics Genealogy Project
  4. Jack Edmonds und Richard M. Karp , „  Theoretische Verbesserungen der algorithmischen Effizienz bei Netzwerkflussproblemen  “, Journal of the ACM , Association for Computing Machinery (ACM), vol.  19, n o  21972, p.  248–264 ( DOI  10.1145 / 321694.321699 )
  5. (in) Richard M. Karp Reduzierbarkeit bei kombinatorischen Problemen . In Complexity of Computer Computations , Proc. Nett. IBM Thomas J. Watson Res. Zentrum, Yorktown Heights, NY. New York: Plenum, S. 85-103. 1972.
  6. John Hopcroft und Richard Karp, „  Ein n 5/2- Algorithmus für maximale Übereinstimmungen in zweigeteilten Graphen  “, SIAM Journal on Computing , vol.  2, n o  4, 1973, p.  225-231 ( DOI  10.1137 / 0202019 )
  7. Richard M. Karp und Richard J. Lipton, „Einige Verbindungen zwischen ungleichmäßigen und einheitlichen Komplexitätsklassen“ , im Symposium on Theory of Computing , 1980( DOI  10.1145 / 800141.804678 ) , p.  302-309.
  8. Richard M. nom2 = Rabin Karp , „  Effiziente randomisierte Mustervergleichsalgorithmen  “, IBM Journal of Research and Development , vol.  31, n o  2März 1987, p.  249–260 ( DOI  10.1147 / rd.312.0249 , online lesen ).
  9. "  Richard-Karp-Preis  " am Institut für Operations Research und Management Sciences

Externe Links