Рабин, Михаэль
Михаэль Озер Рабин | |
---|---|
нем. Michael Oser Rabin | |
| |
Дата рождения | 1 сентября 1931 (92 года) |
Место рождения | Вроцлав, Пруссия |
Страна |
|
Род деятельности | специалист в области информатики, математик, криптограф, педагог, преподаватель университета |
Научная сфера | информатика, математика |
Место работы | Гарвардский университет |
Альма-матер |
Еврейский университет в Иерусалиме, Принстонский университет |
Научный руководитель | А. Чёрч |
Ученики | Саарон Шелах |
Известен как |
Алгоритм Рабина — Карпа, Тест Миллера — Рабина |
Награды и премии | Премия Тьюринга |
Михаэль Озер Рабин (нем. 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 — Премия Дейкстры
См. также
[править | править код]Примечания
[править | править код]- ↑ An Interview with Michael Rabin – Communications of the ACM
- ↑ 1 2 Источник . Дата обращения: 16 сентября 2008. Архивировано 2 октября 2008 года.
- ↑ 1 2 3 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 [4114 дней] — история) (англ.)
- 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
- Родившиеся 1 сентября
- Родившиеся в 1931 году
- Персоналии по алфавиту
- Родившиеся во Вроцлаве
- Учёные по алфавиту
- Математики по алфавиту
- Математики Израиля
- Математики XX века
- Математики XXI века
- Лауреаты премии Тьюринга
- Лауреаты премии Канеллакиса
- Выпускники Еврейского университета в Иерусалиме
- Выпускники Математического института имени Эйнштейна Еврейского университета в Иерусалиме
- Учёные в области информатики Израиля
- Иностранные члены Национальной академии наук США
- Иностранные члены Французской академии наук
- Иностранные члены Лондонского королевского общества
- Преподаватели вузов Израиля
- Лауреаты Государственной премии Израиля
- Лауреаты премии Вольфа (математика)
- Лауреаты премии Харви
- Криптографы Израиля
- Персоналии:Математическая логика
- Лауреаты премии Дэна Дэвида
- Лауреаты премии Ротшильда
- Почётные доктора Вроцлавского университета
- Почётные доктора Института Вейцмана
- Почётные доктора Хайфского университета