Воан Пратт (родился 12 апреля 1944 года) — почетный профессор Стэнфордского университета , один из первых пионеров в области компьютерных наук . С 1969 года Пратт внес ряд вкладов в такие фундаментальные области, как алгоритмы поиска , алгоритмы сортировки и проверка простоты . В последнее время его исследования были сосредоточены на формальном моделировании параллельных систем и пространств Чу .
Выросший в Австралии и получивший образование в Knox Grammar School , где он стал dux в 1961 году, Пратт учился в Сиднейском университете , где в 1970 году защитил магистерскую диссертацию, посвященную тому, что сейчас известно как обработка естественного языка . Затем он отправился в Соединенные Штаты, где всего за 20 месяцев защитил докторскую диссертацию в Стэнфордском университете под руководством консультанта Дональда Кнута . Его диссертация была посвящена анализу алгоритма сортировки Шеллсорт и сетей сортировки . [1]
Пратт был доцентом Массачусетского технологического института (с 1972 по 1976 год), а затем доцентом (с 1976 по 1982 год). В 1974 году, работая в сотрудничестве с Кнутом и Джеймсом Х. Моррисом , Пратт завершил и формализовал работу, которую он начал в 1970 году, будучи аспирантом в Беркли ; результатом совместной работы стал алгоритм сопоставления шаблонов Кнута–Морриса–Пратта . В 1976 году он разработал систему динамической логики , модальную логику структурированного поведения.
Он отправился в академический отпуск из Массачусетского технологического института в Стэнфорд (1980–1981 гг.) и в 1981 г. был назначен штатным профессором Стэнфорда.
Пратт руководил проектом рабочей станции SUN в Стэнфорде с 1980 по 1982 год. Он внес разный вклад в создание и раннюю деятельность Sun Microsystems , выступая в роли консультанта в течение первого года, затем, взяв отпуск в Стэнфорде на следующие два года, стал директором по исследованиям и, наконец, возобновив свою роль консультанта Sun и вернувшись в Стэнфорд в 1985 году.
Он также разработал логотип Sun Microsystems [2] , который представляет собой четыре чередующихся копии слова «sun» ; это амбиграмма .
В 2000 году Пратт стал почетным профессором Стэнфорда.
Ряд известных алгоритмов носят имя Пратта. Сертификаты Пратта , краткие доказательства простоты числа, продемонстрировали на практике, что простота может быть эффективно проверена, поместив задачу проверки простоты в класс сложности NP и предоставив первое весомое доказательство того, что задача не является ко-NP-полной . [3] Алгоритм Кнута–Морриса–Пратта , который Пратт разработал в начале 1970-х годов вместе с коллегой-профессором Стэнфорда Дональдом Кнутом и независимо от Морриса , до сих пор является самым эффективным общим алгоритмом поиска строк, известным сегодня. [4] Вместе с Блюмом , Флойдом , Ривестом и Тарьяном он описал медиану медиан , первый оптимальный алгоритм выбора для наихудшего случая . [5]
Pratt создал несколько полезных инструментов. В 1976 году он написал рабочий документ MIT AI Lab о CGOL , альтернативном синтаксисе для MACLISP , который он разработал и реализовал на основе своей парадигмы для нисходящего анализа приоритета операторов. [6] Его синтаксический анализатор иногда называют « Pratt parser » [7], и он использовался в более поздних системах, таких как MACSYMA . Дуглас Крокфорд также использовал его в качестве базового синтаксического анализатора для JSLint . [8] Pratt также реализовал текстовый редактор на основе TECO под названием «DOC», который позже был переименован в «ZED». [9]
В 1999 году Пратт построил самый маленький в мире (на тот момент) веб-сервер — он был размером со спичечный коробок. [10] [11]
В статье журнала Byte за 1995 год Пратту приписывают предположение, что ошибка Pentium FDIV может иметь худшие последствия, чем предсказывали Intel или IBM в то время. [12] [13]
Сегодня Пратт имеет широкое влияние. Помимо своей профессорской должности в Стэнфорде, он является членом по крайней мере семи профессиональных организаций. Он является членом Ассоциации вычислительной техники и входит в редакционную коллегию трех крупных математических журналов. Он также был основателем, председателем и техническим директором TIQIT Computers, Inc. в течение десяти лет до ее закрытия в 2010 году.
