Воган Пратт

Воган Пратт
Воган Пратт
Рожденный	Вон Рональд Пратт ; 12 апреля 1944 г. (80 лет) ; Мельбурн , Австралия
Образование	Стэнфордский университет (1972) ; Сиднейский университет (1970)
Известный	Алгоритм Кнута – Морриса – Пратта ; Сертификат Пратта ; Парсер Пратта
	Научная карьера
Поля	Информатика
Учреждения	Стэнфордский университет ; С
Научные консультанты	Дональд Кнут
Докторанты	Пархам Аараби ; Дэвид Харел ; Дэвид Магерман ; Анна Паттерсон ;
Веб-сайт	буль Стэнфорд .edu /пратт .html

Воган Пратт (родился 12 апреля 1944 года) — почетный профессор Стэнфордского университета , пионер в области информатики . С 1969 года Пратт внес несколько вкладов в такие основополагающие области, как алгоритмы поиска , алгоритмы сортировки и тестирование на простоту . Совсем недавно его исследования были сосредоточены на формальном моделировании параллельных систем и пространств Чу .

Карьера

Выросший в Австралии и получивший образование в гимназии Нокса , где он учился в 1961 году, Пратт учился в Сиднейском университете , где в 1970 году защитил магистерскую диссертацию, связанную с тем, что сейчас известно как обработка естественного языка . Затем он отправился в Соединенные Штаты, где защитил докторскую диссертацию. диссертацию в Стэнфордском университете всего за 20 месяцев под руководством консультанта Дональда Кнута . Его диссертация была посвящена анализу алгоритма сортировки Shellsort и сортировочных сетей . ^{[ 1 ]}

Пратт был доцентом Массачусетского технологического института (с 1972 по 1976 год), а затем доцентом (с 1976 по 1982 год). В 1974 году, работая в сотрудничестве с Кнутом и Джеймсом Х. Моррисом , Пратт завершил и формализовал работу, которую он начал в 1970 году, будучи аспирантом Беркли ; соавторским результатом стал алгоритм сопоставления с образцом Кнута-Морриса-Пратта . В 1976 году он разработал систему динамической логики — модальной логики структурированного поведения.

Он ушел из Массачусетского технологического института в Стэнфорд (с 1980 по 1981 год) и был назначен профессором Стэнфорда в 1981 году.

Пратт руководил проектом рабочей станции SUN в Стэнфорде с 1980 по 1982 год. Он внес разнообразный вклад в основание и начало работы Sun Microsystems , выступая в роли консультанта в течение первого года ее существования, затем взяв отпуск в Стэнфорде на следующие два года, став директором по исследованиям и, наконец, возобновив свою роль консультанта Sun и вернувшись в Стэнфорд в 1985 году.

Он также разработал логотип Sun Microsystems . ^{[ 2 ]} который представляет собой четыре чередующихся копии слова «солнце» ; это амбиграмма .

Пратт стал почетным профессором Стэнфорда в 2000 году.

Основные вклады

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

Полезный инструмент для создания

Пратт создал несколько полезных инструментов. В 1976 году он написал рабочий документ MIT AI Lab о CGOL , альтернативном синтаксисе MACLISP , который он разработал и реализовал на основе своей парадигмы анализа приоритета операторов сверху вниз. ^{[ 6 ]} Его парсер иногда называют « парсером Пратта ». ^{[ 7 ]} и использовался в более поздних системах, таких как MACSYMA . Дуглас Крокфорд также использовал его в качестве базового парсера для JSLint . ^{[ 8 ]} Пратт также внедрил текстовый редактор на основе TECO под названием «DOC», который позже был переименован в «ZED». ^{[ 9 ]}

В 1999 году Пратт построил самый маленький (на тот момент) веб-сервер в мире — он был размером со спичечный коробок. ^{[ 10 ]}^{[ 11 ]}

Другие вклады

за 1995 год Пратт получил признание В статье журнала Byte за предположение, что ошибка Pentium FDIV может иметь худшие последствия, чем прогнозировали в то время Intel или IBM. ^{[ 12 ]}^{[ 13 ]}

Сегодня Пратт имеет широкое влияние. Помимо профессорской должности в Стэнфорде, он является членом как минимум семи профессиональных организаций. Он является членом Ассоциации вычислительной техники и входит в редакционную коллегию трех крупных математических журналов. Он также был основателем, председателем и техническим директором TIQIT Computers, Inc. в течение десяти лет до закрытия компании в 2010 году.

Ссылки

