Richard Karp

De la Wikipedia, enciclopedia liberă
Sari la navigare Sari la căutare
Richard Karp
Karp mg 7725-b.cr2.jpg
Richard Karp
Date personale
Născut (86 de ani)[1][2] Modificați la Wikidata
Boston, Massachusetts, SUA Modificați la Wikidata
CetățenieFlag of the United States.svg SUA Modificați la Wikidata
Ocupațiematematician
informatician
profesor universitar[*] Modificați la Wikidata
Activitate
Domeniuteoria calculabilității
bioinformatică  Modificați la Wikidata
Număr ErdősModificați la Wikidata
InstituțieUniversitatea Berkeley din California
Universitatea Statului Washington  Modificați la Wikidata
Alma MaterUniversitatea Harvard
Harvard School of Engineering and Applied Sciences[*][[Harvard School of Engineering and Applied Sciences (Engineering School in Cambridge, Massachusetts)|​]]
Universitatea Berkeley din California  Modificați la Wikidata
OrganizațiiAcademia Franceză de Științe
Academia Națională de Științe a Statelor Unite ale Americii[*]
American Philosophical Society[*][[American Philosophical Society (United States scholarly organization that promotes knowledge in the sciences and humanities)|​]]
Asociația Americană pentru Progresul Științei[*]
Academia Americană de Arte și Științe[*]
US National Academy of Engineering[*][[US National Academy of Engineering (engineering branch of the United States National Academies)|​]]
Association for Computing Machinery  Modificați la Wikidata
Conducător de doctorat Anthony Oettinger[*][[Anthony Oettinger (computer scientist)|​]][3]  Modificați la Wikidata
Doctoranzi Noam Nisan[*][[Noam Nisan (computer scientist)|​]]
Rajeev Motwani[*][[Rajeev Motwani (Indian theoretical computer scientist and venture capitalist at Stanford University (1962–2009))|​]]
Narendra Karmarkar[*][[Narendra Karmarkar (matematician indian)|​]]
Barbara Simons[*][[Barbara Simons (American computer scientist)|​]]
Eric P. Xing[*][[Eric P. Xing (American artificial intelligence researcher)|​]]
Robert M. Keller[*][[Robert M. Keller (American computer scientist)|​]][4]
Valerie King[*][[Valerie King (American and Canadian computer scientist)|​]][3]
Raymond Reiter[*][[Raymond Reiter (Canadian computer scientist)|​]][3]
Dan Gusfield[*][[Dan Gusfield (American Computational Biologist)|​]][3]
Michael Luby[*][[Michael Luby (Information theorist and cryptographer)|​]][3]
Faith Ellen[*][[Faith Ellen (Canadian computer scientist)|​]][3]
Kellogg Speed Booth[*][[Kellogg Speed Booth (Ph.D. University of California, Berkeley 1975)|​]][3]
Thomas Jerome Schaefer[*][[Thomas Jerome Schaefer (matematician american)|​]][3]
Kathleen Marie O'Hara[*][[Kathleen Marie O'Hara (Ph.D. University of California, Berkeley 1984)|​]][3]
Sukhamay Kundu[*][[Sukhamay Kundu (Ph.D. University of California, Berkeley 1971)|​]][3]
Danny Soroker[*][[Danny Soroker (Ph.D. University of California, Berkeley 1987)|​]][3]
Howard Jeffrey Karloff[*][[Howard Jeffrey Karloff (Ph.D. University of California, Berkeley 1985)|​]][3]
Prabhakar Lakshman Ragde[*][[Prabhakar Lakshman Ragde (Ph.D. University of California, Berkeley 1986)|​]][3]
Jean-Louis Goffin[*][[Jean-Louis Goffin (Ph.D. University of California, Berkeley 1972)|​]][3]
George W. Hartzell, III[*][[George W. Hartzell, III (Ph.D. University of California, Berkeley 2001)|​]][3]
Daniel Fasulo[*][[Daniel Fasulo (Ph.D. University of Washington 2000)|​]][3]
Lee Aaron Newberg[*][[Lee Aaron Newberg (Ph.D. University of California, Berkeley 1993)|​]][3]
Ysmar Vianna Silva-Filho[*][[Ysmar Vianna Silva-Filho (Ph.D. University of California, Berkeley 1972)|​]][3]
Felix Andres Pohorille Weintraub[*][[Felix Andres Pohorille Weintraub (Ph.D. University of California, Berkeley 1972)|​]][3]
Norman Asker Zadeh[*][[Norman Asker Zadeh (Ph.D. University of California, Berkeley 1972)|​]][3]
Anne Ginzton Cottrell[*][[Anne Ginzton Cottrell (Ph.D. University of California, Berkeley 1974)|​]][3]
Robert Malcolm MacGregor[*][[Robert Malcolm MacGregor (Ph.D. University of California, Berkeley 1978)|​]][3]
Pedro Gonzalo Gazmuri[*][[Pedro Gonzalo Gazmuri (Ph.D. University of California, Berkeley 1981)|​]][3]
Rubin Johnson[*][[Rubin Johnson (Ph.D. University of California, Berkeley 1982)|​]][3]
James Powell Richardson[*][[James Powell Richardson (Ph.D. University of California, Berkeley 1984)|​]][3]
Jonathan Alexander Frankle[*][[Jonathan Alexander Frankle (Ph.D. University of California, Berkeley 1987)|​]][3]
Sally Jean Floyd[*][[Sally Jean Floyd (Ph.D. University of California, Berkeley 1989)|​]][3]
Phillip Baldwin Gibbons[*][[Phillip Baldwin Gibbons (Ph.D. University of California, Berkeley 1989)|​]][3]
Lisa Hellerstein[*][[Lisa Hellerstein (Ph.D. University of California, Berkeley 1989)|​]][3]
Yanjun Zhang[*][[Yanjun Zhang (Ph.D. University of California, Berkeley 1989)|​]][3]
Sandra Shireen Irani[*][[Sandra Shireen Irani (Ph.D. University of California, Berkeley 1991)|​]][3]
Eunice E. Santos[*][[Eunice E. Santos (Ph.D. University of California, Berkeley 1995)|​]][3]
Abhijit Sahay[*][[Abhijit Sahay (Ph.D. University of California, Berkeley 1994)|​]][3]
Amoolya Hardev Singh[*][[Amoolya Hardev Singh (Ph.D. University of California, Berkeley 2006)|​]][3]
Manikandan Narayanan[*][[Manikandan Narayanan (Ph.D. University of California, Berkeley 2007)|​]][3]  Modificați la Wikidata
Cunoscut pentru A simple algorithm for finding frequent elements in streams and bags[*][[A simple algorithm for finding frequent elements in streams and bags (article)|​]]  Modificați la Wikidata
PremiiPremiul Turing ()[5][6]
Premiul de teorie John von Neumann[*] ()
Harvard Centennial Medal[*][[Harvard Centennial Medal |​]]
Premiul Harvey[*] ()[7]
Fulkerson Prize[*][[Fulkerson Prize (Prize given jointly by the Mathematical Programming Society and the American Mathematical Society for outstanding papers in discrete mathematics)|​]] ()
Medalia Națională pentru Știință a Statelor Unite[*] ()
premiul EATCS[*] ()
Benjamin Franklin Medal[*][[Benjamin Franklin Medal (medal conferred by the RSA)|​]] ()
Kyoto Prize in Advanced Technology[*][[Kyoto Prize in Advanced Technology |​]] ()
Medalia Benjamin Franklin[*] ()
Dickson Prize in Science[*][[Dickson Prize in Science |​]] ()
doctor honoris causa al Technionului din Haifa[*]
doctor honoris causa al Institutului Weizmann din Rehovot[*]
Kyoto Prize[*][[Kyoto Prize (award for global achievement)|​]]
ACM Fellow[*][[ACM Fellow (Award granted by the Association for Computing Machinery (ACM))|​]] ()[8]
Fellow of the Society for Industrial and Applied Mathematics[*][[Fellow of the Society for Industrial and Applied Mathematics |​]]
Frederick W. Lanchester Prize[*][[Frederick W. Lanchester Prize (award)|​]] ()
Ehrendoktor der Eidgenössischen Technischen Hochschule Zürich[*][[Ehrendoktor der Eidgenössischen Technischen Hochschule Zürich |​]]  Modificați la Wikidata

