Richard Karp

Richard Manning Karp (* 3. január 1935, Boston, Massachusetts, USA) je americký informatik. Je známy najmä vďaka výskumu v oblasti teórie algoritmov a výpočtovej zložitosti, za ktorý dostal v roku 1985 dostal Turingovu cenu. Zaoberá sa však aj mnohými ďalšími oblasťami informatiky a operačnej analýzy, ako sú napríklad kombinatorické algoritmy alebo bioinformatika.

Život 

Richard Karp sa narodil v roku 1935 v Bostone, Massachusetts, USA ako syn Abrahama Karpa a Rose Karpovej. Mal troch mladších súrodencov: Roberta, Davida (profesor sociológie na Vysokej škole v Bostone) a Carolyn. Študoval na Harvardovej univerzite, kde v roku 1955 získal titul bakalára, v roku 1956 titul magistra a v roku 1959 titul PhD. v oblasti aplikovanej matematiky.

Po ukončení štúdií začal pracovať pre IBM vo Výskumnom centre Thomasa J. Watsona. V roku 1968 sa stal profesorom informatiky, matematiky a operačnej analýzy na Kalifornskej univerzite v Berkeley, kde, až na štvorročné obdobie pôsobenia na Washingtonskej univerzite, zotrval dodnes.

Práca 

V roku 1971, spolu s Jackom Edmondsom, objavil tzv. Edmonsov-Karpov algoritmus (často zamieňaný za Fordov-Fulkersonov algoritmus, ktorého je špeciálnym prípadom) na hľadanie maximálneho toku v sietiach. V roku 1972 publikoval významný článok v oblasti výpočtovej zložitosti, Reducibility Among Combinatorial Problems, v ktorom o 21 problémoch dokázal, že sú NP-úplné. V roku 1973, spoločne s Johnom Hopcroftom, publikoval Hopcroftov-Karpov algoritmus, ktorý je dodnes najefektívnejšou metódou na hľadanie maximálneho párenia v bipartitných grafoch.

V roku 1980 spolu s Richardom Liptonom dokázal tzv. Karpovu-Liptonovu vetu, významný výsledok v teórii booleovských obvodov. V roku 1987 spolu s Michaelom Oserom Rabinom objavil tzv. Rabinov-Karpov algoritmus na vyhľadávanie v texte.

V roku 1985 dostal Turingovu cenu najmä za svoju prácu v oblasti výpočtovej zložitosti a teórie algoritmov, pričom v zdôvodnení sa špeciálne zdôrazňuje jeho prínos teórii NP-úplnosti.

Iné projekty

Externé odkazy 
 Článok o Karpovi

Držitelia Turingovej ceny
Informatici USA
Informatici židovského pôvodu
Matematici USA
Matematici židovského pôvodu
Osobnosti USA židovského pôvodu
Priekopníci informatiky
Osobnosti z Bostonu (Massachusetts)