Richard M. Karp

Fra Wikipedia, den frie encyklopedi
Hopp til: navigasjon, søk
Richard M. Karp
Karp mg 7725-b.cr2.jpg
Født 3. januar 1935 (82 år)
Boston
Utdannet ved Harvard University
Yrke Matematiker, informatiker, universitetslærer
Nasjonalitet USA
Medlem av Det franske vitenskapsakademiet, National Academy of Sciences, American Philosophical Society, American Association for the Advancement of Science, American Academy of Arts and Sciences, National Academy of Engineering, Association for Computing Machinery
Utmerkelser
11 oppføringer
Turing-prisen, John von Neumann Theory Prize, Harvard Centennial Medal, Harveyprisen, Fulkerson Prize, National Medal of Science, EATCS award, Benjamin Franklin-medaljen, Kyotoprisen for avansert teknologi, Benjamin Franklin-medaljen, EATCS award

Richard Manning Karp (født 3. januar 1935 i Boston) er en amerikansk informatiker som har gitt betydningsfulle bidrag til forskning innen kompleksitetsteori. For dette arbeidet mottok han Turing-prisen i 1985.

Karp gikk på Harvard University hvor han tok bachelorgraden i 1955, mastergraden i 1956 og doktorgraden i anvendt matematikk i 1959. Deretter jobbet han på Thomas J. Watson Research Center hos IBM. I 1968 ble han professor i informatikk, matematikk og operations research ved University of California, Berkeley. Siden det har han vært i Berkeley, med unntak av fire år hvor han arbeidet som professor ved University of Washington. Karp mottok også Benjamin Franklin-medaljen i 2004 i informatikk og kognitiv vitenskap for bidragene sine innen kompleksitetsteori.

I 1971 utviklet han Edmonds-Karp-algoritmen for maks-flyt-problemet sammen med Jack Edmonds, og i 1972 publiserte han en viktig artikkel i kompleksitetsteori, Reducibility Among Combinatorial Problems hvor han viste at 21 problemer er NP-fullstendige. I 1987 utviklet han Rabin-Karp-algoritmen for tekstsøking sammen med Michael O. Rabin.

Han har gjort mange andre viktige oppdagelser i informatikk, spesielt i kombinatorisk optimalisering. For tiden er hans viktigste forskningsområde bioinformatikk.

Eksterne lenker[rediger | rediger kilde]