Русская Википедия:Пратт, Вон Рональд
Шаблон:Учёный Вон Рональд Пратт (Шаблон:Lang-en, род. 12 апреля 1944 года, Мельбурн, Австралия) — эмерит-профессор Стэнфордского университета, один из первопроходцев теоретической информатики. С 1969 г. Пратт внёс существенный вклад в такие основополагающие области как Шаблон:Iw, сортировки и проверки простоты. Его более современные исследования сосредоточены на формальном моделировании конкурентных систем и Шаблон:Iw. Работы Пратта выделяются применением к информатике моделей из различных областей математики — геометрии, линейной и общей алгебры, математической логики.
Карьера
В 1970 г. Пратт защитил магистерскую диссертацию в Сиднейском университете в области, известной сейчас как обработка естественного языка. После этого он переехал в США, где спустя 20 месяцев защитил докторскую диссертацию под руководством Дональда Кнута. Темой его работы был анализ сортировки Шелла и сортирующих сетей.
Пратт занимал должность ассистент-профессора в MIT с 1972 г. по 1976 г., а затем экстраординарного профессора с 1976 г. по 1982 г. В 1974 году, совместно с Кнутом и Моррисом, Пратт закончил и формализовал работу, начатую им в 1970 г. во время студенчества в Беркли. В результате данного соавторства появился Алгоритм Кнута — Морриса — Пратта. В 1976 г. Пратт разработал систему Шаблон:Iw — модальную логику структурированного поведения.
В 1980-1981 г. Пратт взял отпуск для научной работы в MIT и перешёл в Стэнфордский университет, где в 1981 г. получил профессорскую должность.
В 2000 г. Пратт стал эмерит-профессором Стэнфорда.
Основные достижения
Именем Пратта названы несколько известных алгоритмов. Предложенный Праттом сертификат простоты показал, что простота чисел может быть верифицирована за полиномиальное время. Из этого факта следовало, что задача проверки чисел на простоту лежит в классе NP, а значит, предположительно, не является co-NP полной[1]. Впоследствии был разработан полиномиальный алгоритм проверки числа на простоту. Алгоритм Кнута — Морриса — Пратта, который Пратт разработал в начале 70-ых вместе с коллегой из Стэнфорда Дональдом Кнутом независимо от Морриса, является наиболее эффективным общим алгоритмом поиска подстрок известным в наши дни[2]. Вместе с Блюмом, Флойдом, Ривестом и Тарьяном Пратт описал медиану медиан (алгоритм BFRPT по инициалам авторов) — первый оптимальный алгоритм выбора порядковой статистики[3].
Примечания
Ссылки
- Шаблон:MathGenealogy
- Страница сотрудника на сайте Стэнфордского университета Шаблон:Wayback
- Страница аннотаций Шаблон:Wayback с полными текстами многих работ Пратта.
- ↑ Vaughan Pratt. Every prime has a succinct certificate. SIAM Journal on Computing, vol.4, pp.214-220. 1975. Citations Шаблон:Wayback, Full-text Шаблон:Wayback (requires paid login)
- ↑ Donald Knuth, James H. Morris, Jr., and Vaughan Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(2):323-350. 1977. Citations Шаблон:Wayback
- ↑ Шаблон:Статья
