Пратт, Вон Рональд (Hjgmm, Fku Jkugl,;)

Вон Рональд Пратт
Вон Рональд Пратт
	англ. Vaughan Ronald Pratt
Дата рождения	12 апреля 1944 (80 лет)
Место рождения	Мельбурн, Австралия;
Страна	Австралия;
Род деятельности	специалист в области информатики, научный работник, преподаватель университета
Научная сфера	информатика
Место работы	Стэнфордский университет; Массачусетский технологический институт;
Альма-матер	Стэнфордский университет; International House, The University of Sydney[вд];
Научный руководитель	Дональд Эрвин Кнут
Известен как	Один из авторов алгоритма Кнута — Морриса — Пратта, автор cертификата простоты Пратта и синтаксического анализатора Пратта[англ.]
Награды и премии	Фелло ACM (1997)
Сайт	profiles.stanford.edu/… (англ.)
	Медиафайлы на Викискладе

Вон Рональд Пратт (англ. Vaughan Ronald Pratt, род. 12 апреля 1944 года, Мельбурн, Австралия) — эмерит-профессор Стэнфордского университета, один из первопроходцев теоретической информатики. С 1969 г. Пратт внёс существенный вклад в такие основополагающие области как алгоритмы поиска^[англ.], сортировки и проверки простоты. Его более современные исследования сосредоточены на формальном моделировании конкурентных систем и пространств Чу^[англ.]. Работы Пратта выделяются применением к информатике моделей из различных областей математики — геометрии, линейной и общей алгебры, математической логики.

Карьера

В 1970 году Пратт защитил магистерскую диссертацию в Сиднейском университете в области, известной сейчас как обработка естественного языка. После этого он переехал в США, где спустя 20 месяцев защитил докторскую диссертацию под руководством Дональда Кнута. Темой его работы был анализ сортировки Шелла и сортирующих сетей.

Пратт занимал должность ассистент-профессора в MIT с 1972 год по 1976 год, а затем экстраординарного профессора с 1976 год по 1982 год. В 1974 году, совместно с Кнутом и Моррисом, Пратт закончил и формализовал работу, начатую им в 1970 год во время студенчества в Беркли. В результате данного соавторства появился Алгоритм Кнута — Морриса — Пратта. В 1976 год Пратт разработал систему динамической логики^[англ.] — модальную логику структурированного поведения.

В 1980-1981 годах Пратт взял отпуск для научной работы в MIT и перешёл в Стэнфордский университет, где в 1981 году получил профессорскую должность.

В 2000 году Пратт стал эмерит-профессором Стэнфорда.

Основные достижения

Именем Пратта названы несколько известных алгоритмов. Предложенный Праттом сертификат простоты показал, что простота чисел может быть верифицирована за полиномиальное время. Из этого факта следовало, что задача проверки чисел на простоту лежит в классе NP, а значит, предположительно, не является co-NP полной^[3]. Впоследствии был разработан полиномиальный алгоритм проверки числа на простоту. Алгоритм Кнута — Морриса — Пратта, который Пратт разработал в начале 70-х вместе с коллегой из Стэнфорда Дональдом Кнутом независимо от Морриса, является наиболее эффективным общим алгоритмом поиска подстрок известным в наши дни^[4]. Вместе с Блюмом, Флойдом, Ривестом и Тарьяном Пратт описал медиану медиан (алгоритм BFRPT по инициалам авторов) — первый оптимальный алгоритм выбора порядковой статистики^[5].

Примечания

↑ ¹ ² https://profiles.stanford.edu/vaughan-pratt
↑ Mathematics Genealogy Project (англ.) — 1997.
↑ Vaughan Pratt. Every prime has a succinct certificate. SIAM Journal on Computing, vol.4, pp.214-220. 1975. Citations Архивная копия от 6 июня 2008 на Wayback Machine, Full-text Архивная копия от 26 сентября 2007 на Wayback Machine (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 Архивная копия от 4 января 2010 на Wayback Machine
↑ 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. Архивировано 31 марта 2019 года.

Ссылки

Пратт, Вон Рональд (англ.) в проекте «Математическая генеалогия»
Страница сотрудника на сайте Стэнфордского университета Архивная копия от 14 августа 2011 на Wayback Machine
Страница аннотаций Архивная копия от 14 августа 2011 на Wayback Machine с полными текстами многих работ Пратта.

[_c773d85ebe854333-1] ¹ ² https://profiles.stanford.edu/vaughan-pratt

[_a19c080968bb2679-2] Mathematics Genealogy Project (англ.) — 1997.

[3] Vaughan Pratt. Every prime has a succinct certificate. SIAM Journal on Computing, vol.4, pp.214-220. 1975. Citations Архивная копия от 6 июня 2008 на Wayback Machine, Full-text Архивная копия от 26 сентября 2007 на Wayback Machine (requires paid login)

[4] Donald Knuth, James H. Morris, Jr., and Vaughan Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(2):323-350. 1977. Citations Архивная копия от 4 января 2010 на Wayback Machine

[5] 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. Архивировано 31 марта 2019 года.

[1]

[2]

[3]

[4]

[5]

Вон Рональд Пратт
англ. Vaughan Ronald Pratt

Дата рождения	12 апреля 1944(1944-04-12) (80 лет)
Место рождения	Мельбурн, Австралия
Страна	Австралия
Род деятельности	специалист в области информатики, научный работник, преподаватель университета
Научная сфера	информатика^[1]
Место работы	Стэнфордский университет^[1] Массачусетский технологический институт
Альма-матер	Стэнфордский университет International House, The University of Sydney^[вд]
Научный руководитель	Дональд Эрвин Кнут^[2]
Известен как	Один из авторов алгоритма Кнута — Морриса — Пратта, автор cертификата простоты Пратта и синтаксического анализатора Пратта^[англ.]
Награды и премии	Фелло ACM (1997)
Сайт	profiles.stanford.edu/… (англ.)
Медиафайлы на Викискладе