Michael O. Rabin

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání
Michael Ozer Rabin
Narození1. září 1931 (90 let)
Breslau, Výmarská republika (dnes Polsko)
Alma materHebrejská univerzita
Princetonská univerzita
PracovištěHarvard University
Hebrejská univerzita
Columbia University
Oborinformatika
OceněníTuringova cena, Izraelská cena a řada dalších
RodičeIsrael Abraham Rabin a Ester Rabin
PříbuzníMiriam Ben-Peretz[1] a Chaim Rabin[1] (sourozenci)
Některá data mohou pocházet z datové položky.

Michael Ozer Rabin (hebrejsky מִיכָאֵל עוזר רַבִּין, ‎* 1. září 1931, Breslau) je izraelský informatik. V roce 1959 zavedl společně s Dana Scottem koncept nedeterministického konečného automatu, který se stal mimořádně důležitým konceptem především ve výpočtové složitosti. Upravil též algoritmus Garyho Millera na testování prvočíselnosti – tento test prvočíselnosti je dnes známý jako Millerův-Rabinův test prvočíselnosti (1975). Rabin je též autorem tzv. Rabinova kryptosystému (1979), asymetrické kryptografické techniky, jejíž bezpečnost závisí, podobně jako bezpečnost algoritmu RSA, na výpočtové složitosti problému rozkladu na prvočísla. V roce 1987 objevil společně s Richardem Karpem tzv. Rabinův-Karpův algoritmus, což je efektivní algoritmus na vyhledávání v textu.

Za článek z roku 1959, ve kterém byl zavedený koncept nedeterministického konečného automatu, dostal v roce 1976 společně s Danem Scottem Turingovu cenu.

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Michael Oser Rabin na slovenské Wikipedii.

Externí odkazy[editovat | editovat zdroj]