Ryszard M. Karp - Richard M. Karp
Richard Manning Karp | |
|---|---|
 Richard Karp na EPFL 13 lipca 2009 r.
| |
| Urodzony |
3 stycznia 1935
Boston, Massachusetts , Stany Zjednoczone
|
| Narodowość | amerykański |
| Alma Mater | Uniwersytet Harwardzki |
| Znany z |
Algorytm Edmondsa-Karpa 21 problemów NP-zupełnych Karpa Algorytm Hopcrofta-Karpa Twierdzenie Karpa-Liptona Algorytm wyszukiwania ciągów Rabina-Karpa |
| Nagrody |
Nagroda Turinga (1985) Nagroda Johna von Neumanna (1990) Narodowy Medal Nauki (1996) Nagroda Harveya Medal Benjamina Franklina Nagroda Kyoto Nagroda IEEE Computer Society Charles Babbage Award |
| Kariera naukowa | |
| Pola | Informatyka |
| Instytucje |
Uniwersytet Kalifornijski, Berkeley IBM |
| Praca dyplomowa | Niektóre zastosowania składni logicznej do cyfrowego programowania komputerów (1959) |
| Doradca doktorski | Antoniego Oettingera |
| Doktoranci | |
Richard Manning Karp (ur. 3 stycznia 1935) jest amerykańskim informatykiem i teoretykiem obliczeń na Uniwersytecie Kalifornijskim w Berkeley . Najbardziej znany jest z badań nad teorią algorytmów , za które otrzymał nagrodę Turinga w 1985 r., Medal Benjamina Franklina w dziedzinie informatyki i kognitywistyki w 2004 r. oraz Nagrodę Kioto w 2008 r.
Karp został wybrany członkiem National Academy of Engineering (1992) za znaczący wkład w teorię i zastosowanie NP-zupełności, konstruowanie wydajnych algorytmów kombinatorycznych i stosowanie metod probabilistycznych w informatyce.
Biografia
Urodzony przez rodziców Abrahama i Rose Karp w Bostonie w stanie Massachusetts , Karp ma troje młodszego rodzeństwa: Roberta, Davida i Carolyn. Jego rodzina była żydowska i dorastał w małym mieszkaniu, w wówczas w większości żydowskiej dzielnicy Dorchester w Bostonie. Oboje jego rodzice byli absolwentami Harvardu (jego matka ostatecznie uzyskała dyplom Harvardu w wieku 57 lat po uczęszczaniu na kursy wieczorowe), podczas gdy jego ojciec miał ambicje pójścia do szkoły medycznej po Harvardzie, ale został nauczycielem matematyki, ponieważ nie było go stać na szkołę medyczną opłaty.
Uczęszczał na Uniwersytet Harvarda , gdzie uzyskał tytuł licencjata w 1955, magisterium w 1956 oraz doktorat. w stosowanych matematyki w 1959 roku rozpoczął pracę w IBM jest Thomas J. Watson Research Center . W 1968 został profesorem informatyki, matematyki i badań operacyjnych na Uniwersytecie Kalifornijskim w Berkeley . Poza 4-letnim stażem profesora na Uniwersytecie Waszyngtońskim pozostał w Berkeley. Od 1988 do 1995 i 1999 do chwili obecnej był również naukowcem w Międzynarodowym Instytucie Informatyki w Berkeley, gdzie obecnie kieruje Grupą Algorytmów.
Richard Karp został odznaczony National Medal of Science , a także laureatem Harvey Prize of the Technion oraz Benjamina Franklin Medal w dziedzinie Computer and Cognitive Science za jego spostrzeżenia na temat złożoności obliczeniowej . W 1994 został wprowadzony jako Fellow of the Association for Computing Machinery . Został wybrany do klasy 2002 Fellows z Instytutu Badań Operacyjnych i nauk o zarządzaniu . Jest laureatem kilku stopni honorowych.
W 2012 roku Karp został dyrektorem-założycielem Simons Institute for the Theory of Computing na Uniwersytecie Kalifornijskim w Berkeley .
Praca
Karp dokonał wielu ważnych odkryć w informatyce, algorytmach kombinatorycznych i badaniach operacyjnych . Jego główne aktualne zainteresowania badawcze obejmują bioinformatykę .
W 1971 roku opracowany wspólnie z Jackiem Edmonds ten algorytm Edmonds-Karp dla rozwiązania problemu przepływu maksymalnego w sieciach, aw 1972 roku opublikował przełomową w teorii złożoności, „redukowalność Wśród problemów kombinatorycznych”, w którym udowodnił 21 problemy się NP-zupełne .
W 1973 roku wraz z Johnem Hopcroftem opublikowali algorytm Hopcrofta-Karpa , najszybszą znaną metodę znajdowania maksymalnych dopasowań kardynalności w grafach dwudzielnych .
W 1980 roku, wraz z Richardem J. Liptonem , Karp udowodnił twierdzenie Karpa-Liptona (które dowodzi, że jeśli SAT można rozwiązać za pomocą układów logicznych z wielomianową liczbą bramek logicznych , to hierarchia wielomianowa załamuje się do drugiego poziomu).
W 1987 roku opracowany wspólnie z Michael O. Rabin algorytm wyszukiwania ciąg Rabin-Karp .
Nagroda Turinga
Jego cytat z nagrody Turinga (1985) był następujący:
Za jego stały wkład w teorię algorytmów, w tym opracowanie wydajnych algorytmów dla przepływu sieciowego i innych problemów optymalizacji kombinatorycznej, identyfikację obliczalności w czasie wielomianowym z intuicyjnym pojęciem wydajności algorytmicznej , a przede wszystkim wkład w teorię NP -kompletność . Karp wprowadził standardową obecnie metodologię udowadniania problemów jako NP-zupełnych, co doprowadziło do zidentyfikowania wielu problemów teoretycznych i praktycznych jako trudnych obliczeniowo.
Bibliografia
- ^ a b Richard M. Karp w projekcie Genealogia Matematyki .
- ^ Richard Manning Karp - NAGRODA KYOTO 2008 - Zaawansowana technologia
- ^ a b Moc i granice algorytmów Richard Manning Karp, Kyoto Prize Address, 2008
- ^ Stypendyści: Lista alfabetyczna , Instytut Badań Operacyjnych i Nauk o Zarządzaniu , pobrane 09.10.2019
- ^ „Kalifornia wybrana jako dom dla Instytutu Informatyki” . New York Times . 30 kwietnia 2012 . Źródło 23 października 2016 .
- ^ Richard M. Karp (1972). „Sprowadzalność wśród problemów kombinatorycznych” (PDF) . W RE Miller; JW Thatcher (wyd.). Złożoność obliczeń komputerowych . Nowy Jork: Plenum. s. 85–103.
- ^ Stowarzyszenie Maszyn Komputerowych. "ACM Award Citation/Richard M. Karp" . Zarchiwizowane od oryginału w dniu 2012-07-03 . Źródło 2010-01-17 .
Linki zewnętrzne
- Wywiad/bio Richarda Karpa w magazynie ACM Crossroads
- Strona domowa Karpa w Berkeley
- Biografia Richarda Karpa z Instytutu Badań Operacyjnych i Nauk o Zarządzaniu
| Poprzedzał John McCarthy |
Medal Benjamina Franklina w dziedzinie informatyki i kognitywistyki 2004 |
Następca Aravind Joshi |