Vaughan Ronald Pratt

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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[3][2]. Wersja algorytmu zaproponowana przez Pratta ma rząd złożoności pesymistycznej \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 [5][6][3]. 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), 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[edytuj | edytuj kod]

  1. Strona domowa profesora Pratta na serwerze Uniwersytetu Stanforda (ang.).
  2. 2,0 2,1 Curriculum Vitae (ang.). [dostęp 2015-02-20].
  3. 3,0 3,1 3,2 3,3 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 (ang.). [dostęp 2015-02-20]. 
  9. Mathematics Genealogy Project – Vaughan Ronald Pratt (ang.).

Linki zewnętrzne[edytuj | edytuj kod]