Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Что касается скрипача, см. Майкл Рабин .
Майкл Осер Рабин
М.О. Рабин.jpg
Родившийся( 1931-09-01 )1 сентября 1931 г. (89 лет)
Бреслау , Германия
НациональностьИзраильский
Альма-матерЕврейский университет Иерусалима ( MSc )
Принстонский университет ( PhD )
ИзвестенТест на простоту Миллера – Рабина
Криптосистема Рабина
Незаметный перенос
Алгоритм поиска строки Рабина – Карпа
Недетерминированные конечные автоматы
Рандомизированные алгоритмы
НаградыПремия Тьюринга (1976)
Премия Пэрис Канеллакис (2003)
Премия Израиля Премия
EMET Премия
Харви Премия
Дэна Дэвида Премия
Дейкстры
IEEE Computer Society Премия Чарльза Бэббиджа
Научная карьера
ПоляИнформатика
УчрежденияГарвардский университет
Еврейский университет Иерусалима
Колумбийский университет
ТезисРекурсивная неразрешимость теоретико-групповых задач  (1957)
ДокторантЦерковь Алонсо
Докторанты

Майкл Осер Рабин ( иврит : מִיכָאֵל עוזר רַבִּין ; родился 1 сентября 1931 г.) - израильский математик и ученый-компьютерщик , лауреат премии Тьюринга .

Биография [ править ]

Ранняя жизнь и образование [ править ]

Рабин родился в 1931 году в Бреслау , Германия (сегодня Вроцлав , Польша ), в семье раввина . В 1935 году он эмигрировал со своей семьей в подмандатную Палестину . В детстве он очень интересовался математикой, и отец отправил его в лучшую среднюю школу Хайфы , где он учился у математика Элиша Нетаньяху , который тогда был учителем средней школы. [1]

После школы его призвали в армию во время арабо-израильской войны 1948 года . Математик Абрахам Френкель , который был профессором математики в Иерусалиме , вмешался в армейское командование, и Рабин был уволен учиться в университет в 1949 году [1].

Он получил степень магистра наук. окончил Еврейский университет в Иерусалиме в 1953 году и получил степень доктора философии. из Принстонского университета в 1956 году.

Карьера [ править ]

Рабин стал адъюнкт-профессором математики в Калифорнийском университете в Беркли (1961–62) и Массачусетском технологическом институте (1962–63). Прежде чем перейти в Гарвардский университет в качестве профессора компьютерных наук Гордона Маккея в 1981 году, он был профессором Еврейского университета. [2]

В конце 1950-х его пригласили на лето для проведения исследований для IBM в Lamb Estate в округе Вестчестер, штат Нью-Йорк, вместе с другими многообещающими математиками и учеными. Именно там он и Дана Скотт написали статью «Конечные автоматы и их проблемы принятия решений». [3] Вскоре, используя недетерминированные автоматы, они смогли повторно доказать результат Клини о том, что конечные автоматы точно принимают регулярные языки. [1]

Что касается истоков того, что должно было стать теорией вычислительной сложности , следующим летом Рабин вернулся в Lamb Estate. Джон Маккарти поставил перед ним загадку о шпионах, охранниках и паролях, которую Рабин изучил и вскоре после того, как написал статью «Степень сложности вычисления функции и иерархии рекурсивных множеств». [1] [4]

Недетерминированные машины стали ключевым понятием в теории сложности вычислений, особенно с описанием классов сложности P и NP .

Затем Рабин вернулся в Иерусалим, исследуя логику и работая над основами того, что позже будет известно как информатика . Он был адъюнкт-профессором и главой Института математики Еврейского университета в 29 лет, а в 33 года стал профессором. Рабин вспоминает: «Работа по вопросам вычислений не получила абсолютно никакой оценки. признать возникающее новое поле ". [1]

В 1960 году Эдвард Ф. Мур пригласил его работать в Bell Labs , где Рабин представил вероятностные автоматы, которые используют подбрасывание монеты, чтобы решить, какие переходы между состояниями предпринять. Он показал примеры регулярных языков, которые требовали очень большого количества состояний, но для которых вы получаете экспоненциальное уменьшение количества состояний, если переходите к вероятностным автоматам. [1]

В 1969 году Рабин доказал , что теория второго порядка из п преемников разрешима . [5] Ключевой компонент доказательства неявно показал детерминированность игр на четность , которые лежат на третьем уровне иерархии Бореля .

В 1975 году Рабин закончил свою должность ректора Еврейского университета в Иерусалиме и отправился в Массачусетский технологический институт в США в качестве приглашенного профессора. Гэри Миллер также был там и прошел свой полиномиальный временной тест на простоту, основанный на расширенной гипотезе Римана . Находясь там, Рабин изобрел тест простоты Миллера – Рабина , рандомизированный алгоритм, который может очень быстро (но с крошечной вероятностью ошибки) определить, является ли число простым . [6] [7] Метод Рабина был основан на предыдущей работе Гэри Миллера , в котором проблема решалась детерминированно с предположением, чтоОбобщенная гипотеза Римана верна, но версия теста Рабина не делает такого предположения. Быстрое тестирование на простоту является ключом к успешной реализации большей части криптографии с открытым ключом, и в 2003 году Миллер, Рабин, Роберт М. Соловей и Фолькер Штрассен были удостоены премии Париса Канеллакиса за их работу по проверке простоты.

В 1976 году он был приглашен Джозефом Траубом на встречу в университете Карнеги-Меллона и представил тест на простоту. После той лекции Трауб сказал: «Нет, нет, это революционно, и это станет очень важным». [1]

