Pratt, Vaughn Ronald

Vaughn Ronald Pratt
engelsk  Vaughan Ronald Pratt
Födelsedatum 12 april 1944( 1944-04-12 ) (78 år)
Födelseort
Land
Vetenskaplig sfär datavetenskap [1]
Arbetsplats
Alma mater
vetenskaplig rådgivare Donald Ervin Knuth [2]
Känd som En av författarna till Knuth-Morris-Pratt-algoritmen , författaren till Pratt Simplicity Certificate och Pratt Parser
Utmärkelser och priser Hej ACM
Hemsida profiles.stanford.edu/… ​(  engelska)
 Mediafiler på Wikimedia Commons

Vaughan Ronald Pratt ( född 12  april 1944, Melbourne , Australien ) är en emeritusprofessor vid Stanford University , en av pionjärerna inom teoretisk datavetenskap . Sedan 1969 har Pratt gjort betydande bidrag till grundläggande områden som sökalgoritmer , sortering och . Hans nyare forskning fokuserar på formell modellering av konkurrenskraftiga system och Chu-utrymmen Pratts arbete kännetecknas av tillämpningen till datavetenskap av modeller från olika områden av matematik - geometri , linjär och allmän algebra, matematisk logik .

Karriär

1970 avslutade Pratt sin masteruppsats vid University of Sydney i vad som nu är känt som Natural Language Processing . Därefter flyttade han till USA , där han disputerade 20 månader senare under handledning av Donald Knuth . Ämnet för hans arbete var analysen av Shellsort och sorteringsnätverk .

Pratt tjänstgjorde som assisterande professor vid MIT från 1972 till 1976 och sedan som extraordinarie professor från 1976 till 1982. 1974, tillsammans med Knuth och Morris , avslutade och formaliserade Pratt det arbete han hade påbörjat 1970. under min studenttid i Berkeley . Som ett resultat av detta medförfattarskap dök Knuth-Morris-Pratt-algoritmen upp . 1976 utvecklade Pratt ett system av dynamisk logik  , en modal logik för strukturerat beteende.

1980-1981 tog Pratt tjänstledigt från forskning vid MIT och flyttade till Stanford University , där han fick en professur 1981.

År 2000 blev Pratt emeritusprofessor vid Stanford.

Nyckelprestationer

Flera välkända algoritmer är uppkallade efter Pratt. Primalitetscertifikatet som Pratt föreslagit visade att tals primalitet kan verifieras i polynomtid. Av detta faktum följde att problemet med att kontrollera siffror för enkelhet ligger i klassen NP , och därför, förmodligen, inte är co-NP komplett [3] . Därefter utvecklades en polynomalgoritm för att kontrollera ett tal för enkelhet. Knuth-Morris-Pratt-algoritmen , som Pratt utvecklade i början av 70-talet tillsammans med Stanford-kollegan Donald Knuth oberoende av Morris , är den mest effektiva allmänna sökalgoritmen för delsträngar som är känd idag [4] . Tillsammans med Bloom , Floyd , Rivest och Tarjan beskrev Pratt medianen för medianerna ( BFRPT-algoritmen av författarnas initialer) - den första optimala algoritmen för att välja en ordningsstatistik [5] .

Anteckningar

  1. ↑ 1 2 https://profiles.stanford.edu/vaughan-pratt
  2. ↑ Mathematical Genealogy  (engelska) - 1997.
  3. ↑ Vaughan Pratt. Varje prime har ett kortfattat intyg. SIAM Journal on Computing , vol. 4, s. 214-220. 1975. Citations Arkiverad 6 juni 2008 på Wayback Machine , Fulltext Arkiverad 26 september 2007 på Wayback Machine (kräver betald inloggning)
  4. ↑ Donald Knuth, James H. Morris, Jr. och Vaughan Pratt. Snabb mönstermatchning i strängar. SIAM Journal on Computing , 6(2):323-350. 1977. Citationer Arkiverade 4 januari 2010 på Wayback Machine
  5. ↑ Blum, M .; Floyd, RW ; Pratt, VR ; Rivest, R.L .; Tarjan, RE Tidsgräns för urval  //  Journal of Computer and System Sciences : journal. - 1973. - Augusti ( vol. 7 , nr 4 ). - s. 448-461 . - doi : 10.1016/S0022-0000(73)80033-9 .

Länkar

  Gå till Wikidata-objektet  Tematiska platser