Karp, Richard Manning

Richard Manning Karp
Engleză  Richard Manning Karp
Data nașterii	3 ianuarie 1935( 03.01.1935 ) (87 de ani)
Locul nașterii	Boston , SUA
Țară	STATELE UNITE ALE AMERICII
Sfera științifică	teoria algoritmilor si bioinformatica
Loc de munca	UC Berkeley Universitatea Washington
Alma Mater	Universitatea Harvard Școala de Inginerie și Științe Aplicate de la Harvard [d] UC Berkeley
consilier științific	Anthony Oettinger [d] [1]
Premii și premii	Premiul Turing ( 1985 ) Premiul teoretic von Neumann ( 1990 ) Medalia Centenar a Școlii Absolvente de Arte și Științe, Universitatea Harvard [d] Premiul Harvey ( 1998 ) Premiul Fulkerson ( 1979 ) Premiul Asociației Europene pentru Informatică Teoretică [d] ( 2000 ) Medalia Benjamin Franklin ( 2004 ) Premiul Kyoto pentru Tehnologie Avansată [d] ( 2008 ) Medalia Benjamin Franklin ( 2004 ) Premiul Dixon pentru contribuția semnificativă la dezvoltarea științei [d] ( 2009 ) doctor onorific al Technion [d] doctorat onorific de la Institutul Weizmann [d] Premiul Kyoto Fello ACM ( 1994 ) membru al Societății pentru Matematică Industrială și Aplicată [d] ( 2009 ) Premiul Frederick W. Lanchester [d] ( 1977 ) doctorat onorific de la ETH Zurich [d]
Fișiere media la Wikimedia Commons

Richard Manning Karp ( ing.  Richard Manning Karp ; născut la 3 ianuarie 1935 , Boston , SUA ) este un om de știință american în domeniul teoriei computerelor, câștigător al Premiului Turing .

Membru al Academiei Naționale de Științe din SUA (1980) [2] , Academiei Naționale de Inginerie din SUA (1992) [3] , membru străin al Academiei Franceze de Științe (2002) [4] .

Biografie

Richard Karp sa născut în Boston , statul Massachusetts . _ _ Odată cu el au crescut doi frați mai mici Robert și David (n. 1944, sociolog) și sora mai mică Carolyn.

După ce a absolvit liceul, Richard a intrat la Universitatea Harvard , unde a primit o diplomă de licență ( 1955 ), un master în științe ( 1956 ) și, în final, un doctorat în matematică aplicată în 1959 .

După absolvire, Richard Karp a lucrat timp de 9 ani la Centrul de Cercetare IBM ( Thomas Watson Research Center ). În 1968, a primit o profesie de profesor în informatică, matematică și cercetare operațională de la Universitatea din California, Berkeley , unde rămâne până în prezent, în afară de o pauză de patru ani de la munca la Universitatea din Washington (din Seattle ).

Contribuție

În 1971, Karp, împreună cu Jack Edmonds , au dezvoltat un algoritm pentru găsirea debitului maxim într-o rețea de transport , numit după ei. Un an mai târziu, Karp a publicat lucrarea sa „Reducibility Among Combinatorial Problems”, [6] în care a demonstrat NP-completitudinea pentru 21 de probleme.

În 1973, Karp și John Hopcroft au publicat algoritmul Hopcroft-Karp , care este cea mai rapidă metodă cunoscută pentru găsirea corespondențelor maxime de numărare a elementelor în graficele bipartite [7] .

În 1980 , împreună cu Richard J. Lipton, Karp a demonstrat teorema Karp-Lipton .

În 1987 , împreună cu Michael Rabin , Karp a dezvoltat algoritmul de căutare subșirurilor numit după ei [7] .

Richard Karp a făcut multe alte descoperiri importante în domeniul informaticii și cercetării operaționale în domeniul algoritmilor combinatori . Astăzi este angajat în cercetare în bioinformatică [7] .

Recunoaștere

• La sfârșitul lunii februarie 2009, Karp a fost clasat pe locul 35 pe lista celor mai citați autori în proiectul CiteSeer . [opt]
• 1977  - Premiul Frederic Lanchester , ORSA
• 1979  - Premiul Fulkerson , Societatea Americană de Matematică
• 1985  - Premiul Turing „pentru contribuțiile sale continue la teoria algoritmilor, inclusiv dezvoltarea de algoritmi eficienți pentru fluxuri pe rețele și alte probleme de optimizare combinatorie , compararea calculelor complexității polinomiale cu noțiunea intuitivă de eficiență și, cel mai important, pentru contribuțiile sale la teoria completității NP ”.
• 1987 - Prelegere de John von Neumann
• 1990  - Premiul teoretic Von Neumann , ORSA
• 1994 Calitatea de Membru  de Onoare ACM
• 1995  - Premiul Charles Babbage
• 1996  - Medalia Națională a Științei SUA
• 1998  - Premiul Harvey , Institutul de Tehnologie din Israel
• 2004  - Medalia Benjamin Franklin [9]
• 2008  - Premiul Kyoto
• 2008  - Premiul Dixon

Literatură

• R. Karp. = Complexitatea calculului. - Societatea Americană de Matematică , 1974. - 166 p. — ISBN 978-0821813270 .

Vezi și

• Algoritmul Edmonds-Karp
• Algoritmul Rabin-Karp

Link -uri

• Site-ul web Richard Karp Arhivat 19 decembrie 2016 la Wayback Machine de la Universitatea din Berkeley  
• „O zi din viața lui Richard Karp” , biografie pe site-ul ACM
•  Richard M. Karp - Biografie. Data accesului: 8 decembrie 2014. Arhivat din original pe 19 februarie 2015.
• Fundația Inamori  (engleză)  (link nu este disponibil) . - Știința informației. Arhivat din original pe 16 februarie 2013.

Note

1. ↑ Genealogia matematică  (engleză) - 1997.
2. ^ Karp, Richard Manning pe site-ul Academiei Naționale de Științe din SUA  
3. ↑ Dr. Richard M. Karp Arhivat 2 mai 2019 la Wayback Machine 
4. ↑ Richard Karp Arhivat pe 8 septembrie 2019 la Wayback Machine  (FR)
5. ↑ Familia mamei provenea din orașul Eishishki , provincia Grodno .
6. ↑ „Reducibility Among Combinatorial Problems” Arhivat 29 iunie 2011 la Wayback Machine , R. Karp , 1972 
7. ↑ 1 2 3 Richard M.  Karp . - Biografie. Data accesului: 8 decembrie 2014. Arhivat din original pe 19 februarie 2015.
8. ↑ Statistici - Cei mai citați autori în informatică . Consultat la 27 februarie 2009. Arhivat din original la 1 mai 2012. (nedefinit)
9. ↑ Richard M. Karp - Premiile Institutului Franklin - Baza de date Laureate Arhivată la 1 iunie 2010 la Wayback Machine

Site-uri tematice	Genealogie matematică Scopus zbMATH Deschide
Dicționare și enciclopedii	Britannica (online)
În cataloagele bibliografice BIBSYS: 90786429 BNF : 13493331z GND : 170367800 ISNI : 0000 0001 1669 0593 J9U : 987007376932905171 LCCN : nr.2010128364 NTA : 070554897 NUKAT : n99032553 SUDOC : 074436279 VIAF : 71546274 WorldCat VIAF : 71546274