Пратт, Вон Рональд
| Воан Рональд Пратт | |
|---|---|
| англ. Vaughan Ronald Pratt | |
 | |
| Дата рождения | 12 апреля 1944 (80 лет) |
| Место рождения | |
| Страна | |
| Род деятельности | специалист в области информатики, научный работник, преподаватель университета |
| Научная сфера | Информатика |
| Место работы | Стэнфордский университет, Массачусетский технологический институт |
| Альма-матер | |
| Научный руководитель | Дональд Кнут |
| Известен как | Один из авторов алгоритма Кнута — Морриса — Пратта, автор Шаблон:Iw5 и Шаблон:Iw5 |
| Награды и премии | |
| Сайт | profiles.stanford.edu/… (англ.) |
 Медиафайлы на Викискладе | |
Воан Рональд Пратт (англ. Vaughan Ronald Pratt, род. 12 апреля 1944 года, Мельбурн, Австралия) — эмерит-профессор Стэнфордского университета, один из первопроходцев теоретической информатики. С 1969 г. Пратт внёс существенный вклад в такие основополагающие области как Шаблон:Iw5, сортировки и проверки простоты. Его более современные исследования сосредоточены на формальном моделировании конкурентных систем и Шаблон:Iw5. Работы Пратта выделяются применением к информатике моделей из различных областей математики — геометрии, линейной и общей алгебры, математической логики.
Карьера
В 1970 г. Пратт защитил магистерскую диссертацию в Сиднейском университете в области, известной сейчас как обработка естественного языка. После этого он переехал в США, где спустя 20 месяцев защитил докторскую диссертацию под руководством Дональда Кнута. Темой его работы был анализ сортировки Шелла и сортирующих сетей.
Пратт занимал должность ассистент-профессора в MIT с 1972 г. по 1976 г., а затем экстраординарного профессора с 1976 г. по 1982 г. В 1974 году, совместно с Кнутом и Шаблон:Iw5, Пратт закончил и формализовал работу, начатую им в 1970 г. во время студенчества в Беркли. В результате данного соавторства появился Алгоритм Кнута — Морриса — Пратта. В 1976 г. Пратт разработал систему Шаблон:Iw5 — модальную логику структурированного поведения.
В 1980-1981 г. Пратт взял отпуск для научной работы в MIT и перешёл в Стэнфордский университет, где в 1981 г. получил профессорскую должность.
В 2000 г. Пратт стал эмерит-профессором Стэнфорда.
Основные достижения
Именем Пратта названы несколько известных алгоритмов. Предложенный Праттом Шаблон:Iw5 показал, что простота чисел может быть верифицирована за полиномиальное время. Из этого факта следовало, что задача проверки чисел на простоту лежит в классе NP, а значит, предположительно, не является co-NP полной[англ.][1]. Алгоритм Кнута — Морриса — Пратта, который Пратт разработал в начале 70-ых вместе с коллегой из Стэнфорда Дональдом Кнутом независимо от Морриса?!, является наиболее эффективным общим алгоритмом поиска подстрок известным в наши дни[2]. Вместе с Блюмом, Флойдом, Ривестом и Тарьяном Пратт описал медиану медиан (алгоритм BFRPT по инициалам авторов) — первый оптимальный алгоритм выбора порядковой статистики[3].
Примечания
- ↑ Vaughan Pratt. Every prime has a succinct certificate. SIAM Journal on Computing, vol.4, pp.214-220. 1975. Citations, Full-text (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
- ↑ Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E. Time bounds for selection (англ.) // Journal of Computer and System Sciences[англ.] : journal. — 1973. — August (vol. 7, no. 4). — P. 448—461. — doi:10.1016/S0022-0000(73)80033-9.
Ссылки
- Пратт, Вон Рональд (англ.) в проекте «Математическая генеалогия»
- Страница сотрудника на сайте Стэнфордского университета
- Страница аннотаций с полными текстами многих работ Пратта.
