Vaughan Ronald Pratt

Vaughan Pratt

Vaughan Ronald Pratt (ur. 1944) – emerytowany profesor Uniwersytetu Stanforda, jeden z pionierów informatyki. Obecnie związany z firmą Tiqit.

Życiorys

Dorastał i kształcił się w Australii. W maju 1970 uzystał tytuł magistra informatyki na Uniwersytecie w Sydney pod nadzorem Jana B. Hexta pracą Translation of English into Logical Expressions[1][2][3]. Studia doktoranckie rozpoczął w październiku 1970 na Uniwersytecie Stanforda i w styczniu 1972 pod nazdzorem Donalda Knutha uzyskał tytuł doktora pracą Shellsort and Sorting Networks związaną z algorytmem Shellsort[2][3]. Wersja algorytmu zaproponowana przez Pratta ma rząd złożoności pesymistycznej Θ ( N log 2 ⁡ N ) {\displaystyle \Theta (N\log ^{2}N)} [4]. Od 1972 do 1976 był najpierw adiunktem (assistant professor), a potem do 1982 profesorem nadzwyczajnym (associate professor) w MIT. Następnie został profesorem zwyczajnym (full professor) Uniwersytetu Stanforda.

W 1973 opracował LINGOL, język do programowania języka naturalnego, który użyto do utworzenia programu tłumaczącego z japońskiego na angielski[3][5][6]. W tym samym roku wspólnie z Blumem, Floydem, Rivestem i Tarjanem opisał algorytm znajdowania mediany median, pierwszy optymalny w czasie pesymistycznym, tj. rzędu O ( n ) , {\displaystyle O(n),} algorytm rozwiązujący problem selekcji[7].

W 1974 roku razem z Donaldem Knuthem i Jamesem Morrisem opracował algorytm wyszukiwania wzorca w tekście. Wspólna praca opisująca algorytm została opublikowana w 1977[8].

W 1975 zdefiniował certyfikat pierwszości nazwany certyfikatem Pratta, który pozwala szybko zweryfikować, czy dana liczba jest pierwsza. Dowiódł, że problem znajdowania liczb pierwszych leży w klasie NP, czyli problemów których rozwiązania można sprawdzić w czasie wielomianowym.

W 1982 w czasie urlopu pomógł założyć firmę Sun i zaprojektował jej logo składające się z czterech przeplatających się słów sun (słońce) w formie ambigramu[3].

Do jego doktorantów należał m.in. David Harel[9].

Od 2000 jest emerytowanym profesorem Uniwersytetu Stanforda.

Przypisy

  1. ↑ Strona domowa profesora Pratta na serwerze Uniwersytetu Stanforda. [dostęp 2015-02-20]. (ang.).
  2. ↑ a b Curriculum Vitae. [dostęp 2015-02-20]. (ang.).
  3. ↑ a b c d Science Hall of Fame – Professor Vaughan Pratt. [dostęp 2015-02-20]. (ang.).
  4. ↑ Vaughan Ronald Pratt: Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences). Garland, 1979. ISBN 0-824-04406-1. (ang.).
  5. ↑ A Linguistics Oriented Programming Language. [dostęp 2015-02-20]. (ang.).
  6. ↑ LINGOL – A Progress Report. [dostęp 2015-02-20]. (ang.).
  7. ↑ Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ron L. Rivest i inni. Time bounds for selection. „Journal of Computer and System Sciences”. 7 (4), s. 448–461, 1973. DOI: 10.1016/S0022-0000(73)80033-9. [dostęp 2015-02-20]. (ang.). 
  8. ↑ Donald E. Knuth, James H. Morris, Vaughan R. Pratt. Fast pattern matching in strings. „SIAM Journal on Computing”. 6 (2), s. 323–350, 1977. DOI: 10.1137/0206024. MR451916. [dostęp 2015-02-20]. (ang.). 
  9. ↑ Mathematics Genealogy Project – Vaughan Ronald Pratt. [dostęp 2015-02-20]. (ang.).

Linki zewnętrzne

  • Strona domowa profesora Pratta na serwerze Uniwersytetu Stanforda. [dostęp 2015-02-20]. (ang.).
  • Lista publikacji Pratta. [dostęp 2015-02-20]. (ang.).
  • Streszczenia i pełne wersje większości prac Pratta. [dostęp 2015-02-20]. (ang.).
  • ISNI: 0000000439554801
  • VIAF: 165199731
  • LCCN: n79076109
  • SUDOC: 155022954
  • PLWABN: 9810694828705606
  • NUKAT: n98003195
  • J9U: 987007424449805171
  • WorldCat: viaf-165199731