system
Răspunde în limba română, în stilul Wikipedia, cat mai corect gramatical.
user
Ce poți povesti despre Richard Karp?
assistant
Richard Manning Karp () este un specialist în calculatoare electronice cunoscut pentru cercetările sale în domeniul algoritmilor, pentru care a primit Premiul Turing în 1985. Este coautor al algoritmilor Edmonds Karp și Rabin-Karp.

Biografia 
Născut în familia lui Abraham și a lui Rose Karp în Boston, Massachusetts, Karp are trei frați mai mici: Robert, , and Carolyn. A studiat la Universitatea Harvard, unde a absolvit cursurile de licență în 1955, cele de master în 1956, și a obținut doctoratul în matematică aplicată în 1959.

A început să lucreze la  de la IBM. În 1968, a devenit profesor de informatică, matematică și cercetare operațională la University of California, Berkeley. În afara unei perioade de patru ani petrecută ca profesor la Universitatea din Washington, a rămas permanent la Berkeley. Între 1988 și 1995 și din 1999 încoace este și cercetător la  din Berkeley, unde conduce grupul de algoritmi.

Richard Karp a primit , și este laureat al  de la Technion și a  pe 2004 pentru informatică și științe cognitive pentru descoperirile din domeniul teoriei complexității. În 1994 a fost primit ca  al ACM.

În 2012, Karp a devenit director fondator al  de la University of California, Berkeley.

Activitatea 
A efectuat numeroase alte descoperiri importante în informatică și în  în domeniul . Interesele sale principale de cercetare cuprind și bioinformatica.

În 1971 a dezvoltat împreună cu Jack Edmonds algoritmul Edmonds–Karp de rezolvare a problemei debitului maxim în rețele, iar în 1972 a publicat o lucrare esențială în teoria complexității, "Reducibility Among Combinatorial Problems", în care a demonstrat că 21 de probleme sunt NP-complete.

În 1973, împreună cu John Hopcroft, a publicat , care și astăzi este cea mai rapidă metodă cunoscută de găsire a  de cardinalitate maximă în grafurile bipartite.

În 1980, împreună cu , Karp a demonstrat , care arată că, dacă  poate fi rezolvată prin  cu un număr polinomial de porți logice, atunci  se pliază la nivelul al doilea.

În 1987, împreună cu Michael O. Rabin, a dezvoltat algoritmul Rabin-Karp de căutare în șiruri de caractere.

Premiul Turing 
A primit premiul Turing pe anul 1985, pentru:

... contribuțiile continue la teoria algoritmilor, inclusiv dezvoltarea de algoritmi eficienți pentru fluxul în rețele și pentru alte probleme de optimizare combinatorică, identificarea calculabilității în timp polinomial cu noțiunea intuitivă de eficiență algoritmică și, mai ales, pentru contribuțiile aduse în teoria NP-completitudinii. Karp a introdus metodologia, devenită astăzi standard, de demonstrare a NP-completitudinii problemelor care a dus la identificarea multor probleme practice și teoretice ca fiind probleme computațional grele.

Note 

Oameni de știință americani din secolul al XX-lea
Absolvenți ai Universității Harvard
Oameni în viață
Membri ai Academiei Franceze de Științe
Membri ai Academiei Naționale de Științe a Statelor Unite
Laureați ai National Medal of Science
Oameni din Boston, Massachusetts
Matematicieni americani din secolul al XX-lea
Laureați ai Premiului Turing
Informaticieni americani
Nașteri în 1935
Matematicieni americani din secolul al XXI-lea
Americani în viață