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 |
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) |
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.
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 .
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 .
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. ""