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] .
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 ).
Î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] .
Site-uri tematice | ||||
---|---|---|---|---|
Dicționare și enciclopedii | ||||
|
ai premiului Turing | Câștigători|
---|---|
|