Майкл О. Рабин - Michael O. Rabin

Скрипкашы үшін қараңыз Майкл Рабин.
Майкл Осер Рабин
M O Rabin.jpg
Туған (1931-09-01) 1931 жылдың 1 қыркүйегі (89 жас)
Бреслау, Германия
ҰлтыИзраильдік
Алма матерИерусалимдегі Еврей университеті (Магистр )
Принстон университеті (PhD докторы )
БелгіліМиллер-Рабинге қатысты тест
Рабин криптожүйесі
Айқын аудару
Рабин – Карп жолдарын іздеу алгоритмі
Шектелмеген автоматтар
Кездейсоқ алгоритмдер
МарапаттарТюринг сыйлығы (1976)
Париж Канеллакис сыйлығы (2003)
Израиль сыйлығы
EMET сыйлығы
Харви сыйлығы
Дэн Дэвид сыйлығы
Дайкстра сыйлығы
IEEE Computer Society Чарльз Бэббидж атындағы сыйлық
Ғылыми мансап
ӨрістерИнформатика
МекемелерГарвард университеті
Иерусалимдегі Еврей университеті
Колумбия университеті
ДиссертацияТоптық теоретикалық мәселелердің рекурсивті шешілмеуі (1957)
Докторантура кеңесшісіАлонзо шіркеуі
Докторанттар

Майкл Осер Рабин (Еврей: מִיכָאֵל עוזר רַבִּין; 1931 жылы 1 қыркүйекте туған) - Израиль математик және информатик және алушы Тюринг сыйлығы.

Өмірбаян

Ерте өмірі және білімі

Рабин 1931 жылы дүниеге келген Бреслау, Германия (бүгін Вроцлав, жылы Польша ), а. ұлы раввин. 1935 жылы ол қоныс аударды отбасымен бірге Палестина мандаты. Жас кезінде ол математикаға өте қызығушылық танытты және әкесі оны ең жақсы орта мектепке жіберді Хайфа, онда ол математикадан оқыды Элиша Нетаньяху, ол кезде орта мектеп мұғалімі болған.[1]

Орта мектептен кейін ол армия қатарына шақырылды 1948 ж. Араб-Израиль соғысы. Математик Авраам Фраенкел математика профессоры болған Иерусалим, армия қолбасшылығына араласып, Рабин 1949 жылы университетте оқуға босатылды.[1]

Ол магистр дәрежесін алды бастап Иерусалимдегі Еврей университеті 1953 ж. және а Ph.D. бастап Принстон университеті 1956 жылы.

Мансап

Рабин математика кафедрасының доценті болды Калифорния университеті, Беркли (1961–62) және MIT (1962-63). Көшу алдында Гарвард университеті Гордон МакКей 1981 жылы информатика профессоры ретінде Еврей университетінің профессоры болған.[2]

1950 жылдардың аяғында оны жазда зерттеуге шақырды IBM Қозы жылжымайтын мүлік үйінде Вестчестер округі, Нью-Йорк басқа перспективалы математиктермен және ғалымдармен. Дәл сол жерде ол және Дана Скотт «Ақырлы автоматтар және оларды шешуге арналған мәселелер» мақаласын жазды.[3] Көп ұзамай, автоматты емес белгілерді қолдана отырып, олар қайтадан дәлелдей алды Клиннің ақырғы мемлекеттік машиналар қарапайым тілдерді дәл қабылдайтын нәтиже.[1]

Болашақтың бастауы туралы есептеу күрделілігі теориясы, келесі жазда Рабин Қозы Мүлікке оралды. Джон Маккарти оған тыңшылар, күзетшілер және құпия сөздер туралы жұмбақ қойды, оны Рабин зерттеді және ол көп ұзамай «Функцияны есептеудің қиындық дәрежесі және рекурсивті жиынтықтардың иерархиясы» атты мақала жазды.[1][4]

Терминистикалық емес машиналар есептеу күрделілігі теориясының негізгі ұғымына айналды, атап айтқанда P және NP күрделілік сыныптары.