В 1979 году Рабин изобрел криптосистему Рабина , первую асимметричную криптосистему, безопасность которой оказалась эквивалентной неразрешимости целочисленной факторизации . [8]

В 1981 году Рабин заново изобрел слабый вариант техники неявной передачи, изобретенной Визнером под названием мультиплексирование, [9] позволяя отправителю передать сообщение получателю, где получатель имеет некоторую вероятность от 0 до 1 изучить сообщение. , при этом отправитель не знает, смог ли получатель это сделать.

В 1987 году Рабин вместе с Ричардом Карпом создал один из самых известных эффективных алгоритмов поиска по строкам , алгоритм поиска по строкам Рабина – Карпа , известный своим скользящим хешем. [10]

Недавнее исследование Рабина было сосредоточено на компьютерной безопасности. В настоящее время он является профессором компьютерных наук Томаса Дж. Уотсона-старшим в Гарвардском университете и профессором компьютерных наук в Еврейском университете . В весеннем семестре 2007 года он был приглашенным профессором Колумбийского университета и преподавал введение в криптографию .

Награды и награды [ править ]

Рабин - иностранный член Национальной академии наук США , член Французской академии наук и иностранный член Королевского общества .

В 1976 году премия Тьюринга была присуждена совместно Рабину и Дане Скотт за статью, написанную в 1959 году, в цитате говорится, что награда была присуждена:

За их совместную статью «Конечные автоматы и проблемы их решения», в которой была представлена ​​идея недетерминированных машин, которая оказалась чрезвычайно ценной концепцией. Их (Scott & Rabin) [ sic ] классическая статья была постоянным источником вдохновения для дальнейшей работы в этой области. [11]

В 1995 году Рабин был удостоен премии Израиля в области компьютерных наук. [12] В 2010 году Рабин был удостоен премии Тель-Авивского университета Дэна Дэвида (категория «Будущее») совместно с Леонардом Клейнроком и Гордоном Э. Муром за компьютеры и телекоммуникации. [13] Рабин был удостоен звания почетного доктора наук Гарвардского университета в 2017 году. [14]

См. Также [ править ]

  • Незаметный перевод
  • Автомат Рабина
  • Отпечаток пальца рабина
  • Гипер-шифрование
  • Список лауреатов премии Израиля

Ссылки [ править ]

  1. ^ a b c d e f g Шаша, Деннис (февраль 2010 г.). «Интервью с Майклом О. Рабиным» . Коммуникации ACM . 53 (2): 37–42. DOI : 10.1145 / 1646353.1646369 . S2CID  16975542 .
  2. ^ "Майкл О. Рабин - Биографическая справка" (PDF) . Гарвардский университет . Проверено 31 марта 2017 года .
  3. ^ Скотт, Дана ; Рабин, Майкл (1959). «Конечные автоматы и проблемы их решения» (PDF) . Журнал исследований и разработок IBM . 3 (2): 114–125. DOI : 10.1147 / rd.32.0114 . Архивировано 4 марта 2016 года. CS1 maint: неподходящий URL ( ссылка )
  4. ^ Рабин, М. О., «Степень сложности вычисления функции и иерархии рекурсивных множеств», Технический отчет № 2, ONR, Еврейский университет, Иерусалим, 1960
  5. Перейти ↑ Rabin, MO (1969). «Разрешимость теорий и автоматов второго порядка на бесконечных деревьях» . Труды Американского математического общества . 141 : 1–35. DOI : 10.2307 / 1995086 . JSTOR 1995086 . 
  6. Перейти ↑ Rabin, MO (1976). «Вероятностные алгоритмы». Алгоритмы и сложность, Тр. Symp . Питтсбург.
  7. Перейти ↑ Rabin, MO (1980). «Вероятностный алгоритм проверки простоты». Журнал теории чисел . 12 (1): 128–138. DOI : 10.1016 / 0022-314X (80) 90084-0 .
  8. ↑ Рабин, Миссури (январь 1979 г.). «Оцифрованные подписи и функции открытого ключа так же трудноразрешимы, как факторизация» (PDF) . Технический отчет Лаборатории компьютерных наук Массачусетского технологического института . Архивировано из оригинального (PDF) 21 сентября 2006 года . Проверено 15 марта 2007 .
  9. ^ Рабин, Майкл О. (1981). Как обмениваться секретами путем скрытой передачи (Технический отчет TR-81) (PDF) . Лаборатория вычислений Айкена: Гарвардский университет.
  10. ^ Карп, РМ; Рабин, Миссури (март 1987 г.). «Эффективные алгоритмы рандомизированного сопоставления с образцом» . Журнал исследований и разработок IBM . 31 (2): 249–260. DOI : 10.1147 / rd.312.0249 . Проверено 15 марта 2007 .
  11. ↑ ACM Turing Award Citation. Архивировано 14 июля 2012 г. в archive.today.
  12. ^ "Официальный сайт израильской премии - Получатели в 1995 году (на иврите)" . Архивировано из оригинала на 2008-12-27.
  13. ^ "Официальный сайт премии Дэна Дэвида - Лауреаты 2010" . Архивировано из оригинала 6 марта 2010 года.
  14. ^ "Гарвард присуждает 10 почетных степеней" .

Внешние ссылки [ править ]

  • Краткое описание в Зале славы информатики Питтсбургского университета
  • Незаметный перевод
  • Цитаты из занятий профессора Рабина
  • Сайт одного из курсов Рабина
  • Описание исследования Рабина на Ричарда Дж Lipton