Рабин, Михаэль

Михаэль Озер Рабин
нем. Michael Oser Rabin
Дата рождения 1 сентября 1931(1931-09-01) (94 года)
Место рождения Вроцлав, Пруссия
Страна  Израиль
Род деятельности специалист в области информатики, математик, криптограф, педагог, преподаватель университета
Научная сфера информатика, математика
Место работы Гарвардский университет
Альма-матер Еврейский университет в Иерусалиме,
Принстонский университет
Научный руководитель А. Чёрч
Ученики Саарон Шелах
Известен как Алгоритм Рабина — Карпа,
Тест Миллера — Рабина
Награды и премии
Премия Тьюринга
Логотип Викисклада Медиафайлы на Викискладе

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

Биография

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

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

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

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

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

Достижения

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

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

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

Награды

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

См. также

  • Алгоритм Рабина — Карпа
  • Тест Миллера — Рабина
  • Отпечаток пальца Рабина
  • Автомат Рабина

Примечания

  1. ↑ An Interview with Michael Rabin – Communications of the ACM. Дата обращения: 15 апреля 2024. Архивировано 14 апреля 2024 года.
  2. ↑ 1 2 Источник. Дата обращения: 16 сентября 2008. Архивировано 2 октября 2008 года.
  3. ↑ 1 2 3 Einstein Institute of Mathematics, The Hebrew University — About the Institute: Prizes. Дата обращения: 16 сентября 2008. Архивировано 25 мая 2011 года.
  4. ↑ ACM Award Citation / Michael O. Rabin Архивная копия от 18 июня 2007 на Wayback Machine (англ.)
  5. ↑ «Rabin awarded 2004 EMET Prize» Архивная копия от 6 января 2011 на Wayback Machine, Harvard University Gazette, 16 декабря 2004 года (англ.)

Ссылки

Эта статья взята у (из) Википедия. Текст лицензируется по Creative Commons Attribution-Share Alike 4.0. К медиа файлам могут применятся дополнительные условия.