La publication de l'article de 1972 « Reducibility Among Combinatorial Problems » a établi Richard M. Karp comme une figure fondamentale de la théorie de la complexité computationnelle. En prouvant que 21 problèmes distincts sont NP-complets, il a fourni la méthodologie nécessaire aux chercheurs pour identifier quels défis théoriques et pratiques en informatique sont fondamentalement difficiles à résoudre en utilisant des algorithmes efficaces à temps polynomial.
Fondements académiques et début de carrière
Né à Boston en 1935, Richard Manning Karp a suivi toute sa formation universitaire à l'Université Harvard. Il a obtenu une licence en 1955, un master en 1956 et a terminé son doctorat en mathématiques appliquées en 1959 à la Harvard School of Engineering and Applied Sciences. Après ses études, il a commencé sa carrière professionnelle au centre de recherche Thomas J. Watson d'IBM.
Développement d'algorithmes combinatoires
Les travaux de Karp couvrent plusieurs décennies de développement algorithmique. En 1962, il a collaboré avec Michael Held pour créer l'algorithme de Held-Karp pour le problème du voyageur de commerce. Cela a été suivi par l'algorithme d'Edmonds-Karp en 1971, développé avec Jack Edmonds pour résoudre les problèmes de flot maximum dans les réseaux. En 1973, il s'est associé à John Hopcroft pour produire l'algorithme de Hopcroft-Karp, qui reste la méthode la plus rapide pour identifier les couplages de cardinalité maximale dans les graphes bipartis. De plus, il a travaillé avec Michael O. Rabin en 1987 pour co-développer l'algorithme de recherche de chaînes de Rabin-Karp.
Rôles institutionnels et reconnaissance
En 1968, Karp a rejoint le corps professoral de l'Université de Californie à Berkeley, où il a été le premier président associé de la division des sciences informatiques. En dehors d'un mandat de quatre ans en tant que professeur à l'Université de Washington, il a maintenu son affiliation avec Berkeley. En 2012, il est devenu le directeur fondateur du Simons Institute for the Theory of Computing. Ses contributions à la science ont été reconnues par de nombreuses distinctions, notamment le prix Turing en 1985, le prix Harvey en 1998, la médaille Benjamin Franklin en 2004, le prix Kyoto en 2008 et le prix Dickson en 2009.
Vingt questions, huit minutes au chronomètre et un centile mesuré face à tous ceux qui l’ont passé. Sans inscription.
Passer le test de QI →Faits marquants
- Naissance : 1935, Boston, Massachusetts - Éducation : Université Harvard (B.S., M.S., Ph.D.) - Affiliation principale : Université de Californie, Berkeley - Prix Turing : 1985 - Prix Kyoto en technologie avancée : 2008 - Domaines de recherche clés : Bioinformatique et théorie du calcul - Publication majeure de 1972 : Reducibility Among Combinatorial Problems - Directeur fondateur : Simons Institute for the Theory of Computing
Questions posées par les lecteurs
### Quelle est l'importance de l'article de 1972 de Richard Karp ?
Il a prouvé que 21 problèmes différents étaient NP-complets, fournissant une méthodologie standard pour classer la difficulté computationnelle des problèmes.
### Quelles distinctions majeures Richard Karp a-t-il reçues ?
Il a reçu le prix Turing, le prix Kyoto, le prix Harvey, la médaille Benjamin Franklin et le prix de théorie John von Neumann, entre autres.
.jpg)
