Rabin, Michael

Michael Ozer Rabin ( německy  Michael Oser Rabin , hebrejsky מִיכָאֵל עוזר רַבִּין ‏‎, narozen 1. září 1931 , Wroclaw ) je izraelský počítačový vědec, další matematik a cena Turingze . Jeho dcera, Tal Rabin, vede Cryptography and Privacy Research Group v IBM .

Životopis

Michael Rabin se narodil v roce 1931 rodákovi z Proskurova , rabi Yisrael Avraham Rabin, v Breslau (nyní Wrocław ), která tehdy patřila Prusku . V roce 1935 jeho rodina emigrovala do Palestiny . V roce 1953 získal titul Master of Science na Hebrejské univerzitě v Jeruzalémě . O tři roky později, v roce 1956, dokončil svou disertační práci na Princetonské univerzitě a získal titul Ph.D.

V současné době (září 2008 ) Michael Rabin provádí výzkum v oblasti počítačové bezpečnosti a výuky v Jeruzalémě a na Harvardu . Má titul čestného profesora na těchto univerzitách: [1]

• Univerzita v Bordeaux (1996)
• Univerzita Haifa (1996)
• Open University of Israel (čestný člen, 1999)
• Ben Gurion University (2000)
• Wroclaw University (2007)

Mezi jeho slavné studenty patří Saharon Shelah , nyní profesorka v Jeruzalémě, vítězka Wolfovy ceny v matematice.

Úspěchy

V roce 1969 Rabin zobecnil Buchiho teorém na případ více než jedné důsledkové funkce, čímž ukázal rozhoditelnost odpovídající teorie druhého řádu . V průběhu dokazování dokázal determinismus her pro paritu ( anglicky  parity games )

V roce 1975 Gary Miller vyvinul nový test primality, který byl upraven Rabinem v roce 1980 . Miller-Rabinův test  je pravděpodobnostní polynomiální algoritmus, který dokáže velmi efektivně, avšak s nenulovou pravděpodobností chyby, testovat číslo na prvočíslo .

O čtyři roky později vyvinul Michael Rabin první asymetrický kryptosystém , jehož obtížnost je srovnatelná s problémem faktorizace celého čísla .

V roce 1981 Rabin vynalezl oblivious transfer protocol , spolehlivou techniku ​​přenosu informací ,  při které odesílatel neobdrží potvrzení, zda zpráva dorazila k příjemci.

V roce 1987 , spolu s Richardem Karpem , Rabin vyvinul slavný algoritmus pro nalezení vzoru (podřetězce) v řetězci .

Ocenění

• 1960  - Weizmannova cena za exaktní vědy [2]
• 1973  - Rothschildova cena v matematice [2]
• 1976  – Turing Award s Danou Scott „za práci „Finite Automata and Their Decision Problem“, která zavádí koncept nedeterministických konečných automatů , který se stal nepochybně užitečným konceptem. Jejich práce se stala stálým zdrojem inspirace pro další práci v této oblasti“ [3] Nedeterministické konečné automaty jsou klíčovým pojmem v teorii výpočetní složitosti , kde s jejich pomocí popisují třídu NP .
• 1980  – Harvey Award [2]
• 1985  – Gibbsova přednáška
• 1995  - Izraelská státní cena v matematice
• 2000  - Charles Babbage Award od IEEE
• 2001  - Weizmann Memorial Lectures
• 2003  - Paris Kanellakis Award [1]
• 2004  - EMET Award [4]
• 2010  - Cena Dana Davida
• 2015  - Cena Dijkstra

Viz také

• Rabin-Karpův algoritmus
• Miller-Rabinův test
• Rabinův otisk prstu
• Rabinova útočná puška

Poznámky

1. ↑ 1 2 Zdroj . Získáno 16. září 2008. Archivováno z originálu 2. října 2008. (neurčitý)
2. ↑ 1 2 3 Einsteinův institut matematiky, Hebrejská univerzita – O institutu: Ceny . Získáno 16. září 2008. Archivováno z originálu 25. května 2011. (neurčitý)
3. ↑ ACM Award Citation / Michael O. Rabin Archived 18. června 2007 na Wayback Machine 
4. ↑ „Rabin oceněn cenou EMET 2004“ Archivováno 6. ledna 2011 na Wayback Machine , Harvard University Gazette , 16. prosince 2004 

Odkazy

•  Biografie Rabina na stránkách  Harvardské univerzity
• Karp, R.M.; Rabin, MO (březen 1987). „Efektivní algoritmy náhodného porovnávání vzorů“. IBM Journal of Research and Development. 31(2): 249-260.
• Harvard uděluje 10 čestných titulů

Tematické stránky	Matematická genealogie Scopus zbMATH Otevřeno Všeruský matematický portál
Slovníky a encyklopedie	Britannica (online)
V bibliografických katalozích BNF : 150239741 ISNI : 0000 0000 7845 8063 J9U : 987007520695805171 NKC : skuk0004713 NTA : 151752370 SUDOC : 078079926 VIAF : 27345115 WorldCat VIAF : 27345115