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 [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órego 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 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