Воган Пратт
Воган Пратт | |
|---|---|
 | |
| Рожденный | Вон Рональд Пратт 12 апреля 1944 г. Мельбурн , Австралия |
| Образование | Стэнфордский университет (1972) Сиднейский университет (1970) |
| Известный | Алгоритм Кнута – Морриса – Пратта Сертификат Пратта Парсер Пратта |
| Научная карьера | |
| Поля | Информатика |
| Учреждения | Стэндфордский Университет С |
| Научные консультанты | Дональд Кнут |
| Докторанты | |
| Веб-сайт | буль |
Воан Пратт (родился 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 г.
- ^ «Цепная реакция в Pentiums» , Воган Пратт, 1994. В wdv-notes334, 22 января 1995. Статья отформатирована на основе сообщения в группе новостей: Воан Пратт (30 декабря 1994 г.). " "ТЕХНИЧЕСКОЕ: Цепная реакция в процессорах Pentium (Было: Недостаток: данные, загрязненные Pentium, сохраняются)" " . Группа новостей : comp.sys.intel . Usenet: [email protected] . Проверено 3 июня 2006 г.
Внешние ссылки [ править ]
- Воан Пратт в проекте «Математическая генеалогия»
- Домашняя страница факультета Стэнфордского университета
- Страница с аннотациями , где можно загрузить полнотекстовые версии многих публикаций Пратта.
- Дуглас Крокфорд рассказывает о создании парсера Пратта на JavaScript.
| Международный | |
|---|---|
| Национальный | |
| академики | |
| Другой | |
- 1944 года рождения
- Живые люди
- Австралийские ученые-компьютерщики
- 1997 г. Члены Ассоциации вычислительной техники.
- Выпускники Сиднейского университета
- Выпускники Стэнфордского университета
- Факультет инженерной школы Стэнфордского университета
- Факультет Массачусетского технологического института
- Теоретики-компьютерщики
- Люди, получившие образование в гимназии Нокса