Karp, Richard Manning

Richard Manning Karp
engelsk  Richard Manning Karp
Fødselsdato 3. januar 1935( 1935-01-03 ) (87 år)
Fødselssted
Land
Videnskabelig sfære teori om algoritmer og bioinformatik
Arbejdsplads
Alma Mater
videnskabelig rådgiver Anthony Oettinger [d] [1]
Præmier og præmier Turing Award ( 1985 ) von Neumann teoretiske pris ( 1990 ) Hundredårsmedalje for Graduate School of Arts and Sciences, Harvard University [d] Harvey Award ( 1998 ) Fulkerson-prisen ( 1979 ) US National Medal of Science European Association for Theoretical Computer Science Prize [d] ( 2000 ) Benjamin Franklin-medalje ( 2004 ) Kyoto Advanced Technology Prize [d] ( 2008 ) Benjamin Franklin-medalje ( 2004 ) Dixon-prisen for væsentligt bidrag til udviklingen af ​​videnskab [d] ( 2009 ) æresdoktor i Technion [d] æresdoktor fra Weizmann Instituttet [d] Kyoto-prisen Fello ACM ( 1994 ) medlem af Society for Industrial and Applied Mathematics [d] ( 2009 ) Frederick W. Lanchester Prize [d] ( 1977 ) æresdoktor fra ETH Zürich [d]
 Mediefiler på Wikimedia Commons

Richard Manning Karp ( eng.  Richard Manning Karp ; født 3. januar 1935 , Boston , USA ) er en amerikansk videnskabsmand inden for computerteori, vinder af Turing-prisen .

Medlem af US National Academy of Sciences (1980) [2] , US National Academy of Engineering (1992) [3] , udenlandsk medlem af det franske videnskabsakademi (2002) [4] .

Biografi

Richard Karp blev født i Boston , staten Massachusetts . _ _ Med ham voksede to yngre brødre Robert og David (f. 1944, sociolog) og lillesøster Carolyn op.

Efter at have afsluttet gymnasiet gik Richard ind på Harvard University , hvor han modtog en bachelorgrad ( 1955 ), en kandidatgrad i naturvidenskab ( 1956 ) og til sidst en Ph.D. -grad i anvendt matematik i 1959 .

Efter endt uddannelse arbejdede Richard Karp i 9 år på IBM Research Center ( Thomas Watson Research Center ). I 1968 modtog han et professorat i datalogi, matematik og operationsforskning fra University of California, Berkeley , hvor han forbliver den dag i dag, bortset fra en fire-årig pause fra arbejdet ved University of Washington (i Seattle ).

Bidrag

I 1971 udviklede Karp sammen med Jack Edmonds en algoritme til at finde den maksimale flow i et transportnetværk , opkaldt efter dem. Et år senere udgav Karp sit papir "Reducibility Among Combinatorial Problems", [6] hvori han beviste NP-fuldstændighed for 21 problemer.

I 1973 udgav Karp og John Hopcroft Hopcroft-Karp algoritmen , som er den hurtigste kendte metode til at finde maksimale elementantal korrespondancer i todelte grafer [7] .

I 1980 beviste Karp sammen med Richard J. Lipton Karp-Lipton-sætningen .

I 1987 udviklede Karp sammen med Michael Rabin understrengssøgningsalgoritmen opkaldt efter dem [7] .

Richard Karp gjorde mange andre vigtige opdagelser inden for datalogi og operationsforskning inden for kombinatoriske algoritmer . I dag er han engageret i forskning i bioinformatik [7] .

Anerkendelse

Litteratur

Se også

Links

Noter

  1. ↑ Matematisk genealogi  (engelsk) - 1997.
  2. ↑ Karp, Richard Manning på US National Academy of Sciences  hjemmeside
  3. ↑ Dr. Richard M. Karp Arkiveret 2. maj 2019 på Wayback Machine 
  4. ↑ Richard Karp Arkiveret 8. september 2019 på Wayback Machine  (FR)
  5. ↑ Moderens familie kom fra byen Eishishki i Grodno-provinsen .
  6. ↑ "Reducibility Among Combinatorial Problems" Arkiveret 29. juni 2011 på Wayback Machine , R. Karp , 1972 
  7. ↑ 1 2 3 Richard M.  Karp . - Biografi. Dato for adgang: 8. december 2014. Arkiveret fra originalen 19. februar 2015.
  8. ↑ Statistik - Mest citerede forfattere i datalogi . Hentet 27. februar 2009. Arkiveret fra originalen 1. maj 2012.
  9. ↑ Richard M. Karp - The Franklin Institute Awards - Laureate Database Arkiveret 1. juni 2010 på Wayback Machine
  Gå til Wikidata-elementet  Tematiske steder
Ordbøger og encyklopædier
 Turing prisvindere