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.

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ó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 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 (ang.). [dostęp 2015-02-20].
  2. a b Curriculum Vitae (ang.). [dostęp 2015-02-20].
  3. a b c d Science Hall of Fame – Professor Vaughan Pratt (ang.). [dostęp 2015-02-20].
  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 (ang.). [dostęp 2015-02-20].
  6. LINGOL – A Progress Report (ang.). [dostęp 2015-02-20].
  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 (ang.). [dostęp 2015-02-20]. 
  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 (ang.). [dostęp 2015-02-20]. 
  9. Mathematics Genealogy Project – Vaughan Ronald Pratt (ang.). [dostęp 2015-02-20].

Linki zewnętrzne

Media użyte na tej stronie

VaughanPratt.JPG
Autor: Vaughan Pratt, Licencja: CC BY-SA 3.0
Photograph of Vaughan Pratt for uploading to Wikimedia Commons, per request of User:EdJohnston