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

Для скрипача см. Майкл Рабин.
Майкл Осер Рабин
M O Rabin.jpg
Родившийся (1931-09-01) 1 сентября 1931 г. (возраст 89)
Бреслау, Германия
НациональностьИзраильский
Альма-матерЕврейский университет Иерусалима (Магистр )
Университет Принстона (кандидат наук )
ИзвестенТест на простоту Миллера – Рабина
Криптосистема Рабина
Незаметный перевод
Алгоритм поиска строки Рабина – Карпа
Недетерминированные конечные автоматы
Рандомизированные алгоритмы
НаградыПремия Тьюринга (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]

Что касается истоков того, что должно было стать теория сложности вычислений Следующим летом Рабин вернулся в поместье Лэмб. Джон Маккарти поставил перед ним загадку о шпионах, охранниках и паролях, которую Рабин изучил и вскоре после этого написал статью «Степень сложности вычисления функции и иерархии рекурсивных множеств».[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 году, в цитировании которой указано, что награда была присуждена:

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

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

Смотрите также

Рекомендации

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

внешняя ссылка