Narodziny |
1 st Wrzesień +1.931 Wrocław |
---|---|
Imię w języku ojczystym | Michael Oser Rabin |
Narodowość | izraelski |
Trening |
Hebrew University of Jerusalem Hebrew Reali School ( in ) Princeton University |
Zajęcia | Informatyk , matematyk , kryptograf , pedagog , profesor uniwersytetu |
Tata | Izrael Abraham Rabin ( d ) |
Rodzeństwo |
Miriam Ben-Peretz ( en ) Chaim Rabin ( en ) |
Pracował dla | Harvard University , New York University , California Institute of Technology , Technion , Massachusetts Institute of Technology , Columbia University , University of California at Berkeley , Swiss Federal Institute of Technology w Zurychu |
---|---|
Pole | Informatyka ( w ) |
Członkiem |
American Academy of Arts and Sciences American Philosophical Society Academy of Sciences Izraelska Akademia Nauk i Literatury Amerykańska Akademia Nauk (1984) Towarzystwo Królewskie (2007) |
Kierownik | Alonzo Church |
Nagrody |
Nagroda Turinga (1976) |
Michael Oser Rabin , urodzony dnia1 st Wrzesień +1.931we Wrocławiu w Niemczech , obecnie we Wrocławiu w Polsce ) jest izraelskim informatykiem i logikiem . Był laureatem nagrody Turinga , najbardziej prestiżowej nagrody w dziedzinie informatyki.
Rabin urodził się jako syn rabina . Uzyskał tytuł magistra na Uniwersytecie Hebrajskim w Jerozolimie w 1953 r. I doktorat na Uniwersytecie Princeton w 1956 r .
Odniesienie do nagrody Turinga, przyznanej w 1976 r. Wspólnie Michaelowi Rabinowi i Dana Scott za artykuł napisany w 1959 r. , Stwierdza, że nagroda została przyznana:
„Za swój artykuł„ Automaty skończone i ich problem decyzyjny ”przedstawiający ideę niedeterministycznych automatów skończonych, która okazała się pojęciem o ogromnej wartości. Ich klasyczny artykuł był ciągłym źródłem inspiracji dla dalszych prac w tej dziedzinie. "
Maszyny niedeterministyczne stały się kluczowym pojęciem w teorii złożoności , w szczególności przy opisie klas złożoności P i NP .
W 1957 i 1958 r. Rabin wykazał, że różne problemy grup teoretycznych są nierozstrzygalne (są to pierwsze tego typu problemy po problemach Siergieja Adiana z 1955 r.).
W 1969 Rabin wykazał, że arytmetyka monadyczna drugiego rzędu (z k następców) jest rozstrzygalna. To jest twierdzenie Rabina o drzewach .
W 1974 roku Rabin wykazał z Michelem Fischerem, że arytmetyka Presburgera ma super-wykładniczą złożoność.
W 1975 roku Rabin był pionierem algorytmów probabilistycznych . W szczególności wynalazł randomizowany algorytm , test pierwszości Millera-Rabina , który bardzo szybko, ale z niewielkim prawdopodobieństwem błędu, określa, czy liczba jest liczbą pierwszą. Algorytm ten jest niezbędny do implementacji większości asymetrycznych algorytmów kryptograficznych . Napisał również jeden z pierwszych probabilistycznych algorytmów geometrycznych, aby znaleźć dwa najbliższe punkty .
W 1979 roku Rabin wynalazł kryptosystem Rabin , który jest pierwszym asymetrycznym kryptosystemem, którego bezpieczeństwo sprowadza się do trudności z faktoryzacją liczby całkowitej .
W 1981 r. Rabin wynalazł technikę nieświadomego przekazu , pozwalającą nadawcy na przesłanie wiadomości do odbiorcy, tak aby ten ostatni miał pewne prawdopodobieństwo nauczenia się wiadomości, podczas gdy nadawca nic nie wie o sukcesie odbiorcy.
W 1987 roku Rabin i Richard Karp stworzyli efektywny algorytm najbardziej znanego ciągu znaków wyszukiwania , algorytmu Rabina-Karpa .
Obecne badania Rabin koncentrują się na bezpieczeństwie systemów komputerowych i obecnie jest profesorem katedry komputerowej Thomasa J. Watsona seniora na Uniwersytecie Harvarda oraz profesorem informatyki na Uniwersytecie Hebrajskim w Jerozolimie .