Michael O. Rabin

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Michael Ozer Rabin
Michael Rabin v říjnu 2009
Michael Rabin v říjnu 2009
Narozen 1. září 1931 (82 let)
Breslau, Výmarská republika (dnes Polsko)
Alma mater Hebrejská univerzita
Princetonská univerzita
Pracoviště Harvard University
Hebrejská univerzita
Columbia University
Obor informatika
Získaná ocenění Turingova cena, Izraelská cena a řada dalších

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]