Karp, Richard Manning
Richard Manning Karp ( Ing. Richard Manning Karp ; nacido el 3 de enero de 1935 , Boston , EE . UU .) es un científico estadounidense en el campo de la teoría informática, ganador del Premio Turing .
Miembro de la Academia Nacional de Ciencias de EE . UU. (1980) [2] , Academia Nacional de Ingeniería de EE . UU. (1992) [3] , miembro extranjero de la Academia de Ciencias de Francia (2002) [4] .
Biografía
Richard Karp nació en Boston , estado de Massachusetts . _ _ Con él crecieron dos hermanos menores, Robert y David (n. 1944, sociólogo) y una hermana menor, Carolyn.
Después de graduarse de la escuela secundaria, Richard ingresó a la Universidad de Harvard , donde recibió una licenciatura ( 1955 ), una maestría en ciencias ( 1956 ) y finalmente un doctorado en matemáticas aplicadas en 1959 .
Después de graduarse, Richard Karp trabajó durante 9 años en el IBM Research Center ( Thomas Watson Research Center ). En 1968, recibió una cátedra de informática, matemáticas e investigación de operaciones de la Universidad de California, Berkeley , donde permanece hasta el día de hoy, además de un descanso de cuatro años de su trabajo en la Universidad de Washington (en Seattle ).
Contribución
En 1971, Karp, junto con Jack Edmonds , desarrollaron un algoritmo para encontrar el flujo máximo en una red de transporte , que lleva su nombre. Un año más tarde, Karp publicó su artículo "Reducibilidad entre problemas combinatorios", [6] en el que demostró la completitud de NP para 21 problemas.
En 1973, Karp y John Hopcroft publicaron el algoritmo Hopcroft-Karp , que es el método conocido más rápido para encontrar las correspondencias máximas de recuento de elementos en gráficos bipartitos [7] .
En 1980 , junto con Richard J. Lipton, Karp demostró el teorema de Karp-Lipton .
En 1987 , junto con Michael Rabin , Karp desarrolló el algoritmo de búsqueda de subcadenas que lleva su nombre [7] .
Richard Karp hizo muchos otros descubrimientos importantes en ciencias de la computación e investigación de operaciones en el campo de los algoritmos combinatorios . Hoy se dedica a la investigación en bioinformática [7] .
Reconocimiento
- A fines de febrero de 2009, Karp ocupaba el puesto 35 en la lista de autores más citados en el proyecto CiteSeer . [ocho]
- 1977 - Premio Frederic Lanchester , ORSA
- 1979 - Premio Fulkerson , Sociedad Matemática Estadounidense
- 1985 - Premio Turing "por sus continuas contribuciones a la teoría de algoritmos, incluido el desarrollo de algoritmos eficientes para flujos en redes y otros problemas de optimización combinatoria , la comparación de cálculos de complejidad polinomial con la noción intuitiva de eficiencia y, lo más importante, por sus contribuciones a la teoría de la completitud NP .
- 1987 - Conferencia de John von Neumann
- 1990 - Premio Teórico Von Neumann , ORSA
- 1994 Membresía Honoraria ACM
- 1995 - Premio Charles Babbage
- 1996 - Medalla Nacional de Ciencias de EE . UU.
- 1998 - Premio Harvey , Instituto de Tecnología de Israel
- 2004 - Medalla Benjamín Franklin [9]
- 2008 - Premio Kioto
- 2008 - Premio Dixon
Literatura
- R. Karp. = Complejidad de Cómputo. - Sociedad Matemática Americana , 1974. - 166 p. — ISBN 978-0821813270 .
Véase también
Enlaces
- Sitio web de Richard Karp Archivado el 19 de diciembre de 2016 en Wayback Machine en la Universidad de Berkeley .
- "Un día en la vida de Richard Karp" , biografía en el sitio web de ACM
- Richard M Karp - Biografía. Fecha de acceso: 8 de diciembre de 2014. Archivado desde el original el 19 de febrero de 2015.
- Fundación Inamori (inglés) (enlace no disponible) . - Ciencias de la Información. Archivado desde el original el 16 de febrero de 2013.
Notas
- ↑ Genealogía matemática (inglés) - 1997.
- ↑ Karp, Richard Manning en el sitio web de la Academia Nacional de Ciencias de EE . UU.
- ↑ Dra. Richard M. Karp Archivado el 2 de mayo de 2019 en Wayback Machine .
- ↑ Richard Karp Archivado el 8 de septiembre de 2019 en Wayback Machine (FR)
- ↑ La familia de la madre procedía de la ciudad de Eishishki , provincia de Grodno .
- ↑ "Reducibilidad entre problemas combinatorios" Archivado el 29 de junio de 2011 en Wayback Machine , R. Karp , 1972
- ↑ 1 2 3 Richard M. Karp . - Biografía. Fecha de acceso: 8 de diciembre de 2014. Archivado desde el original el 19 de febrero de 2015.
- ↑ Estadísticas: autores más citados en informática . Consultado el 27 de febrero de 2009. Archivado desde el original el 1 de mayo de 2012.
- ↑ Richard M. Karp - The Franklin Institute Awards - Laureate Database Archivado el 1 de junio de 2010 en Wayback Machine .
 sitios temáticos | ||||
|---|---|---|---|---|
| diccionarios y enciclopedias | ||||
| ||||
| Ganadores del Premio Turing | |
|---|---|
| |