Pratt, Vaughn Ronald

Vaughn Ronald Pratt
angol  Vaughan Ronald Pratt
Születési dátum 1944. április 12.( 1944-04-12 ) (78 évesen)
Születési hely
Ország
Tudományos szféra számítástechnika [1]
Munkavégzés helye
alma Mater
tudományos tanácsadója Donald Ervin Knuth [2]
Ismert, mint A Knuth-Morris-Pratt algoritmus egyik szerzője , a Pratt Simplicity Certificate és a Pratt Parser szerzője
Díjak és díjak Kedves ACM
Weboldal profiles.stanford.edu/… ​(  angol)
 Médiafájlok a Wikimedia Commons oldalon

Vaughan Ronald Pratt ( született : 1944. április  12., Melbourne , Ausztrália ) a Stanford Egyetem emeritus professzora , az elméleti számítástechnika egyik úttörője . 1969 óta a Pratt jelentős mértékben hozzájárult az olyan alapvető területekhez, mint a keresési algoritmusok , a rendezés és az tesztelése . Újabb kutatásai a kompetitív rendszerek és Chu terek formális modellezésére összpontosítanak Pratt munkáját a matematika különböző területeiről származó modellek – geometria , lineáris és általános algebra, matematikai logika – számítástechnikában való alkalmazása különbözteti meg .

Karrier

1970-ben Pratt a Sydney-i Egyetemen fejezte be diplomamunkáját az úgynevezett természetes nyelvi feldolgozás témakörben . Ezt követően az USA -ba költözött , ahol 20 hónappal később védte meg doktori disszertációját Donald Knuth irányítása alatt . Munkájának témája a Shellsort és a rendezési hálózatok elemzése volt .

Pratt 1972 és 1976 között adjunktus professzorként, majd 1976 és 1982 között rendkívüli professzorként szolgált. 1974-ben Knuth és Morris társaságában Pratt befejezte és formalizálta az 1970-ben megkezdett munkát . A társszerzőség eredményeként megjelent a Knuth-Morris-Pratt algoritmus . 1976-ban Pratt kifejlesztette a dinamikus logika rendszerét  , a strukturált viselkedés modális logikáját .

1980 és 1981 között Pratt szabadságot vett ki az MIT-n végzett kutatásból, és a Stanford Egyetemre költözött , ahol 1981-ben professzori címet kapott.

2000-ben Pratt emeritus professzor lett a Stanfordon.

Key Achievements

Pratt nevéhez fűződik számos jól ismert algoritmus. A Pratt által javasolt primalitástanúsítvány megmutatta, hogy a számok elsődlegessége polinomiális időben ellenőrizhető. Ebből a tényből az következett, hogy a számok egyszerűség céljából történő ellenőrzésének problémája az NP osztályban rejlik , ezért feltehetően nem co-NP teljes [3] . Ezt követően egy polinomiális algoritmust fejlesztettek ki egy szám ellenőrzésére az egyszerűség kedvéért. A Knuth-Morris-Pratt algoritmus , amelyet Pratt a 70-es évek elején dolgozott ki stanfordi kollégájával, Donald Knuth -al Morristól függetlenül , a ma ismert leghatékonyabb általános részkarakterlánc-kereső algoritmus [4] . Pratt Bloommal, Floyddal, Rivesttel és Tarjannal együtt leírta a mediánok mediánját ( a BFRPT algoritmust a szerzők kezdőbetűivel ) – ez az első optimális algoritmus a sorrendi statisztika kiválasztásához [5] .

Jegyzetek

  1. ↑ 1 2 https://profiles.stanford.edu/vaughan-pratt
  2. ↑ Matematikai genealógia  (angol) - 1997.
  3. ↑ Vaughan Pratt. Minden prímnak van egy tömör bizonyítványa. SIAM Journal on Computing , 4. kötet, 214-220. 1975. A Wayback Machine -nél 2008. június 6-án archivált idézetek , teljes szöveges archiválás : 2007. szeptember 26., a Wayback Machine -nél (fizetett bejelentkezés szükséges)
  4. ↑ Donald Knuth, James H. Morris, Jr. és Vaughan Pratt. Gyors mintaillesztés húrokban. SIAM Journal on Computing , 6(2):323-350. 1977. Idézetek archiválva 2010. január 4-én a Wayback Machine -nél
  5. ↑ Blum, M .; Floyd, RW ; Pratt, VR ; Rivest, R. L .; Tarjan, RE A kiválasztás időhatárai  //  Journal of Computer and System Sciences : folyóirat. - 1973. - augusztus ( 7. köt . 4. sz .). - P. 448-461 . - doi : 10.1016/S0022-0000(73)80033-9 .

Linkek

  Ugrás a Wikidata elemre  Tematikus oldalak