Содан кейін Рабин Иерусалимге оралды, логиканы зерттеді және кейінірек белгілі болатын негіздердің үстінде жұмыс істеді Информатика. Ол 29 жасында Еврей университетінің доценті және Математика институтының жетекшісі және 33-тегі толық профессор болған. жаңа өрісті тану ».[1]

1960 жылы оны шақырды Мур жұмыс істеу Bell Labs, онда Рабин таныстырды ықтималдық автоматтары қандай мемлекеттік өтпелерді жасау керектігін шешу үшін монеталарды лақтыруды қолданатын. Ол өте көп күйлерді қажет ететін, бірақ ықтималдық автоматтарына көшсеңіз, күйлердің экспоненциалды қысқаруына ие болатын тұрақты тілдердің мысалдарын көрсетті.[1]

1969 жылы Рабин дәлелдеді екінші ретті теория туралы n мұрагерлері болып табылады шешімді.[5] Дәлелдеудің негізгі компоненті жанама түрде көрсетілген анықтау туралы паритет ойындары, үшінші деңгейінде орналасқан Борел иерархиясы.

1975 жылы Рабин Иерусалимдегі Еврей Университетінің ректоры қызметін аяқтап, университетке барды Массачусетс технологиялық институты АҚШ-та қонаққа келген профессор ретінде. Гари Миллер сол жерде де болған көпмүшелік негізіндегі уақытты тексеру кеңейтілген Риман гипотезасы. Рабин сол жерде болған кезде Миллер-Рабинге қатысты тест, санның бар-жоғын өте тез анықтайтын (бірақ қателіктер ықтималдығы аз) кездейсоқ алгоритм қарапайым.[6][7] Рабин әдісі алдыңғы жұмыстарға негізделген Гари Миллер деген болжаммен мәселені детерминалды түрде шешкен жалпыланған Риман гипотезасы бұл дұрыс, бірақ Рабиннің тест нұсқасы мұндай болжам жасаған жоқ. Жылдамдықты тестілеу ашық кілттердің көпшілігін сәтті жүзеге асыруда маңызды болып табылады, ал 2003 жылы Миллер, Рабин, Роберт М. Соловай, және Фолькер Страссен берілген Париж Канеллакис сыйлығы бірінші кезектегі тестілеу бойынша жұмыстары үшін.

1976 жылы оны шақырды Джозеф Труб кездесу Карнеги Меллон университеті және бірінші дәрежелі тест ұсынды. Ол сол дәрісті оқығаннан кейін, Труб: «Жоқ, жоқ, бұл революциялық және бұл өте маңызды болады», - деді.[1]

1979 жылы Рабин ойлап тапты Рабин криптожүйесі, қауіпсіздігі дәлелденген бірінші асимметриялық криптожүйе бүтін факторлау.[8]

1981 жылы Рабин техниканың әлсіз нұсқасын қайта ойлап тапты назар аудару Визнер мультиплексинг деп ойлап тапқан,[9] Жіберушіге хабарды алушының 0-ден 1-ге дейін үйрену ықтималдығы бар қабылдағышқа хабар жіберуге мүмкіндік беруі мүмкін, ал жіберуші алушының мұны істей алған-алмағаны туралы білмейді.

1987 жылы Рабин, бірге Ричард Карп, ең танымал тиімді құрылды жол іздеу алгоритмдері, Рабин – Карп жолдарын іздеу алгоритмі, өзінің айналмалы хэшімен танымал.[10]

Рабиннің соңғы зерттеулері компьютерлік қауіпсіздікке бағытталған. Ол қазіргі уақытта Томас Дж. Уотсон аға Информатика профессоры Гарвард университеті және информатика профессоры Еврей университеті. 2007 жылдың көктемгі семестрінде ол келуші профессор болды Колумбия университеті оқыту Кіріспе Криптография.

Марапаттар мен марапаттар

Рабин - шетелдік мүше Америка Құрама Штаттарының Ұлттық ғылым академиясы, мүшесіФранция ғылым академиясы және шетелдік мүше Корольдік қоғам.

