Pratt, Vaughn Ronald

Vaughn Ronald Pratt
Englanti  Vaughan Ronald Pratt
Syntymäaika 12. huhtikuuta 1944( 12.4.1944 ) (78-vuotiaana)
Syntymäpaikka
Maa
Tieteellinen ala tietojenkäsittelytiede [1]
Työpaikka
Alma mater
tieteellinen neuvonantaja Donald Ervin Knuth [2]
Tunnetaan Yksi Knuth-Morris-Pratt-algoritmin tekijöistä , Pratt Simplicity Certificate -sertifikaatin ja Pratt Parserin kirjoittaja
Palkinnot ja palkinnot Hyvä ACM
Verkkosivusto profiles.stanford.edu/… ​(  englanti)
 Mediatiedostot Wikimedia Commonsissa

Vaughan Ronald Pratt ( s . 12. huhtikuuta  1944, Melbourne , Australia ) on Stanfordin yliopiston emeritusprofessori , yksi teoreettisen tietojenkäsittelytieteen pioneereista . Vuodesta 1969 lähtien Pratt on osallistunut merkittävästi perusaloihin , kuten hakualgoritmeihin , lajitteluun ja . Hänen uudempi tutkimuksensa keskittyy kilpailevien järjestelmien ja Chu-tilojen muodolliseen mallintamiseen Prattin työ erottuu matematiikan eri alojen mallien soveltamisesta tietojenkäsittelytieteeseen - geometria , lineaarinen ja yleinen algebra, matemaattinen logiikka .

Ura

Vuonna 1970 Pratt suoritti pro gradu -tutkielmansa Sydneyn yliopistossa aiheesta , joka tunnetaan nykyään nimellä Natural Language Processing . Sen jälkeen hän muutti Yhdysvaltoihin , missä hän puolusti väitöskirjaansa 20 kuukautta myöhemmin Donald Knuthin johdolla . Hänen työnsä aiheena oli Shellsortin ja lajitteluverkostojen analyysi .

Pratt toimi apulaisprofessorina MIT :ssä 1972–1976 ja sitten ylimääräisenä professorina vuosina 1976–1982. Vuonna 1974 Pratt sai Knuthin ja Morrisin kanssa päätökseen ja virallisti työnsä, jonka hän oli aloittanut vuonna 1970. Opiskeluaikoinani Berkeleyssä . Tämän yhteistyön seurauksena Knuth-Morris-Pratt-algoritmi ilmestyi . Vuonna 1976 Pratt kehitti dynaamisen logiikan järjestelmän  , strukturoidun käyttäytymisen modaalisen logiikan .

Vuosina 1980-1981 Pratt piti virkavapautta MIT:n tutkimuksesta ja muutti Stanfordin yliopistoon , jossa hän sai professorin viran vuonna 1981.

Vuonna 2000 Prattista tuli emeritusprofessori Stanfordissa.

Tärkeimmät saavutukset

Useita tunnettuja algoritmeja on nimetty Prattin mukaan. Prattin ehdottama ensisijaisuussertifikaatti osoitti, että lukujen ensisijaisuus voidaan todentaa polynomiajassa. Tästä tosiasiasta seurasi, että numeroiden yksinkertaisuuden tarkistamisen ongelma piilee luokassa NP , ja siksi oletettavasti se ei ole co-NP täydellinen [3] . Myöhemmin kehitettiin polynomialgoritmi luvun tarkistamiseksi yksinkertaisuuden vuoksi. Knuth-Morris-Pratt-algoritmi , jonka Pratt kehitti 70-luvun alussa Stanfordin kollegansa Donald Knuthin kanssa Morrisista riippumatta , on tehokkain nykyään tunnettu yleinen osamerkkijonohakualgoritmi [4] . Yhdessä Bloomin , Floydin , Rivestin ja Tarjanin kanssa Pratt kuvasi mediaanien mediaanin ( BFRPT-algoritmi tekijöiden alkukirjaimilla) - ensimmäisen optimaalisen algoritmin tilaustilaston valinnassa [5] .

Muistiinpanot

  1. ↑ 1 2 https://profiles.stanford.edu/vaughan-pratt
  2. ↑ Matemaattinen sukututkimus  (englanniksi) - 1997.
  3. ↑ Vaughan Pratt. Jokaisella primellä on ytimekäs todistus. SIAM Journal on Computing , vol. 4, s. 214-220. 1975. Sitaatit arkistoitu 6. kesäkuuta 2008 Wayback Machinessa , koko teksti arkistoitu 26. syyskuuta 2007 Wayback Machinessa (vaatii maksullisen kirjautumisen)
  4. ↑ Donald Knuth, James H. Morris, Jr. ja Vaughan Pratt. Nopea kuvion sovitus nauhoissa. SIAM Journal on Computing , 6(2):323-350. 1977. Sitaatit arkistoitu 4. tammikuuta 2010 Wayback Machinessa
  5. ↑ Blum, M .; Floyd, RW ; Pratt, VR ; Rivest, R.L .; Tarjan, RE Valinnan aikarajat  //  Journal of Computer and System Sciences : päiväkirja. - 1973. - elokuu ( osa 7 , nro 4 ). - s. 448-461 . - doi : 10.1016/S0022-0000(73)80033-9 .

Linkit

  Siirry Wikidata-kohteeseen  Temaattiset sivustot