Михаэль Озер Рабин (, , 1 сентября 1931, Бреслау — 14 апреля 2026, Раанана) — израильский учёный в области теории вычислительных систем, математик, лауреат премии Тьюринга.
Биография Родился в семье уроженца Проскурова раввина Исраэля Аврахама Рабина. В 1935 году его семья эмигрировала в Палестину. В юном возрасте обучался математике у Элиши Нитаньяху. В 1953 году он получил степень , окончив учёбу в Еврейском университете в Иерусалиме. В 1956 году под руководством Алонзо Чёрч защитил диссертацию в Принстонском университете и стал доктором философии.
Вёл исследования в области компьютерной безопасности, преподавал в Еврейском университете в Иерусалиме и Гарварде. Почётный профессор университетов Бордо (1996), Хайфы (1996), Открытого университета Израиля (почётный член, 1999), Университета Бен-Гуриона (2000), Вроцлавского университета (2007).
Среди учеников — лауреат премии Вольфа по математике Саарон Шелах.
Дочь — Таль Рабин, руководитель научно-исследовательской группы по криптографии и конфиденциальности в корпорации IBM.
Научные результаты В 1969 году обобщил теорему Бюхи на случай более одной функции следования, чем показал разрешимость соответствующей теории второго порядка. В рамках доказательства также установлена детерминированность игр на чётность ().
В 1980 году модифицировал тест простоты Гари Миллера (1975), в результате был сформирован алгоритмический класс BPP — алгоритмов, способных очень эффективно, но с ненулевой вероятностью ошибки, проверить число на простоту. Четыре года спустя разработал первую асимметричную криптосистему, сложность взлома которой сравнима с проблемой факторизации целых чисел.
В 1981 году изобрёл протокол передачи данных с забыванием () — надёжную технику передачи информации, при которой отправитель не получает подтверждения того, дошло ли сообщение до получателя. В 1987 году совместно с Ричардом Карпом разработал знаменитый алгоритм поиска образца (подстроки) в строке.
Награды 1960 — Премия Вейцмана по точным наукам 1973 — Премия Ротшильда по математике 1976 — Премия Тьюринга совместно с Даной Скоттом за работу «Finite Automata and Their Decision Problem», в которой введено понятие недетерминированных конечных автоматовACM Award Citation / Michael O. Rabin , ставшее ключевым в теории сложности вычислений — с его помощью описывается класс NP 1980 — Премия Харви 1985 — Гиббсовская лекция 1995 — Государственная премия Израиля по математике 2000 — Премия Чарльза Беббиджа от IEEE 2001 — Мемориальные лекции Вейцмана 2003 — Премия Париса Канеллакиса 2004 — Премия ЭМЕТ«Rabin awarded 2004 EMET Prize» , Harvard University Gazette, 16 декабря 2004 года 2010 — Премия Дэна Дэвида 2015 — Премия Дейкстры
Примечания
Ссылки Биография Рабина на сайте Гарвардского университета 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
Категория:Выпускники Еврейского университета в Иерусалиме Категория:Выпускники Математического института имени Эйнштейна Еврейского университета в Иерусалиме Категория:Преподаватели Колумбийского университета Категория:Учёные в области информатики Израиля Категория:Иностранные члены Национальной академии наук США Категория:Иностранные члены Французской академии наук Категория:Иностранные члены Лондонского королевского общества Категория:Преподаватели вузов Израиля Категория:Лауреаты Государственной премии Израиля Категория:Лауреаты премии Вольфа (математика) Категория:Лауреаты премии Харви Категория:Криптографы Израиля Категория:Персоналии:Математическая логика Категория:Лауреаты премии Дэна Дэвида Категория:Лауреаты премии Ротшильда Категория:Почётные доктора Вроцлавского университета Категория:Почётные доктора Института Вейцмана Категория:Почётные доктора Хайфского университета Категория:Ректоры Еврейского университета в Иерусалиме