Michael Oser Rabin

z Wikipédie, slobodnej encyklopédie
Verzia z 13:58, 15. september 2010, ktorú vytvoril YMS (diskusia | príspevky) (Added image)
Skočit na navigaci Skočit na vyhledávání
Michael Oser Rabin
Michael O. Rabin.jpg
izraelský informatik
Narodenie1. september 1931
Vroclav, Poľsko, vtedy Nemecko
Odkazy
CommonsSpolupracuj na Commons Michael Oser Rabin

Michael Oser Rabin (* 1. september 1931, Vroclav, Poľsko, vtedy Nemecko) je izraelský informatik. Spoločne s Danom Scottom v roku 1959 zaviedol koncept nedeterministického konečného automatu, ktorý sa stal mimoriadne dôležitým konceptom najmä vo výpočtovej zložitosti. Upravil tiež algoritmus Garyho Millera na testovanie prvočíselnosti - tento test prvočíselnosti je dnes známy ako Millerov-Rabinov test prvočíselnosti (1975). Rabin je tiež autorom tzv. Rabinovho kryptosystému (1979), asymetrickej kryptografickej techniky, ktorej bezpečnosť závisí, podobne ako bezpečnosť algoritmu RSA, na výpočtovej zložitosti problému rozkladu na prvočísla. V roku 1987 spolu s Richardom Karpom objavil tzv. Rabinov-Karpov algoritmus, jeden z najznámejších efektívnych algoritmov na vyhľadávanie v texte.

Za článok z roku 1959, v ktorom bol zavedený koncept nedeterministického konečného automatu, dostal v roku 1976, spolu s Danom Scottom, Turingovu cenu.