Home » Знаменательные события » Михаэль Ошер Рабин

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

Михаэль Ошер Рабин (1 сентября 1931 года) — израильский учёный в области теории вычислительных систем, математик, лауреат премии Тьюринга и многих других премий.

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

Премия Тьюринга в 1976 году совместно с Дана Скоттом «за работу „Finite Automata and Their Decision Problem“, в которой вводится понятие недетерминированных конечных автоматов, ставших несомненно полезной концепцией.» Их труд стал постоянным источником вдохновения для дальнейшей работы в этой области». Недетерминированные конечные автоматы являются ключевым понятием в теории сложности вычислений, где с их помощью описывается класс NP.

Одно из важных достижений:
Вместе с Ричардом Карпом, Рабин разработал знаменитый алгоритм поиска образца (подстроки) в строке.
Алгоритм Рабина-Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте, используя хеширование.

Похожая информация:
Яндекс цитирования Яндекс.Метрика