Richard Manning Karp (né le à Boston dans le Massachusetts) est un chercheur américain connu notamment pour ses recherches en optimisation combinatoire et théorie de la complexité. Il a reçu le prix Turing en 1985 pour ses travaux.
Biographie Richard Karp est le fils d'Abraham et Rose Karphttps://www.kyotoprize.org/wp/wp-content/uploads/2016/02/24kA_lct_EN.pdf.
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 reste ensuite, à l'exception d'une période de quatre ans comme professeur à l'université de Washington.
Il a été le directeur de thèse de Narendra Karmarkar, Noam Nisan et Rajeev Motwani entre autres.
Travaux Richard Karp a surtout travaillé en algorithmique et en théorie de la complexité. Parmi ses contributions importantes, on compte notamment les points suivants.
En 1971 il a développé, avec Jack Edmonds, l'algorithme d'Edmonds-Karp pour résoudre le problème de flot maximum dans les réseaux. 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 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 1973, il publie avec John Hopcroft, l'algorithme de Hopcroft-Karp pour un problème de couplage. En 1980, il prouve avec Richard J. Lipton, le théorème de Karp-Lipton, en théorie de la complexité.. En 1987, il a codéveloppé l'algorithme de Rabin-Karp..
Il s'intéresse actuellement à la bio-informatique.
Prix et distinctions 1985 prix Turing 1987 Conférence von Neumann 1990 prix de théorie John-von-Neumann 1996 National Medal of Science 2004 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. »
Source
Notes et références
Liens externes
ACM Crossroads magazine : interview de Richard Karp Page personnelle
Catégorie:Personnalité américaine de l'informatique Catégorie:Personnalité en informatique théorique Catégorie:Personnalité en recherche opérationnelle Catégorie:Bio-informaticien Catégorie:Docteur de l'université Harvard Catégorie:Professeur à l'université de Californie à Berkeley Catégorie:Professeur à l'université de Washington Catégorie:Docteur honoris causa du Technion Catégorie:Docteur honoris causa de l'Institut Weizmann Catégorie:Docteur honoris causa de l'École polytechnique fédérale de Zurich Catégorie:Lauréat du prix EATCS Catégorie:Lauréat du prix Turing Catégorie:Lauréat du prix Kyoto Catégorie:Récipiendaire de la National Medal of Science Catégorie:Lauréat du prix Harvey (Technion) Catégorie:Lauréat du prix Fulkerson Catégorie:Conférencier von Neumann Catégorie:Lauréat du prix de théorie John-von-Neumann Catégorie:Lauréat du prix Lanchester Catégorie:Membre de la Société américaine de philosophie Catégorie:Membre de l'Académie des sciences (France) Catégorie:Membre de l'Académie nationale des sciences Catégorie:Membre de l'Association américaine pour l'avancement des sciences Catégorie:Membre de l'Académie américaine des arts et des sciences Catégorie:Naissance en janvier 1935 Catégorie:Naissance à Boston