- Richard Karp
-
Richard Manning Karp, né en 1935 à Boston dans le Massachusetts, est un informaticien américain, connu pour ses recherches en théorie de la complexité. Il a reçu le prix Turing en 1985 pour ces travaux.
Né de Abraham et Rose Karp à Boston, Karp a trois frères et sœurs : Robert, David et Carolyn. Il est entré à l'université Harvard, où il reçut son Bachelor's degree en 1955, son Master's degree en 1956, et son Ph.D. de mathématiques appliquées en 1959. Il a ensuite travaillé pour IBM au centre de recherche Thomas J. Watson. En 1968, il devient professeur d'informatique et de mathématiques à l'université de Californie, Berkeley, où il restera ensuite, à l'exception d'une période de 4 ans comme professeur à l'université de Washington. Richard Karp a reçu la National Medal of Science et en 2004 la médaille Benjamin Franklin en informatique pour ses travaux sur la complexité algorithmique.
Il fut cité de la façon suivante lors de la remise du prix Turing : Pour ses contributions continues à la théorie des algorithmes, notamment le développement d'algorithmes efficaces pour les réseaux et d'autres problèmes d'optimisation combinatoires, l'identification de calculabilité en temps polynomial avec la notion intuitive d'algorithme efficace, et surtout, ses contributions à la théorie de la NP-complétude. Karp a introduit la méthodologie désormais classique pour prouver qu'un problème est NP-complet, ce qui a permis d'identifier de nombreux problèmes pratiques et théoriques comme étant difficiles à calculer.
En 1971 il a co-développé avec Jack Edmonds l'algorithme d'Edmonds-Karp pour résoudre le problème du flux maximum dans les réseaux, et en 1972 il a publié un article fondateur en théorie de la complexité, dans lequel il prouve la NP-complétude de 21 problèmes[1].
En 1987, il a co-développé l'algorithme de Rabin-Karp.
Il s'intéresse actuellement à la bio-informatique.
Notes et références
- (en) Richard M. Karp, Reducibility Among Combinatorial Problems. In Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y.. New York: Plenum, p.85-103. 1972.
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Richard Karp » (voir la liste des auteurs)
Voir aussi
Liens externes
- (en) ACM Crossroads magazine : interview de Richard Karp
- (en) Page personnelle
- (en) Publications de Richard M. Karp sur DBLP
- (en) Publications de Richard M. Karp sur ScientificCommons
Catégories :- Naissance en 1935
- Personnalité américaine en informatique
- Personnalité en informatique théorique
- Lauréat du prix Turing
Wikimedia Foundation. 2010.
