Richard M. Karp

Richard M. Karp

Richard Karp

Karp mg 7725-b.cr2.jpg

Richard 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 soeurs : Robert, David et Carolyn. Il est entré à l'université de 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-developpé 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-developpé l'algorithme de Rabin-Karp.

Il s'intéresse actuellement à la bioinformatique.

Notes et références de l'article

  1. ↑ (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 d’une traduction de l’article de Wikipédia en anglais intitulé « Richard Karp ».

Voir aussi

Liens externes

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Richard Karp ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Richard M. Karp de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Richard M. Karp — Richard Karp 2009 Richard Manning Karp (* 3. Januar 1935 in Boston, Massachusetts) ist ein amerikanischer Informatiker. Er ist verantwortlich für bedeutende Erkenntnisse in der Komplexitätstheorie. 1985 erhielt er für seine Forschungsarbeit auf… …   Deutsch Wikipedia

  • 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 …   Wikipédia en Français

  • Richard Karp — Saltar a navegación, búsqueda Richard Karp Richard Manning Karp (Boston, (Estados Unidos), 3 de enero de 1935) es un científico de la computación, conocido por su investigación en teoría de algoritmos, por lo que recibió el …   Wikipedia Español

  • Karp — ist der Familienname folgender Personen: Bob Karp (1911–1975), amerikanischer Comictexter Carol Karp (geborene Carol van der Velde; 1926–1972), US amerikanische mathematische Logikerin Guido Karp (* 1963), deutscher Fotograf Marcia Karp (* 1942) …   Deutsch Wikipedia

  • Richard Karp — ist der Name folgender Personen: Richard A. Karp (* 1944), amerikanischer Informatiker Richard M. Karp (* 1935), amerikanischer Informatiker Diese Seite ist eine Begriffsklärung zur Unterscheidung mehrerer mit demselben Wort bezeichne …   Deutsch Wikipedia

  • Richard Karp — Infobox Scientist name = Richard Manning Karp image width = caption = birth date = January 3, 1935 birth place = Boston, Massachusetts death date = death place = residence = citizenship = nationality = American ethnicity = field = Computer… …   Wikipedia

  • Karp-Rabin-Algorithmus — Der Rabin Karp Algorithmus ist ein Suchalgorithmus für Texte, der von Michael O. Rabin und Richard M. Karp entwickelt wurde. Der Algorithmus sucht nach einem Muster, z. B. einer Zeichenkette, innerhalb einer anderen Zeichenkette mit Hilfe von… …   Deutsch Wikipedia

  • Karp-Lipton theorem — The Karp–Lipton theorem in complexity theory states that if the boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then :Pi 2 , = Sigma 2 , and therefore mathrm{PH} , = Sigma 2 ,.That… …   Wikipedia

  • Karp's 21 NP-complete problems — One of the most important results in computational complexity theory was Stephen Cook s 1971 demonstration of the first (practically relevant) NP complete problem, the boolean satisfiability problem. [cite book|author = Stephen Cook|year =… …   Wikipedia

  • Richard J. Lipton — Infobox Scientist image width = 150px name = Richard J. Lipton box width = birth date = Sept 6, 1946 birth place = death date = death place = residence = citizenship = nationality = ethnicity = field = computer science work institutions = Yale… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”