1976 жылы Тюринг сыйлығы Рабинге бірлесіп марапатталды және Дана Скотт 1959 жылы жазылған мақала үшін, марапаттама берілгені туралы дәйексөз:

Үлгіге сыймайтын машиналар идеясын ұсынған «Шектелген автоматтар және оларды шешуге арналған мәселелер» бірлескен мақаласы үшін өте құнды ұғым болды. Олардың (Скотт және Рабин) [sic] классикалық қағаз осы саладағы кейінгі жұмыс үшін үздіксіз шабыт көзі болды.[11]

1995 жылы Рабин марапатталды Израиль сыйлығы, компьютерлік ғылымдарда.[12] 2010 жылы Рабин марапатталды Тель-Авив университеті Дэн Дэвид сыйлығы («Болашақ» санаты), бірге Леонард Клейнрок және Гордон Э. Мур, компьютерлер мен телекоммуникацияға арналған.[13] Рабинге 2017 жылы Гарвард университетінің құрметті ғылым докторы марапатталды.[14]

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ а б c г. e f ж Шаша, Деннис (Ақпан 2010). «Майкл О. Рабинмен сұхбат». ACM байланысы. 53 (2): 37–42. дои:10.1145/1646353.1646369. S2CID  16975542.
  2. ^ «Майкл О. Рабин - өмірбаяны» (PDF). Гарвард университеті. Алынған 31 наурыз 2017.
  3. ^ Скотт, Дана; Рабин, Майкл (1959). «Шекті автоматтар және оларды шешуге арналған мәселелер» (PDF). IBM Journal of Research and Development. 3 (2): 114–125. дои:10.1147 / rd.32.0114. 2016 жылдың 4 наурызында түпнұсқадан мұрағатталған.CS1 maint: жарамсыз url (сілтеме)
  4. ^ Рабин, М.О., «Рекурсивті жиынтықтардың функциясын және иерархиясын есептеу қиындықтарының дәрежесі», № 2 техникалық есеп, О.Н.Р., Еврей университеті, Иерусалим, 1960 ж.
  5. ^ Рабин, MO (1969). «Шексіз ағаштардағы екінші ретті теориялар мен автоматтардың шешімділігі». Американдық математикалық қоғамның операциялары. 141: 1–35. дои:10.2307/1995086. JSTOR  1995086.
  6. ^ Рабин, MO (1976). «Ықтималдық алгоритмдері». Алгоритмдер және күрделілік, Proc. Симптом. Питтсбург.
  7. ^ Рабин, MO (1980). «Басымдылықты тексерудің ықтимал алгоритмі». Сандар теориясының журналы. 12 (1): 128–138. дои:10.1016 / 0022-314X (80) 90084-0.
  8. ^ Рабин, MO (қаңтар 1979). «Факторлау сияқты шешілмейтін цифрлық қолтаңбалар мен ашық кілттер» (PDF). MIT информатика зертханасы Техникалық есеп. Архивтелген түпнұсқа (PDF) 21 қыркүйек 2006 ж. Алынған 2007-03-15.
  9. ^ Рабин, Майкл О. (1981). Құпия алмасу арқылы құпияларды қалай ауыстыруға болады (Техникалық есеп TR-81) (PDF). Айкенді есептеу зертханасы: Гарвард университеті.
  10. ^ Карп, RM; Рабин, MO (наурыз 1987). «Тиімді рандомизацияланған алгоритмдер». IBM Journal of Research and Development. 31 (2): 249–260. дои:10.1147 / rd.312.0249. Алынған 2007-03-15.
  11. ^ ACM Turing Award сілтемесі Мұрағатталды 2012-07-14 сағ Бүгін мұрағат
  12. ^ «Израиль сыйлығының ресми сайты - 1995 жылғы алушылар (иврит тілінде)». Архивтелген түпнұсқа 2008-12-27 ж.
  13. ^ «Дэн Дэвид сыйлығының ресми сайты - 2010 жылғы лауреаттар». Архивтелген түпнұсқа 6 наурыз 2010 ж.
  14. ^ «Гарвард 10 құрметті дәреже береді».

Сыртқы сілтемелер