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

Вы находитесь на сайте "Архив статей из ЭЕЭ и статей на еврейские темы из Википедии"

Версия от 08:33, 26 апреля 2012; Л.Гроервейдл (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Тип статьи: Текст унаследован из Википедии
Рабин, Михаэль Ошер
Michael Oser Rabin
Файл:Michael O. Rabin.jpg
Дата рождения:

1 сентября 1931(1931-09-01) (93 года)
Место рождения:

Вроцлав, Пруссия
Страна:

Израиль Израиль
Научная сфера:

Информатика
Место работы:

Гарвардский университет
Альма-матер:

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

Саарон Шела
Известен как:

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


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

Михаэль Ошер Рабин (нем. 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 — Премия Вейцмана по точным наукам[2]
  • 1974 — Премия Ротшильда по математике[2]
  • 1976 — Премия Тьюринга совместно с Дана Скоттом «за работу „Finite Automata and Their Decision Problem“, в которой вводится понятие недетерминированных конечных автоматов, ставших несомненно полезной концепцией. Их труд стал постоянным источником вдохновения для дальнейшей работы в этой области»[3] Недетерминированные конечные автоматы являются ключевым понятием в теории сложности вычислений, где с их помощью описывается класс NP.
  • 1980 — Премия Харви[2]
  • 1995 — Государственная премия Израиля по математике
  • 2000 — Премия Чарльза Беббиджа от IEEE
  • 2004 — Премия EMIT[4]
  • 2004 — Премия теории и практики Париса Канеллакиса (англ. Paris Kanellakis Theory and Practice Award)[1]

Литература

См. также

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

Ссылки

Примечания

  1. ↑ 1,0 1,1 http://people.seas.harvard.edu/~rabin/morpub.pdf
  2. ↑ 2,0 2,1 2,2 Einstein Institute of Mathematics, The Hebrew University — About the Institute: Prizes
  3. ↑ ACM Award Citation / Michael O. Rabin (англ.)
  4. ↑ «Rabin awarded 2004 EMET Prize», Harvard University Gazette, 16 декабря 2004 года(англ.)
Лауреаты премии Тьюринга

Перлис (1966) • Уилкс (1967) • Хэмминг (1968) • Минский (1969) • Уилкинсон (1970) • Маккарти (1971) • Дейкстра (1972) • Бахман (1973) • Кнут (1974) • Ньюэлл / Саймон (1975) • Рабин / Скотт (1976) • Бэкус (1977) • Флойд (1978) • Айверсон (1979) • Хоар (1980) • Кодд (1981) • Кук (1982) • Томпсон / Ритчи (1983) • Вирт (1984) • Карп (1985) • Хопкрофт / Тарьян (1986) • Кок (1987) • Сазерленд (1988) • Кэхэн (1989) • Корбато (1990) • Милнер (1991) • Лэмпсон (1992) • Хартманис / Стернс (1993) • Фейгенбаум / Редди (1994) • Блюм (1995) • Пнуели (1996) • Энгельбарт (1997) • Грей (1998) • Брукс (1999) • Яо (2000) • Даль / Нигаард (2001) • Ривест / Шамир / Адлеман (2002) • Кэй (2003) • Серф / Кан (2004) • Наур (2005) • Аллен (2006) • Кларк / Эмерсон / Сифакис (2007) • Лисков (2008) • Текер (2009)

 




bn:মাইকেল র‍্যাবিন cs:Michael O. Rabinid:Michael O. Rabin ja:マイケル・ラビン ko:마이클 라빈 nl:Michael Rabin pl:Michael O. Rabin pt:Michael Rabin ro:Michael Rabin sk:Michael Oser Rabin sr:Мајкл О. Рабин zh:迈克尔·拉宾Уведомление: Предварительной основой данной статьи была аналогичная статья в http://ru.wikipedia.org, на условиях CC-BY-SA, http://creativecommons.org/licenses/by-sa/3.0, которая в дальнейшем изменялась, исправлялась и редактировалась.

Источник — «http://www.jearc.info/wiki/%D0%A0%D0%B0%D0%B1%D0%B8%D0%BD,_%D0%9C%D0%B8%D1%85%D0%B0%D1%8D%D0%BB%D1%8C_%D0%9E%D1%88%D0%B5%D1%80»
Личные инструменты
 

Шаблон:Ежевика:Рубрики

Навигация
На других языках