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

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

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

Биография

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

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

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

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

Достижения

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

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

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

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

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

Награды

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

См. также

Примечания

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

Ссылки

Биография Рабина на сайте Гарвардского университета (недоступная ссылка с 13-05-2013 [4010 дней] — история) (англ.)
Karp, RM; Rabin, MO (March 1987). «Efficient randomized pattern-matching algorithms». IBM Journal of Research and Development. 31 (2): 249—260.
Harvard awards 10 honorary degrees

[cv-1] 1,0 ^1,1 Источник (неопр.). Дата обращения: 16 сентября 2008. Архивировано 2 октября 2008 года.

[ei-2] 2,0 ^2,1 ^2,2 Einstein Institute of Mathematics, The Hebrew University — About the Institute: Prizes (неопр.). Дата обращения: 16 сентября 2008. Архивировано 25 мая 2011 года.

[3] ACM Award Citation / Michael O. Rabin Архивная копия от 18 июня 2007 на Wayback Machine (англ.)

[4] «Rabin awarded 2004 EMET Prize» Архивная копия от 6 января 2011 на Wayback Machine, Harvard University Gazette, 16 декабря 2004 года (англ.)

[1]

[2]

[3]

[4]