Richard Manning Karp (n. ,[1][2] Boston, Massachusetts, SUA) 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 IBM 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 din Washington, 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.[9]

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.[10]

Î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:[11]

... 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 „Richard Karp”, Gemeinsame Normdatei, accesat în  
  2. ^ a b Richard M. Karp, SNAC, accesat în  
  3. ^ a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ad ae af ag ah ai Genealogia matematicienilor 
  4. ^ Genealogia matematicienilor, accesat în  
  5. ^ https://amturing.acm.org/award_winners/karp_3256708.cfm  Lipsește sau este vid: |title= (ajutor)
  6. ^ https://awards.acm.org/award_winners/karp_3256708#140  Lipsește sau este vid: |title= (ajutor)
  7. ^ https://harveypz.net.technion.ac.il/harvey-prize-laureates/  Lipsește sau este vid: |title= (ajutor)
  8. ^ https://awards.acm.org/award_winners/karp_3256708#158  Lipsește sau este vid: |title= (ajutor)
  9. ^ „California Chosen as Home for Computing Institute”. The New York Times. . Accesat în . 
  10. ^ Richard M. Karp (). „Reducibility Among Combinatorial Problems” (PDF). În R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103. 
  11. ^ Association for Computing Machinery. „ACM Award Citation/Richard M. Karp”. Accesat în .