Vaughan Ronald 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 ExpressionsSzablon:R. 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 ShellsortSzablon:R. Wersja algorytmu zaproponowana przez Pratta ma rząd złożoności pesymistycznej Szablon:R. 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 angielskiSzablon:R. 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 selekcjiSzablon:R.
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 1977Szablon:R.
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 ambigramuSzablon:R.
Do jego doktorantów należał m.in. David HarelSzablon:R.
Od 2000 jest emerytowanym profesorem Uniwersytetu Stanforda.