Loading AI tools
informaticien américain De Wikipédia, l'encyclopédie libre
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.
Naissance | |
---|---|
Nom dans la langue maternelle |
Richard Manning Karp |
Nationalité | |
Formation |
Université Harvard Harvard School of Engineering and Applied Sciences (en) Université de Californie à Berkeley |
Activités |
A simple algorithm for finding frequent elements in streams and bags (d) |
Richard Karp est le fils d'Abraham et Rose Karp[1].
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[2],[3].
Il a ensuite travaillé pour IBM au centre de recherche Thomas J. Watson[2].
En 1968, il devient professeur d'informatique et de mathématiques à l'université de Californie à Berkeley[2], 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[3].
Richard Karp a surtout travaillé en algorithmique et en théorie de la complexité. Parmi ses contributions importantes, on compte notamment les points suivants.
Il s'intéresse actuellement à la bio-informatique.
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. »
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.