Pratt, Vaughn Ronald

Vaughn Ronald Pratt
engelsk  Vaughan Ronald Pratt
Fødselsdato 12. april 1944( 1944-04-12 ) (78 år)
Fødselssted
Land
Videnskabelig sfære datalogi [1]
Arbejdsplads
Alma Mater
videnskabelig rådgiver Donald Ervin Knuth [2]
Kendt som En af forfatterne til Knuth-Morris-Pratt-algoritmen , forfatteren af ​​Pratt Simplicity Certificate og Pratt Parser
Priser og præmier Hej ACM
Internet side profiles.stanford.edu/… ​(  engelsk)
 Mediefiler på Wikimedia Commons

Vaughan Ronald Pratt ( født 12. april  1944, Melbourne , Australien ) er emeritusprofessor ved Stanford University , en af ​​pionererne inden for teoretisk datalogi . Siden 1969 har Pratt ydet betydelige bidrag til grundlæggende områder som søgealgoritmer , sortering og . Hans nyere forskning fokuserer på den formelle modellering af konkurrerende systemer og Chu-rum Pratts arbejde er kendetegnet ved anvendelsen til datalogi af modeller fra forskellige områder af matematik - geometri , lineær og generel algebra, matematisk logik .

Karriere

I 1970 afsluttede Pratt sin kandidatafhandling ved University of Sydney i det, der nu er kendt som Natural Language Processing . Herefter flyttede han til USA , hvor han 20 måneder senere forsvarede sin doktorafhandling under vejledning af Donald Knuth . Emnet for hans arbejde var analyse af Shellsort og sorteringsnetværk .

Pratt tjente som assisterende professor ved MIT fra 1972 til 1976 og derefter som ekstraordinær professor fra 1976 til 1982. I 1974, sammen med Knuth og Morris , fuldførte og formaliserede Pratt det arbejde, han havde påbegyndt i 1970. under min studietid på Berkeley . Som et resultat af dette medforfatterskab dukkede Knuth-Morris-Pratt-algoritmen op . I 1976 udviklede Pratt et system af dynamisk logik  , en modal logik for struktureret adfærd.

I 1980-1981 tog Pratt orlov fra forskning ved MIT og flyttede til Stanford University , hvor han modtog et professorat i 1981.

I 2000 blev Pratt emeritus professor ved Stanford.

Nøglepræstationer

Flere velkendte algoritmer er opkaldt efter Pratt. Primalitetscertifikatet foreslået af Pratt viste, at tallenes primalitet kan verificeres i polynomisk tid. Af denne kendsgerning fulgte det, at problemet med at kontrollere tal for enkelhed ligger i klassen NP , og derfor formodentlig ikke er co-NP komplet [3] . Efterfølgende blev en polynomial algoritme til kontrol af et tal for enkelhed udviklet. Knuth-Morris-Pratt-algoritmen , som Pratt udviklede i begyndelsen af ​​70'erne sammen med Stanford-kollegaen Donald Knuth uafhængigt af Morris , er den mest effektive generelle søgealgoritme for understrenge , der kendes i dag [4] . Sammen med Bloom , Floyd , Rivest og Tarjan beskrev Pratt medianen af ​​medianer ( BFRPT-algoritmen ved forfatternes initialer) - den første optimale algoritme til at vælge en rækkefølgestatistik [5] .

Noter

  1. ↑ 1 2 https://profiles.stanford.edu/vaughan-pratt
  2. ↑ Matematisk genealogi  (engelsk) - 1997.
  3. ↑ Vaughan Pratt. Hver prime har et kortfattet certifikat. SIAM Journal on Computing , bind 4, s.214-220. 1975. Citations Arkiveret 6. juni 2008 på Wayback Machine , Fuldtekst Arkiveret 26. september 2007 på Wayback Machine (kræver betalt login)
  4. ↑ Donald Knuth, James H. Morris, Jr., og Vaughan Pratt. Hurtig mønstermatch i strenge. SIAM Journal on Computing , 6(2):323-350. 1977. Citations Arkiveret 4. januar 2010 på Wayback Machine
  5. ↑ Blum, M .; Floyd, RW ; Pratt, VR ; Rivest, R.L .; Tarjan, RE Tidsgrænser for udvælgelse  //  Journal of Computer and System Sciences : journal. - 1973. - August ( bind 7 , nr. 4 ). - S. 448-461 . - doi : 10.1016/S0022-0000(73)80033-9 .

Links

  Gå til Wikidata-elementet  Tematiske steder