Рабин, Михаэль Ошер

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Рабин, Михаэль Ошер
Michael Oser Rabin
Michael O. Rabin.jpg
Дата рождения:

1 сентября 1931({{padleft:1931|4|0}}-{{padleft:9|2|0}}-{{padleft:1|2|0}}) (83 года)

Место рождения:

Вроцлав, Пруссия

Страна:

Израиль

Научная сфера:

Информатика, математика

Место работы:

Гарвардский университет

Альма-матер:

Еврейский университет в Иерусалиме,
Принстонский университет

Научный руководитель:

А.Чёрч

Известные ученики:

Саарон Шела

Известен как:

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

Награды и премии


Премия Тьюринга

Рабин, Михаэль Ошер на Викискладе

Михаэль Ошер Рабин (нем. Michael Oser Rabin, ивр. מִיכָאֵל אֹשֶׁר רַבִּין‎, родился 1 сентября 1931 года, Вроцлав) — израильский учёный в области теории вычислительных систем, математик, лауреат премии Тьюринга и многих других премий. Его дочь, Таль Рабин, руководит научной группой Cryptography and Privacy Research Group в компании IBM.

Биография[править | править вики-текст]

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

В настоящее время (сентябрь 2008 года) Майкл Рабин занимается исследованиями в области компьютерной безопасности и преподаёт в Иерусалиме и Гарварде. Имеет звания почётного профессора в следующих вузах:[1]

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

Достижения[править | править вики-текст]

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

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

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

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

В 1987 году, вместе с Ричардом Карпом, Рабин разработал знаменитый алгоритм поиска образца (подстроки) в строке.

Награды[править | править вики-текст]


Литература[править | править вики-текст]

См. также[править | править вики-текст]

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

Примечания[править | править вики-текст]