Informatics Educational Institutions & Programs
Contingut
Biografia | |
---|---|
Naixement | 3 gener 1935 (89 anys) Boston (Massachusetts) |
Dades personals | |
Nacionalitat | Estatunidenc |
Formació | Harvard |
Tesi acadèmica | Some Applications of Logical Syntax to Digital Computer Programming (1959) |
Director de tesi | Anthony Oettinger[1] |
Es coneix per | Algorisme d'Edmonds-Karp 21 algorismes NP-complets de Karp Algorisme de Hopcroft-Karp Teorema de Karp–Lipton Algorisme de Rabin–Karp |
Activitat | |
Camp de treball | Teoria de la computació i bioinformàtica |
Ocupació | Informàtica |
Organització | Universitat de Califòrnia a Berkeley IBM |
Membre de | Societat de Matemàtiques Aplicades i Industrials (membre de la Societat de Matemàtiques Aplicades i Industrials) (2009–) Acadèmia Francesa de les Ciències (membre estranger) (2002–) Acadèmia Nacional d'Enginyeria (1992–) Acadèmia Nacional de Ciències dels Estats Units (membre de l'Acadèmia Nacional de Ciències dels Estats Units) (1980–) Societat Filosòfica Americana Acadèmia Americana de les Arts i les Ciències Association for Computing Machinery Associació americana per l'avanç de la ciència |
Obra | |
Obres destacables | |
Estudiant doctoral | Noam Nisan, Rajeev Motwani, Narendra Karmarkar, Barbara Simons, Eric P. Xing (en) , Robert M. Keller, Valerie King, Raymond Reiter, Dan Gusfield (en) , Michael Luby, Faith Ellen, Kellogg S. Booth (en) , Thomas Jerome Schaefer (en) , Kathleen Marie O'Hara (en) , Sukhamay Kundu, Danny Soroker (en) , Howard Jeffrey Karloff (en) , Prabhakar Lakshman Ragde (en) , Jean-Louis Goffin (en) , George W. Hartzell, III (en) , Daniel Fasulo (en) , Lee Aaron Newberg (en) , Ysmar Vianna Silva-Filho (en) , Andrés Weintraub Pohorille, Norm Zada, Anne Ginzton Cottrell (en) , Robert Malcolm MacGregor (en) , Pedro Gonzalo Gazmuri (en) , Rubin Johnson (en) , James Powell Richardson (en) , Jonathan Alexander Frankle (en) , Sally Jean Floyd (en) , Phillip Gibbons (en) , Lisa Hellerstein (en) , Yanjun Zhang (en) , Sandra S. Irani (en) , Eunice E. Santos (en) , Abhijit Sahay (en) , Amoolya Hardev Singh (en) i Manikandan Narayanan (en) |
Premis Premi Turing (1985) John von Neumann Theory Prize (1990) National Medal of Science (1996) Harvey Prize Benjamin Franklin Medal Kyoto Prize | |
Lloc web | eecs.berkeley.edu… |
Richard Manning Karp (nascut el 3 de gener de 1935) és un informàtic i teòric de la computació estatunidenc que treballa a la Universitat de Califòrnia a Berkeley. És conegut sobretot per la seva recerca en teoria d'algorismes, que li va valer el Premi Turing el 1985, la Medalla Benjamin Franklin el 2004, i el Premi Kyoto el 2008.[2]
Biografia
Va néixer a Boston, Massachusetts. Va estudiar a Harvard, on va llicenciar-se el 1955, va obtenir el màster el 1956, i es va doctorar en matemàtica aplicada el 1959.
Va començar a treballar al Centre de Recerca Thomas J. Watson, d'IBM. El 1968, va convertir-se en professor d'Informàtica, Matemàtiques i Investigació Operativa a la Universitat de Califòrnia a Berkeley. A part d'un període de 4 anys que va fer de professor a la Universitat de Washington, sempre més ha treballat a Berkely. Entre 1988 i 1995, i des de 1999 ha fet de Científic a l'International Computer Science Institute de Berkeley, on és el cap del Grup d'Algorismes.
Obra
Ha fet nombrosos descobriments importants en informàtica i investigació operativa en l'àrea d'optimització combinatòria. Actualment s'interessa per la bioinformàtica.
El 1971 va desenvolupar juntament amb Jack Edmonds l'algorisme d'Edmonds-Karp per resoldre el problema de flux màxim en xarxes, i el 1972 va publicar un dels articles més importants de teoria de la complexitat, "Reducibility Among Combinatorial Problems", on demostrava que 21 problemes eren NP-complets.[3]
El 1973 va publicar juntament amb John Hopcroft l'algorisme Hopcroft–Karp, que encara ara és el mètode més ràpid que es coneix per trobar aparellaments de cardinalitat màxima en grafs bipartits.
El 1980, juntament amb Richard J. Lipton, Karp va demostrar el teorema de Karp-Lipton (que demostra que, si el problema SAT es pot resoldre per circuits booleans amb un nombre polinòmic de portes lògiques, llavors la jerarquia polinòmica es col·lapsa al seu segon nivell).
El 1987 va desenvolupar amb Michael O. Rabin l'algorisme de cerca de cadenes Rabin-Karp.
Premi Turing
La presentació[4] del seu Premi Turing deia:
- Per les seves contribucions continuades a la teoria d'algorismes, que inclouen el desenvolupament d'algorismes eficients per al flux de xarxa i altres problemes d'optimització combinatòria, la identificació de la computabilitat en temps polinòmic amb la noció intuïtiva d'eficiència algorísmica, i, com a punt més destacat, les contribucions a la teoria de NP-completesa. Karp va introduir la metodologia que avui en dia és estàndard per demostrar que els problemes són NP-complets, cosa que ha ajudat a la identificació de molts problemes teòrics i pràctics com a difícils a nivell computacional.
Referències
- ↑ Richard Karp al Mathematics Genealogy Project.
- ↑ http://www.inamori-f.or.jp/laureates/k24_a_richard/prs_e.html Arxivat 2010-03-14 a Wayback Machine.
- ↑ Richard M. Karp. «Reducibility Among Combinatorial Problems». A: R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum, 1972, p. 85–103.
- ↑ Association for Computing Machinery. «ACM Award Citation/Richard M. Karp». Arxivat de l'original el 2012-07-03. [Consulta: 17 gener 2010].
Enllaços externs
A Wikimedia Commons hi ha contingut multimèdia relatiu a: Richard Karp |
- Entrevista/biografia de Richard Karp a ACM Crossroads
- Pàgina personal de Karp a Berkeley