Michał O. Rabin - Michael O. Rabin
Michael Oser Rabin | |
|---|---|
 | |
| Urodzić się |
1 września 1931 |
| Narodowość | izraelski |
| Alma Mater |
Hebrajski Uniwersytet w Jerozolimie ( mgr ) Uniwersytet Princeton ( doktorat ) |
| Znany z |
Test pierwszości Millera–Rabina Kryptosystem Rabina Przeniesienie nieświadome Algorytm przeszukiwania łańcuchów Rabina–Karpa Niedeterministyczne automaty skończone Algorytmy randomizowane |
| Nagrody |
Nagroda Turinga (1976) Nagroda Paris Kanellakis (2003) Nagroda Izraela Nagroda EMET Nagroda Harveya Nagroda Dana Davida Nagroda Dijkstry Nagroda IEEE Computer Society Nagroda Charlesa Babbage |
| Kariera naukowa | |
| Pola | Informatyka |
| Instytucje |
Harvard University Hebrajski Uniwersytet w Jerozolimie Columbia University |
| Praca dyplomowa | Rekurencyjna nierozwiązywalność problemów teorii grup (1957) |
| Doradca doktorski | Kościół Alonza |
| Doktoranci | |
Michael Oser Rabin ( hebr . מִיכָאֵל עוזר רַבִּין ; urodzony 1 września 1931) jest izraelskim matematykiem i informatykiem, laureatem nagrody Turinga .
Biografia
Wczesne życie i edukacja
Rabin urodził się w 1931 roku w Breslau , Niemcy (obecnie we Wrocławiu , w Polsce ), syn rabina . W 1935 wyemigrował z rodziną do Mandatu Palestyny . Jako młody chłopak bardzo interesował się matematyką, a ojciec wysłał go do najlepszej szkoły średniej w Hajfie , gdzie uczył się pod kierunkiem matematyka Elisha Netanjahu , który był wówczas nauczycielem w liceum.
Rabin ukończył szkołę hebrajską Reali w Hajfie w 1948 roku i został powołany do wojska podczas wojny arabsko-izraelskiej w 1948 roku . Matematyk Abraham Fraenkel , który był profesorem matematyki w Jerozolimie , interweniował w dowództwie armii, a Rabin został zwolniony na studia na uniwersytecie w 1949 roku.
Otrzymał tytuł mgr inż. z Uniwersytetu Hebrajskiego w Jerozolimie w 1953 oraz doktorat. z Uniwersytetu Princeton w 1956 roku.
Kariera zawodowa
Rabin został profesorem nadzwyczajnym matematyki na Uniwersytecie Kalifornijskim w Berkeley (1961–62) i MIT (1962–63). Zanim przeniósł się na Uniwersytet Harvarda jako Gordon McKay Professor of Computer Science w 1981 roku, był profesorem na Hebrajskim Uniwersytecie.
Pod koniec lat pięćdziesiątych został zaproszony na lato, aby razem z innymi obiecującymi matematykami i naukowcami prowadzić badania dla IBM w posiadłości Lamb Estate w hrabstwie Westchester w stanie Nowy Jork . To właśnie tam on i Dana Scott napisali artykuł „Skończone automaty i ich problemy z decyzjami”. Wkrótce, używając niedeterministycznych automatów, byli w stanie ponownie udowodnić wynik Kleene'a, że maszyny skończone stany dokładnie akceptują języki regularne.
Jeśli chodzi o początki tego, co miało stać się teorią złożoności obliczeniowej , następnego lata Rabin powrócił do Lamb Estate. John McCarthy zadał mu zagadkę dotyczącą szpiegów, strażników i haseł, którą Rabin studiował i wkrótce po tym, jak napisał artykuł „Stopień trudności obliczania funkcji i hierarchii zbiorów rekurencyjnych”.
Maszyny niedeterministyczne stały się kluczowym pojęciem w teorii złożoności obliczeniowej, szczególnie wraz z opisem klas złożoności P i NP .
Rabin wrócił następnie do Jerozolimy, badając logikę i pracując nad podstawami tego, co później będzie znane jako informatyka . Był profesorem nadzwyczajnym i kierownikiem Instytutu Matematyki na Uniwersytecie Hebrajskim w wieku 29 lat, a profesorem zwyczajnym w wieku 33 lat. Rabin wspomina: „Nie było absolutnie żadnego uznania dla pracy nad zagadnieniami informatyki. rozpoznać wyłaniającą się nową dziedzinę”.
W 1960 roku został zaproszony przez Edwarda F. Moore'a do pracy w Bell Labs , gdzie Rabin wprowadził automaty probabilistyczne, które wykorzystują rzuty monetą w celu decydowania, jakie zmiany stanów wykonać. Pokazał przykłady języków regularnych, które wymagały bardzo dużej liczby stanów, ale dla których uzyskuje się wykładniczą redukcję liczby stanów, jeśli przejdziesz do automatów probabilistycznych.
1969, Rabina wykazały, że w drugim rzędzie rachunku z n następców jest rozstrzygalne . Kluczowym elementem dowodu niejawnie pokazał gry nieskończone z gier parzystości , które leżą w trzecim poziomie hierarchii Borel .
W 1975 roku Rabin zakończył swoją kadencję jako rektor Uniwersytetu Hebrajskiego w Jerozolimie i udał się do Massachusetts Institute of Technology w USA jako profesor wizytujący. Gary Miller również tam był i miał swój wielomianowy test czasu dla pierwszości w oparciu o rozszerzoną hipotezę Riemanna . Tam Rabin wynalazł test pierwszości Millera-Rabina , randomizowany algorytm, który może bardzo szybko (ale z małym prawdopodobieństwem błędu) określić, czy liczba jest liczbą pierwszą . Metoda Rabina została oparta na wcześniejszej pracy Gary'ego Millera, która rozwiązała problem deterministycznie przy założeniu, że uogólniona hipoteza Riemanna jest prawdziwa, ale wersja testu Rabina nie zawierała takiego założenia. Szybkie testowanie pierwszości jest kluczem do udanej implementacji większości kryptografii z kluczem publicznym, a w 2003 roku Miller, Rabin, Robert M. Solovay i Volker Strassen otrzymali nagrodę Paris Kanellakis za pracę nad testowaniem pierwszości.
W 1976 roku został zaproszony przez Josepha Trauba na spotkanie na Carnegie Mellon University i przedstawił test pierwszości. Po wygłoszeniu tego wykładu Traub powiedział: „Nie, nie, to jest rewolucyjne i stanie się bardzo ważne”.
W 1979 r. Rabin wynalazł kryptosystem Rabin , pierwszy asymetryczny kryptosystem, którego bezpieczeństwo okazało się równoważne z niewykonalnością faktoryzacji liczb całkowitych .
W 1981 r. Rabin wymyślił na nowo słabą odmianę techniki nieświadomego przekazu wynalezioną przez Wiesnera pod nazwą multipleksacji, pozwalającą nadawcy transmitować wiadomość do odbiorcy, gdzie odbiorca ma pewne prawdopodobieństwo od 0 do 1 poznania wiadomości, z nadawca nie wie, czy odbiorca był w stanie to zrobić.
W 1987 roku Rabin wraz z Richard Karp , stworzył jedną z najbardziej znanych efektywnych algorytmów wyszukiwania łańcuch , ten algorytm wyszukiwania ciąg Rabin-Karp , znany ze swojej toczenia hash.
Najnowsze badania Rabina koncentrują się na bezpieczeństwie komputerowym. Obecnie jest profesorem informatyki Thomasa J. Watsona na Uniwersytecie Harvarda oraz profesorem informatyki na Uniwersytecie Hebrajskim . W semestrze wiosennym 2007 roku był profesorem wizytującym na Uniwersytecie Columbia, nauczając Wprowadzenie do kryptografii .
Nagrody i wyróżnienia
Rabin jest członkiem zagranicznym Narodowej Akademii Nauk Stanów Zjednoczonych , członkiem Francuskiej Akademii Nauk i członkiem zagranicznym Royal Society .
W 1976 r. Nagroda Turinga została przyznana wspólnie Rabinowi i Danie Scott za pracę napisaną w 1959 r., za której cytowanie stwierdza się, że nagroda została przyznana:
Za ich wspólny artykuł „Finite Automata and Their Decision Problems”, który przedstawił ideę maszyn niedeterministycznych, która okazała się niezwykle wartościową koncepcją. Ich (Scott i Rabin) [ sic ] klasyczny artykuł był ciągłym źródłem inspiracji do dalszych prac w tej dziedzinie.
W 1995 Rabin otrzymał Nagrodę Izraela w dziedzinie informatyki. W 2010 roku Rabin został wyróżniony Uniwersytecie w Tel Awiwie Dan David Prize (kategoria "Future"), wspólnie z Leonardem Kleinrock i Gordon E. Moore , dla komputerów i Telekomunikacji. Rabin otrzymał tytuł doktora honoris causa Uniwersytetu Harvarda w 2017 roku.
Zobacz też
- Nieoczywisty transfer
- Rabin automat
- Odcisk palca Rabina
- Hiperszyfrowanie
- Lista laureatów Nagrody Izraela