Richard Karp

z Wikipédie, slobodnej encyklopédie
Skočit na navigaci Skočit na vyhledávání
Richard Manning Karp
americký informatik
americký informatik
Narodenie3. január 1935 (83 rokov)
Boston, Massachusetts, USA
Odkazy
CommonsSpolupracuj na Commons 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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

Externé odkazy[upraviť | upraviť zdroj]