Richard Karp

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare
Richard Karp
Karp mg 7725-b.cr2.jpg
Date personale
Născut (82 de ani)[1] Modificați la Wikidata
Boston, Statele Unite ale Americii[2] Modificați la Wikidata
Cetățenie Flag of the United States.svg SUA Modificați la Wikidata
Ocupație matematician
informatician
profesor universitar Modificați la Wikidata
Activitate
Număr Erdős Modificați la Wikidata
Instituție Universitatea Berkeley din California  Modificați la Wikidata
Alma Mater Universitatea Harvard  Modificați la Wikidata
Societăți Academia Franceză de Științe
Academia Națională de Științe a Statelor Unite ale Americii[*]
American Philosophical Society[*]
American Association for the Advancement of Science[*]
Academia Americană de Arte și Științe[*]
National Academy of Engineering[*]
Association for Computing Machinery  Modificați la Wikidata
Premii Premiul Turing ()
Premiul de teorie John von Neumann[*] ()
Harvard Centennial Medal[*]
Harvey Prize[*] ()
Fulkerson Prize[*] ()
National Medal of Science[*] ()
premiul EATCS[*] ()
Benjamin Franklin Medal[*] ()
Kyoto Prize in Advanced Technology[*] ()
Medalia Benjamin Franklin[*] ()
Q30871847[*] (Modificați la Wikidata
Prezență online

Richard Manning Karp (n. ,[1] Boston, Statele Unite ale Americii[2]) 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[modificare | modificare sursă]

Născut în familia lui Abraham și a lui Rose Karp în Boston, Massachusetts, Karp are trei frați mai mici: Robert, David⁠(d), 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 Thomas J. Watson Research Center⁠(d) 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 Statului Washington⁠(d), a rămas permanent la Berkeley. Între 1988 și 1995 și din 1999 încoace este și cercetător la International Computer Science Institute⁠(d) din Berkeley, unde conduce grupul de algoritmi.

Richard Karp a primit Medalia Națională a Științei⁠(d), și este laureat al Premiului Harvey⁠(d) de la Technion și a Medaliei Benjamin Franklin⁠(d) pe 2004 pentru informatică și științe cognitive pentru descoperirile din domeniul teoriei complexității. În 1994 a fost primit ca fellow⁠(d) al ACM.

În 2012, Karp a devenit director fondator al Simons Institute for the Theory of Computing⁠(d) de la University of California, Berkeley.[3]

Activitatea[modificare | modificare sursă]

A efectuat numeroase alte descoperiri importante în informatică și în cercetarea operațională⁠(d) în domeniul algoritmilor combinatorici⁠(d). 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.[4]

În 1973, împreună cu John Hopcroft, a publicat algoritmul Hopcroft–Karp⁠(d), care și astăzi este cea mai rapidă metodă cunoscută de găsire a cuplajelor⁠(d) de cardinalitate maximă în grafurile bipartite.

În 1980, împreună cu Richard J. Lipton⁠(d), Karp a demonstrat teorema Karp-Lipton⁠(d), care arată că, dacă SAT⁠(d) poate fi rezolvată prin circuite booleene⁠(d) cu un număr polinomial de porți logice, atunci ierarhia polinomială⁠(d) 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[modificare | modificare sursă]

A primit premiul Turing pe anul 1985, pentru:[5]

... 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[modificare | modificare sursă]

  1. ^ a b Gemeinsame Normdatei, accesat la 24 aprilie 2014 
  2. ^ a b Gemeinsame Normdatei, accesat la 11 decembrie 2014 
  3. ^ California Chosen as Home for Computing Institute”. The New York Times. 30 aprilie 2012. https://www.nytimes.com/2012/05/01/science/simons-foundation-chooses-uc-berkeley-for-computing-center.html?_r=0. Accesat la 23 octombrie 2016. 
  4. ^ Richard M. Karp (1972). „Reducibility Among Combinatorial Problems”. în R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103. http://www.cs.berkeley.edu/~luca/cs172/karp.pdf 
  5. ^ Association for Computing Machinery. „ACM Award Citation/Richard M. Karp. http://awards.acm.org/citation.cfm?id=3256708&srt=all&aw=140&ao=AMTURING&yr=1985. Accesat la 17 ianuarie 2010.