Майкл О. Рабин
Майкл Озер Рабин ( иврит : מיקאל אוזר רבינ ; родился 1 сентября 1931 года) — израильский математик , учёный-компьютерщик , лауреат премии Тьюринга .
Биография
[ редактировать ]Ранняя жизнь и образование
[ редактировать ]Рабин родился в 1931 году в Бреслау , Германия (сегодня Вроцлав , в Польше ), в семье раввина . В 1935 году он эмигрировал с семьей в подмандатную Палестину . В детстве он очень интересовался математикой, и отец отправил его в лучшую среднюю школу Хайфы , где он учился у математика Элиши Нетаньяху , который тогда был учителем средней школы. [ 1 ]
Рабин окончил еврейскую школу Реали в Хайфе в 1948 году и был призван в армию во время арабо-израильской войны 1948 года . Математик Авраам Френкель , который был профессором математики в Иерусалиме , вмешался в дела армейского командования, и Рабин был выписан на учебу в университет в 1949 году. [ 1 ] После этого он получил степень магистра наук в Еврейском университете в Иерусалиме . Он начал обучение в аспирантуре Пенсильванского университета, прежде чем получил степень доктора философии. из Принстонского университета в 1956 году. [ 2 ]
Карьера
[ редактировать ]Рабин стал доцентом кафедры математики Калифорнийского университета в Беркли (1961–62) и Массачусетского технологического института (1962–63). Прежде чем переехать в Гарвардский университет в качестве профессора компьютерных наук Гордона Маккея в 1981 году, он был профессором Еврейского университета. [ 3 ]
В конце 1950-х годов его пригласили на лето провести исследование для IBM в поместье Лэмб в округе Вестчестер, штат Нью-Йорк , вместе с другими многообещающими математиками и учеными. Именно там он и Дэйна Скотт написали статью «Конечные автоматы и проблемы их решения». [ 4 ] Вскоре, используя недетерминированные автоматы, они смогли повторно доказать результат Клини о том, что конечные автоматы в точности допускают регулярные языки. [ 1 ]
Что касается истоков того, что впоследствии стало теорией сложности вычислений , следующим летом Рабин вернулся в поместье Лэмбов. Джон Маккарти задал ему загадку о шпионах, охранниках и паролях, которую Рабин изучил и вскоре после этого написал статью «Степень сложности вычисления функции и иерархия рекурсивных множеств». [ 1 ] [ 5 ]
Недетерминированные машины стали ключевым понятием в теории сложности вычислений, особенно с описанием классов сложности P и NP .
Затем Рабин вернулся в Иерусалим, исследуя логику и работая над основами того, что позже станет известно как информатика . В 29 лет он был доцентом и главой Института математики Еврейского университета, а к 33 — профессором. Рабин вспоминает: «Работы по вопросам вычислений не получили абсолютно никакой оценки. Математики не оценили признать возникающую новую область». [ 1 ]
пригласил его В 1960 году Эдвард Ф. Мур работать в Bell Labs , где Рабин представил вероятностные автоматы , которые используют подбрасывание монеты, чтобы решить, какие переходы между состояниями предпринять. Он показал примеры регулярных языков, требующих очень большого количества состояний, но для которых можно получить экспоненциальное уменьшение количества состояний с помощью вероятностных автоматов. [ 1 ]
В 1966 г. (опубликовано в материалах конференции 1967 г.) [ 6 ] Рабин ввел понятие полиномиального времени (введенное независимо и незадолго до этого Кобэмом). [ 7 ] и Эдмондс [ 8 ] ).
В 1969 году Рабин представил автоматы с бесконечным деревом и доказал, что порядка монадическая теория второго n последователей ( S2S при n = 2) разрешима . [ 9 ] Ключевой компонент доказательства неявно показал детерминированность , игр на четность которые лежат на третьем уровне иерархии Бореля .
В 1975 году Рабин закончил свою должность ректора Еврейского университета в Иерусалиме и отправился в Массачусетский технологический институт в США в качестве приглашенного профессора. Там Рабин изобрел тест на простоту Миллера-Рабина — рандомизированный алгоритм, который может очень быстро (но с крошечной вероятностью ошибки) определить, является ли число простым . [ 10 ] [ 11 ] Метод Рабина был основан на предыдущей работе Гэри Миллера , которая решала проблему детерминистически, исходя из предположения, что обобщенная гипотеза Римана верна, но версия теста Рабина не делала такого предположения. Быстрое тестирование простоты является ключом к успешной реализации большей части криптографии с открытым ключом, и в 2003 году Миллер, Рабин, Роберт М. Соловей и Фолькер Штрассен были удостоены премии Парижа Канеллакиса за свою работу по тестированию простоты.
пригласил его В 1976 году Джозеф Трауб на встречу в Университете Карнеги-Меллон и представил тест на простоту, который Трауб назвал «революционным». [ 1 ]
В 1979 году Рабин изобрел криптосистему Рабина , первую асимметричную криптосистему, безопасность которой была доказана эквивалентной трудноразрешимости факторизации целых чисел . [ 12 ]
В 1981 году Рабин заново изобрел слабый вариант техники забывчивой передачи, изобретенной Визнером, под названием мультиплексирования. [ 13 ] позволяя отправителю передать сообщение получателю, при этом получатель имеет некоторую вероятность от 0 до 1 узнать сообщение, при этом отправитель не знает, смог ли получатель это сделать.
В 1987 году Рабин вместе с Ричардом Карпом создали один из самых известных эффективных алгоритмов поиска строк — алгоритм поиска строк Рабина-Карпа , известный своим скользящим хешем . [ 14 ]
Последние исследования Рабина были сосредоточены на компьютерной безопасности. В настоящее время он является Томаса Дж. Уотсона-старшего профессором компьютерных наук в Гарвардском университете и профессором компьютерных наук в Еврейском университете . В весеннем семестре 2007 года он был приглашенным профессором Колумбийского университета, преподававшим «Введение в криптографию» .
Награды и почести
[ редактировать ]Рабин — иностранный член Национальной академии наук США . [ 15 ] член Американского философского общества , [ 16 ] член Американской академии искусств и наук , [ 17 ] член Французской академии наук и иностранный член Королевского общества .
В 1976 году Премия Тьюринга была вручена совместно Рабину и Дане Скотт за статью, написанную в 1959 году, в цитате которой говорится, что награда была присуждена:
За их совместную статью «Конечные автоматы и их проблемы принятия решений», в которой была представлена идея недетерминированных машин, которая оказалась чрезвычайно ценной концепцией. Их классическая статья (Скотта и Рабина) [ sic ] была постоянным источником вдохновения для последующих работ в этой области. [ 18 ]
В 1995 году Рабин был удостоен Премии Израиля в области компьютерных наук. [ 19 ] В 2010 году Рабин был награжден Тель-Авивского университета премией Дэна Дэвида (категория «Будущее») совместно с Леонардом Кляйнроком и Гордоном Э. Муром в области компьютеров и телекоммуникаций. [ 20 ] В 2017 году Рабин был удостоен звания почетного доктора наук Гарвардского университета. [ 21 ]
Личная жизнь
[ редактировать ]У Рабина есть дочь, ученый-компьютерщик Таль Рабин . [ 22 ]
См. также
[ редактировать ]- Не обращающий внимания трансфер
- автомат Рабина
- Отпечаток пальца Рабина
- Гипершифрование
- Список лауреатов Премии Израиля
Ссылки
[ редактировать ]- ^ Jump up to: а б с д и ж г Шаша, Деннис (февраль 2010 г.). «Интервью с Майклом О. Рабином» . Коммуникации АКМ . 53 (2): 37–42. дои : 10.1145/1646353.1646369 . S2CID 16975542 . Архивировано из оригинала 13 марта 2016 г. Проверено 4 февраля 2010 г.
- ^ «Майкл О. Рабин» . amturing.acm. Архивировано из оригинала 28 ноября 2023 года . Проверено 14 августа 2023 г.
- ^ «Майкл О. Рабин - Биографическая справка» (PDF) . Гарвардский университет . Проверено 31 марта 2017 г.
- ^ Скотт, Дана ; Рабин, Майкл (1959). «Конечные автоматы и проблемы их решения» (PDF) . Журнал исследований и разработок IBM . 3 (2): 114–125. дои : 10.1147/рд.32.0114 . Архивировано из оригинала 4 марта 2016 года.
{{cite journal}}: CS1 maint: неподходящий URL ( ссылка ) - ^ Рабин, М.О., «Степень сложности вычисления функции и иерархия рекурсивных множеств», Технический отчет № 2, ONR, Еврейский университет, Иерусалим, 1960 г.
- ^ Рабин, Майкл О. (1967). «Математическая теория автоматов». Математические аспекты информатики. Учеб. Симпозиумы. Прил. Матем., Том. XIX . амер. Математика. Соц. стр. 153–175.
- ^ Кобэм, Алан (1965). «Внутренняя вычислительная сложность функций». Логика, методология и философия. наук. (Труды Интерн. конгр. 1964 г.) . стр. 24–30.
- ^ Эдмондс, Дж. (1965). «Дорожки, деревья и цветы». Канадская Дж. Математика . 17 : 449–467. дои : 10.4153/CJM-1965-045-4 . )
- ^ Рабин, Миссури (1969). «Разрешимость теорий и автоматов второго порядка на бесконечных деревьях» . Труды Американского математического общества . 141 : 1–35. дои : 10.2307/1995086 . JSTOR 1995086 . Архивировано из оригинала 12 июня 2020 г. Проверено 24 ноября 2007 г.
- ^ Рабин, Миссури (1976). «Вероятностные алгоритмы». Алгоритмы и сложность, Учеб. Симп . Питтсбург.
- ^ Рабин, Миссури (1980). «Вероятностный алгоритм проверки простоты» . Журнал теории чисел . 12 (1): 128–138. дои : 10.1016/0022-314X(80)90084-0 .
- ^ Рабин, Миссури (январь 1979 г.). «Цифровые подписи и функции открытого ключа, столь же неразрешимые, как факторизация» (PDF) . Технический отчет Лаборатории компьютерных наук Массачусетского технологического института . Архивировано из оригинала (PDF) 21 сентября 2006 г. Проверено 15 марта 2007 г.
- ^ Рабин, Майкл О. (1981). Как обмениваться секретами путем невнимательной передачи (Технический отчет TR-81) (PDF) . Вычислительная лаборатория Айкена: Гарвардский университет. Архивировано (PDF) из оригинала 23 ноября 2021 г. Проверено 15 марта 2007 г.
- ^ Карп, Р.М.; Рабин, Миссури (март 1987 г.). «Эффективные алгоритмы рандомизированного сопоставления с образцом» . Журнал исследований и разработок IBM . 31 (2): 249–260. дои : 10.1147/rd.312.0249 . S2CID 5734450 . Проверено 15 марта 2007 г.
- ^ «Майкл О. Рабин» . www.nasonline.org . Архивировано из оригинала 2 мая 2022 г. Проверено 2 мая 2022 г.
- ^ «История участников APS» . search.amphilsoc.org . Архивировано из оригинала 2 мая 2022 г. Проверено 2 мая 2022 г.
- ^ «Майкл Озер Рабин» . Американская академия искусств и наук . Архивировано из оригинала 2 мая 2022 г. Проверено 2 мая 2022 г.
- ↑ Цитирование премии ACM Тьюринга. Архивировано 14 июля 2012 г. на archive.today.
- ^ «Официальный сайт Премии Израиля – Лауреаты 1995 года (на иврите)» . Архивировано из оригинала 27 декабря 2008 г.
- ^ «Официальный сайт Премии Дэна Дэвида - Лауреаты 2010» . Архивировано из оригинала 6 марта 2010 года.
- ^ «Гарвард вручает 10 почетных степеней» . 25 мая 2017 г. Архивировано из оригинала 25 мая 2017 г. . Проверено 25 мая 2017 г.
- ^ «Таль Рабин» . Форбс . Архивировано из оригинала 26 октября 2022 года . Проверено 26 октября 2022 г.
Внешние ссылки
[ редактировать ]
- 1931 рождений
- Иностранные сотрудники Национальной академии наук
- Израильские математики
- Израильские ученые-компьютерщики
- Выпускники школы иврита реали
- Выпускники математического института Эйнштейна
- Академический состав Еврейского университета в Иерусалиме
- факультет Колумбийского университета
- Лауреаты премии Тьюринга
- Лауреаты премии Дейкстры
- Лауреаты Премии Израиля в области компьютерных наук
- Члены Израильской академии наук и гуманитарных наук
- Современные криптографы
- Логики
- Теоретики-компьютерщики
- Живые люди
- Иностранные члены Королевского общества
- Стипендиаты Международной ассоциации криптологических исследований
- Ученые-компьютерщики IBM Research
- сотрудники IBM
- Факультет математики Гарвардского университета
- Академический состав ETH Zurich
- Члены Американского философского общества
- Лауреаты премии Вейцмана