^ Воан Рональд Пратт: Сортировка Шелл и сортировочные сети . Garland Publishing, Inc., Нью-Йорк и Лондон, 1979 г., ISBN 0-8240-4406-1
^ «Дизайнеры: Воан Пратт» . Логотипбук . Архивировано из оригинала 9 августа 2020 года . Проверено 7 августа 2021 г.
^ Воан Пратт. У каждого простого есть краткий сертификат. SIAM Journal on Computing , том 4, стр. 214–220. 1975. Цитаты , Полный текст (требуется платный вход)
^ Дональд Кнут, Джеймс Х. Моррис-младший и Воан Пратт. Быстрое сопоставление с образцом в строках. SIAM Journal on Computing , 6(2):323–350. 1977. Цитаты .
^ Блюм, М .; Флойд, RW ; Пратт, Вирджиния ; Ривест, РЛ ; Тарьян, Р.Э. (август 1973 г.). «Сроки выбора» (PDF) . Журнал компьютерных и системных наук . 7 (4): 448–461. дои : 10.1016/S0022-0000(73)80033-9 .
^ Пратт, VR, Приоритет операторов сверху вниз. Материалы симпозиума ACM по принципам языков программирования . 1973. стр. 41-51.
^ Джордж Дж. Карретт Простой анализатор Пратта для SIOD . 1990.
^ https://github.com/douglascrockford/JSLint/blob/40e3f73127b56f24a12e5cb091a86d9a24130926/fulljslint.js строка исходного кода jslint 2224
^ Эрик Фишер. Emacs и другие редакторы . альтернативный фольклор.компьютеры. 15 ноября 2000 г.
^ Новости Би-би-си. Серфинг на спичечном коробке . 1999.
^ Новости CNN. Самый маленький веб-сервер помещается в кармане рубашки . 1999.
^ «Как ушибить целое число». Архивировано 7 октября 2008 г. в Wayback Machine , Байт, март 1995 г.
^ «Цепная реакция в пентиумах» , Воган Пратт, 1994. В wdv-notes334, 22 января 1995 г. Статья отформатирована на основе сообщения в группе новостей: Воан Пратт (30 декабря 1994 г.). " "ТЕХНИЧЕСКОЕ: Цепная реакция в процессорах Pentium (Было: Недостаток: данные, загрязненные Pentium, сохраняются)" " . Группа новостей : comp.sys.intel . Usenet: [электронная почта защищена] . Проверено 3 июня 2006 г.

Внешние ссылки

Воан Пратт в проекте «Математическая генеалогия»
Домашняя страница факультета Стэнфордского университета
Страница с аннотациями , где можно загрузить полнотекстовые версии многих публикаций Пратта.
Дуглас Крокфорд рассказывает о создании парсера Пратта на JavaScript.

[1] Воан Рональд Пратт: Сортировка Шелл и сортировочные сети . Garland Publishing, Inc., Нью-Йорк и Лондон, 1979 г., ISBN 0-8240-4406-1

[SunLogobook-2] «Дизайнеры: Воан Пратт» . Логотипбук . Архивировано из оригинала 9 августа 2020 года . Проверено 7 августа 2021 г.

[3] Воан Пратт. У каждого простого есть краткий сертификат. SIAM Journal on Computing , том 4, стр. 214–220. 1975. Цитаты , Полный текст (требуется платный вход)

[4] Дональд Кнут, Джеймс Х. Моррис-младший и Воан Пратт. Быстрое сопоставление с образцом в строках. SIAM Journal on Computing , 6(2):323–350. 1977. Цитаты .

[5] Блюм, М .; Флойд, RW ; Пратт, Вирджиния ; Ривест, РЛ ; Тарьян, Р.Э. (август 1973 г.). «Сроки выбора» (PDF) . Журнал компьютерных и системных наук . 7 (4): 448–461. дои : 10.1016/S0022-0000(73)80033-9 .

[6] Пратт, VR, Приоритет операторов сверху вниз. Материалы симпозиума ACM по принципам языков программирования . 1973. стр. 41-51.

[7] Джордж Дж. Карретт Простой анализатор Пратта для SIOD . 1990.

[8] ttps://github.com/douglascrockford/JSLint/blob/40e3f73127b56f24a12e5cb091a86d9a24130926/fulljslint.js строка исходного кода jslint 2224

[9] Эрик Фишер. Emacs и другие редакторы . альтернативный фольклор.компьютеры. 15 ноября 2000 г.

[10] Новости Би-би-си. Серфинг на спичечном коробке . 1999.

[11] Новости CNN. Самый маленький веб-сервер помещается в кармане рубашки . 1999.

[12] «Как ушибить целое число». Архивировано 7 октября 2008 г. в Wayback Machine , Байт, март 1995 г.

[13] «Цепная реакция в пентиумах» , Воган Пратт, 1994. В wdv-notes334, 22 января 1995 г. Статья отформатирована на основе сообщения в группе новостей: Воан Пратт (30 декабря 1994 г.). " "ТЕХНИЧЕСКОЕ: Цепная реакция в процессорах Pentium (Было: Недостаток: данные, загрязненные Pentium, сохраняются)" " . Группа новостей : comp.sys.intel . Usenet: [электронная почта защищена] . Проверено 3 июня 2006 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

Базы данных авторитетного контроля
Международный	ЯВЛЯЮТСЯ ВИАФ
Национальный	Израиль Соединенные Штаты Польша
академики	Ассоциация вычислительной техники ДБЛП Google Академика MathSciNet Проект математической генеалогии zbMATH
Другой	ИдРеф