Майкл О. Рабин
Майкл Озер Рабин ( иврит : מיקאל אוזר רבינ ; родился 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]
В 1969 году Рабин представил автоматы с бесконечным деревом и доказал, что монадическая теория второго порядка последователей n ( S2S при n = 2) разрешима . [6] Ключевой компонент доказательства неявно показал детерминированность игр на четность , которые лежат на третьем уровне иерархии Бореля .
В 1975 году Рабин закончил свою должность ректора Еврейского университета в Иерусалиме и отправился в Массачусетский технологический институт в США в качестве приглашенного профессора. Там Рабин изобрел тест на простоту Миллера-Рабина — рандомизированный алгоритм, который может очень быстро (но с крошечной вероятностью ошибки) определить, является ли число простым . [7] [8] Метод Рабина был основан на предыдущей работе Гэри Миллера , которая решала проблему детерминистически, исходя из предположения, что обобщенная гипотеза Римана верна, но версия теста Рабина не делала такого предположения. Быстрое тестирование простоты является ключом к успешной реализации большей части криптографии с открытым ключом, и в 2003 году Миллер, Рабин, Роберт М. Соловей и Фолькер Штрассен были удостоены премии Парижа Канеллакиса за свою работу по тестированию простоты.
пригласил его В 1976 году Джозеф Трауб на встречу в Университете Карнеги-Меллон и представил тест на простоту, который Трауб назвал «революционным». [1]
В 1979 году Рабин изобрел криптосистему Рабина , первую асимметричную криптосистему, безопасность которой была доказана эквивалентной трудноразрешимости факторизации целых чисел . [9]
В 1981 году Рабин заново изобрел слабый вариант техники забывчивой передачи , изобретенной Визнером, под названием мультиплексирования. [10] позволяя отправителю передать сообщение получателю, при этом получатель имеет некоторую вероятность от 0 до 1 узнать сообщение, при этом отправитель не знает, смог ли получатель это сделать.
В 1987 году Рабин вместе с Ричардом Карпом создали один из самых известных эффективных алгоритмов поиска строк — алгоритм поиска строк Рабина-Карпа , известный своим скользящим хешем . [11]
Последние исследования Рабина были сосредоточены на компьютерной безопасности. В настоящее время он является Томаса Дж. Уотсона-старшего профессором компьютерных наук в Гарвардском университете и профессором компьютерных наук в Еврейском университете . В весеннем семестре 2007 года он был приглашенным профессором Колумбийского университета, преподававшим «Введение в криптографию» .
Награды и почести [ править ]
Рабин — иностранный член Национальной академии наук США . [12] член Американского философского общества , [13] член Американской академии искусств и наук , [14] член Французской академии наук и иностранный член Королевского общества .
В 1976 году Премия Тьюринга была присуждена совместно Рабину и Дане Скотт за статью, написанную в 1959 году, в цитате которой говорится, что награда была присуждена:
За их совместную статью «Конечные автоматы и их проблемы принятия решений», в которой была представлена идея недетерминированных машин, которая оказалась чрезвычайно ценной концепцией. Их классическая статья (Скотта и Рабина) [ sic ] была постоянным источником вдохновения для последующих работ в этой области. [15]
В 1995 году Рабин был удостоен Премии Израиля в области компьютерных наук. [16] В 2010 году Рабин был награжден Тель-Авивского университета премией Дэна Дэвида (категория «Будущее») совместно с Леонардом Кляйнроком и Гордоном Э. Муром в области компьютеров и телекоммуникаций. [17] В 2017 году Рабин был удостоен звания почетного доктора наук Гарвардского университета. [18]
Личная жизнь [ править ]
У Рабина есть дочь, ученый-компьютерщик Таль Рабин . [19]
См. также [ править ]
- Не обращающий внимания трансфер
- автомат Рабина
- Отпечаток пальца Рабина
- Гипершифрование
- Список лауреатов Премии Израиля
Ссылки [ править ]
- ^ Перейти обратно: а б с д Это ж г Шаша, Деннис (февраль 2010 г.). «Интервью с Майклом О. Рабином» . Коммуникации АКМ . 53 (2): 37–42. дои : 10.1145/1646353.1646369 . S2CID 16975542 .
- ^ «Майкл О. Рабин» . amturing.acm . Проверено 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 г.
- ^ Рабин, Миссури (1969). «Разрешимость теорий и автоматов второго порядка на бесконечных деревьях» . Труды Американского математического общества . 141 : 1–35. дои : 10.2307/1995086 . JSTOR 1995086 .
- ^ Рабин, Миссури (1976). «Вероятностные алгоритмы». Алгоритмы и сложность, Учеб. Симп . Питтсбург.
- ^ Рабин, Миссури (1980). «Вероятностный алгоритм проверки простоты» . Журнал теории чисел . 12 (1): 128–138. дои : 10.1016/0022-314X(80)90084-0 .
- ^ Рабин, Миссури (январь 1979 г.). «Цифровые подписи и функции открытого ключа, столь же неразрешимые, как факторизация» (PDF) . Технический отчет Лаборатории компьютерных наук Массачусетского технологического института . Архивировано из оригинала (PDF) 21 сентября 2006 г. Проверено 15 марта 2007 г.
- ^ Рабин, Майкл О. (1981). Как обмениваться секретами путем невнимательной передачи (Технический отчет TR-81) (PDF) . Вычислительная лаборатория Айкена: Гарвардский университет.
- ^ Карп, Р.М.; Рабин, Миссури (март 1987 г.). «Эффективные алгоритмы рандомизированного сопоставления с образцом» . Журнал исследований и разработок IBM . 31 (2): 249–260. дои : 10.1147/rd.312.0249 . S2CID 5734450 . Проверено 15 марта 2007 г.
- ^ «Майкл О. Рабин» . www.nasonline.org . Проверено 2 мая 2022 г.
- ^ «История участников APS» . search.amphilsoc.org . Проверено 2 мая 2022 г.
- ^ «Майкл Озер Рабин» . Американская академия искусств и наук . Проверено 2 мая 2022 г.
- ↑ Цитирование премии ACM Тьюринга. Архивировано 14 июля 2012 г. на archive.today .
- ^ «Официальный сайт Премии Израиля – Лауреаты 1995 года (на иврите)» . Архивировано из оригинала 27 декабря 2008 г.
- ^ «Официальный сайт Премии Дэна Дэвида - Лауреаты 2010» . Архивировано из оригинала 6 марта 2010 года.
- ^ «Гарвард вручает 10 почетных степеней» . 25 мая 2017 г.
- ^ «Таль Рабин» . Форбс . Проверено 26 октября 2022 г.
Внешние ссылки [ править ]
- 1931 рождений
- Иностранные сотрудники Национальной академии наук
- Израильские математики
- Израильские ученые-компьютерщики
- Выпускники школы иврита реали
- Выпускники математического института Эйнштейна
- Академический состав Еврейского университета в Иерусалиме
- факультет Колумбийского университета
- Лауреаты премии Тьюринга
- Лауреаты премии Дейкстры
- Лауреаты Премии Израиля в области компьютерных наук
- Члены Израильской академии наук и гуманитарных наук
- Современные криптографы
- Логики
- Теоретики-компьютерщики
- Живые люди
- Иностранные члены Королевского общества
- Стипендиаты Международной ассоциации криптологических исследований
- Ученые-компьютерщики IBM Research
- сотрудники IBM
- Факультет математики Гарвардского университета
- Академический состав ETH Zurich
- Члены Американского философского общества
- Лауреаты премии Вейцмана