Михаэль Озер Рабин ( нем. Michael Oser Rabin , ивр. מִיכָאֵל עוזר רַבִּין ‎, род. 1 сентября 1931 , Вроцлав ) — израильский учёный в области теории вычислительных систем, математик, лауреат премии Тьюринга .

Биография

Михаэль Рабин родился в 1931 году в семье уроженца Проскурова , раввина Исраэля Аврахама Рабина в Бреслау (ныне Вроцлав ), принадлежавшем тогда Пруссии . В 1935 году его семья эмигрировала в Палестину . В 1953 году он получил степень магистра наук , окончив учёбу в Еврейском университете в Иерусалиме . Три года спустя, в 1956 году , защитил диссертацию в Принстонском университете и стал доктором философии .

Занимаелся исследованиями в области компьютерной безопасности и преподаёт в Иерусалиме и Гарварде . Имеет звания почётного профессора в следующих вузах:

• Университет Бордо (1996)
• Хайфский университет (1996)
• Открытый университет Израиля (почётный член, 1999)
• Университет Бен-Гуриона (2000)
• Вроцлавский университет (2007)

К его знаменитым ученикам относится Саарон Шелах , ныне профессор в Иерусалиме, лауреат премии Вольфа по математике.

Его дочь Таль Рабин руководит научной группой Cryptography and Privacy Research Group в компании IBM .

Достижения

В 1969 году Рабин обобщил на случай более одной функции следования, чем показал разрешимость соответствующей теории второго порядка . В ходе ведения доказательства он доказал детерминированность игр на чётность ( англ. parity games )

В 1975 году Гари Миллер разработал новый тест простоты, который был модифицирован Рабином в 1980 году. Тест Миллера — Рабина — вероятностный полиномиальный алгоритм, способный очень эффективно, но с ненулевой вероятностью ошибки, проверить число на простоту . Четыре года спустя, Майкл Рабин разработал первую асимметричную криптосистему , сложность взлома которой сравнима с проблемой факторизации целых чисел .

В 1981 году Рабин изобрёл протокол передачи данных с забыванием ( англ. oblivious transfer ) — надёжную технику передачи информации, при которой отправитель не получает подтверждения того, дошло ли сообщение до получателя. В 1987 году, вместе с Ричардом Карпом , Рабин разработал знаменитый алгоритм поиска образца (подстроки) в строке .

Награды

• 1960 — Премия Вейцмана по точным наукам
• 1973 — Премия Ротшильда по математике
• 1976 — Премия Тьюринга совместно с Дана Скоттом «за работу „Finite Automata and Their Decision Problem“, в которой вводится понятие недетерминированных конечных автоматов , ставших несомненно полезной концепцией. Их труд стал постоянным источником вдохновения для дальнейшей работы в этой области» Недетерминированные конечные автоматы являются ключевым понятием в теории сложности вычислений , где с их помощью описывается класс NP .
• 1980 — Премия Харви
• 1985 — Гиббсовская лекция
• 1995 — Государственная премия Израиля по математике
• 2000 — от IEEE
• 2001 — Мемориальные лекции Вейцмана
• 2003 — Премия Париса Канеллакиса
• 2004 — Премия ЭМЕТ
• 2010 — Премия Дэна Дэвида
• 2015 — Премия Дейкстры

См. также

• Алгоритм Рабина — Карпа
• Тест Миллера — Рабина

Примечания

Ссылки

• (недоступная ссылка с 13-05-2013 [3920 дней] — ) (англ.)
• Karp, RM; Rabin, MO (March 1987). «Efficient randomized pattern-matching algorithms». IBM Journal of Research and Development. 31 (2): 249—260.