Pratt, Vaughn Ronald

Vaughn Ronald Pratt
Angličtina  Vaughan Ronald Pratt
Datum narození 12. dubna 1944( 1944-04-12 ) (ve věku 78 let)
Místo narození
Země
Vědecká sféra informatika [1]
Místo výkonu práce
Alma mater
vědecký poradce Donald Ervin Knuth [2]
Známý jako Jeden z autorů Knuth-Morris-Prattova algoritmu , autor Pratt Simplicity Certificate a Pratt Parser
Ocenění a ceny Ahoj ACM
webová stránka profiles.stanford.edu/… ​(  anglicky)
 Mediální soubory na Wikimedia Commons

Vaughan Ronald Pratt ( narozen 12. dubna 1944,  Melbourne , Austrálie ) je emeritním profesorem na Stanfordské univerzitě , jedním z průkopníků teoretické informatiky . Od roku 1969 Pratt významně přispěl k základním oblastem, jako jsou vyhledávací algoritmy , třídění a testování . Jeho novější výzkum se zaměřuje na formální modelování konkurenčních systémů a prostorů Chu Prattova práce se vyznačuje aplikací na informatiku modelů z různých oblastí matematiky - geometrie , lineární a obecné algebry, matematické logiky .

Kariéra

V roce 1970 dokončil Pratt svou magisterskou práci na University of Sydney v tom, co je nyní známé jako zpracování přirozeného jazyka . Poté se přestěhoval do USA , kde o 20 měsíců později pod vedením Donalda Knutha obhájil doktorskou disertační práci . Tématem jeho práce byla analýza Shellsortu a třídicích sítí .

Pratt působil jako odborný asistent na MIT od roku 1972 do roku 1976 a poté jako mimořádný profesor od roku 1976 do roku 1982. V roce 1974 s Knuthem a Morrisem Pratt dokončil a formalizoval práci, kterou začal v roce 1970. během mých studentských let v Berkeley . V důsledku tohoto spoluautorství se objevil Knuth-Morris-Pratt Algorithm . V roce 1976 Pratt vyvinul systém dynamické logiky  , modální logiku strukturovaného chování.

V letech 1980-1981 si Pratt vzal dovolenou z výzkumu na MIT a přestěhoval se na Stanford University , kde v roce 1981 získal profesuru.

V roce 2000 se Pratt stal emeritním profesorem na Stanfordu.

Klíčové úspěchy

Po Prattovi je pojmenováno několik známých algoritmů. Certifikát primality navržený Prattem ukázal, že primálnost čísel lze ověřit v polynomiálním čase. Z tohoto faktu vyplynulo, že problém kontroly jednoduchosti čísel spočívá ve třídě NP , a proto pravděpodobně není co-NP kompletní [3] . Následně byl vyvinut polynomiální algoritmus pro kontrolu čísla pro jednoduchost. Algoritmus Knuth-Morris-Pratt , který Pratt vyvinul na počátku 70. let se Stanfordským kolegou Donaldem Knuthem nezávisle na Morrisovi , je nejúčinnějším obecným vyhledávacím algoritmem podřetězců, který je dnes znám [4] . Spolu s Bloomem , Floydem , Rivestem a Tarjanem Pratt popsal medián mediánů ( algoritmus BFRPT iniciálami autorů) – první optimální algoritmus pro výběr statistiky pořadí [5] .

Poznámky

  1. ↑ 1 2 https://profiles.stanford.edu/vaughan-pratt
  2. ↑ Matematická genealogie  (anglicky) - 1997.
  3. ↑ Vaughan Pratt. Každý prvočíslo má stručný certifikát. SIAM Journal on Computing , sv. 4, s. 214-220. 1975. Citace archivovány 6. června 2008 na Wayback Machine , Fulltext Archivovány 26. září 2007 na Wayback Machine (vyžaduje placené přihlášení)
  4. ↑ Donald Knuth, James H. Morris, Jr., a Vaughan Pratt. Rychlé přizpůsobení vzorů v řetězcích. SIAM Journal on Computing , 6(2):323-350. 1977. Citace archivovány 4. ledna 2010 na Wayback Machine
  5. ↑ Blum, M .; Floyd, RW ; Pratt, VR ; Rivest, R. L .; Tarjan, RE Časové hranice pro výběr  //  Journal of Computer and System Sciences : deník. - 1973. - Srpen ( ročník 7 , č. 4 ). - S. 448-461 . - doi : 10.1016/S0022-0000(73)80033-9 .

Odkazy

  Přejděte na položku Wikidata  Tematické stránky