Richard Karp
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Richard Karp, né en 1935 à Boston dans le Massachussetts, 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, Massachusetts, Karp a trois frères et soeurs : Robert, David et Carolyn. Il est entré à l'université (Une université est un établissement d'enseignement supérieur dont l'objectif est la production du savoir (recherche), sa conservation et sa transmission (études...) 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 (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les...) appliquées en 1959. Il a ensuite travaillé pour IBM (International Business Machines Corporation (IBM) est une société multinationale américaine présente dans les domaines du matériel informatique, du logiciel et des services informatiques.) au centre de recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la recherche scientifique désigne également le cadre...) Thomas J. Watson. En 1968, il devient professeur d'informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement automatique de l'information par des machines...) et de mathématiques à l'Université de Californie (L'université de Californie est une université américaine, fondée en 1868, dont le siège se trouve à Berkeley (Californie),...), Berkeley, où il restera ensuite, à l'exception d'une période de 4 ans comme professeur à l'Université de Washington. Richard Karp (Richard Karp, né en 1935 à Boston dans le Massachussetts, 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.) a reçu la National Medal of Science (La science (latin scientia, « connaissance ») est, d'après le dictionnaire Le Robert, « Ce que l'on sait pour l'avoir appris, ce que l'on tient pour vrai au sens large....) et en 2004 la médaille Benjamin Franklin (Benjamin Franklin (17 janvier 1706 à Boston - 17 avril 1790 à Philadelphie) est l'une des plus illustres figures de l'histoire américaine, à la fois écrivain, physicien et...) en informatique pour ses travaux sur la complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en sociologie, en informatique...) algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à...).

Il fut cité (La cité (latin civitas) est un mot désignant, dans l’Antiquité avant la création des États, un groupe d’hommes sédentarisés...) 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é (La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la logique mathématique et de l'informatique théorique. Alors que la notion intuitive de fonction calculable est...) en temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) 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 (Le mot flux (du latin fluxus, écoulement) désigne en général un ensemble d'éléments (informations / données, énergie, matière, ...) évoluant dans un sens commun. Plus...) maximum dans les réseaux, et en 1972 il a publié un article fondateur en théorie de la complexité (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en informatique. Elle se distingue de la théorie de...), 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 (New York , en anglais New York City (officiellement, City of New York) pour la distinguer de l’État de New York, est la principale ville des États-Unis, elle compte a elle seule 8 143 200 habitants. Son...): Plenum, p.85-103. 1972.
  • (en) Cet article est partiellement ou en totalité issu d’une traduction de l’article de Wikipédia (Wikipédia (prononcé /wi.ki.pe.dja/) est une encyclopédie, multilingue, universelle, librement diffusable, disponible sur le Web et écrite par les internautes grâce à la technologie wiki....) en anglais intitulé "  "
Page générée en 0.256 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique