沃恩·普拉特

沃恩·普拉特
Vaughan Pratt
出生Vaughan Ronald Pratt
(1944-04-12) 1944年4月12日（80歲）
 澳大利亞墨爾本
母校雪梨大學
史丹佛大學
知名于KMP演算法
普拉特證明（英语：Primality certificate）
普拉特解析器（英语：Operator-precedence parser）
网站boole.stanford.edu/pratt.html
科学生涯
研究领域計算機科學
机构史丹佛大學
麻省理工學院
学术指导者高德納

沃恩·普拉特（英語：Vaughan Pratt，1944年4月12日—）是一名澳大利亞計算機科學家，史丹佛大學名譽教授。自1969年以來，普拉特在搜尋演算法、排序演算法和質數測試等基礎領域做出多項貢獻。近期他的研究重點是並行系統和楚空間（英语：Chu space）的形式建模。

職業生涯

普拉特在澳大利亞長大，曾就讀於諾克斯文法學校（英语：Knox Grammar School）。1970年，普拉特進入雪梨大學學習，並在那裡完成碩士論文，該論文與現在的自然語言處理有關。隨後他前往美國，在指導教授高德納的指導下，僅用20個月就完成史丹佛大學的博士論文。他的論文重點分析希爾排序演算法和排序網路（英语：Sorting network）[1]。

普拉特曾任麻省理工學院助理教授（1972年—1976年）和副教授（1976年—1982年）。1974年，普拉特與高德納和詹姆斯·H·莫里斯合作，完成他1970年在加利福尼亞大學柏克萊分校攻讀研究生時開始的工作，並使之正規化；合作成果是KMP演算法。1976年，他發展了動態邏輯（英语：Dynamic logic (modal logic)）系統，這是一種結構化行為的模態邏輯。

他從麻省理工學院到史丹佛大學休假（1980年—1981年），並於1981年被任命為史丹佛大學全職教授。

1980年至1982年，普拉特在史丹佛大學指導太陽工作站（英语：SUN workstation）計畫。他以各種方式為昇陽電腦公司的成立和早期運營做出貢獻，在公司成立的第一年擔任顧問，隨後兩年離開史丹佛大學，擔任研究主管，最後於1985年重新擔任昇陽電腦公司顧問並返回史丹佛大學。

他還設計了昇陽電腦公司的徽標[2]，徽標上有四個交錯的「sun」字樣；這是一個雙向圖。

2000年，普拉特成為史丹佛大學榮譽教授。

主要貢獻

許多著名的演算法都以普拉特的名字命名。普拉特證明（英语：Primality certificate）是對一個數是否為質數的簡短證明，它以一種實用的方式證明質數是可以有效驗證的，將質數檢定問題歸入複雜度類NP，並首次有力地證明該問題並非共NP-完備（英语：co-NP-complete）[3]。1970年代初，普拉特與史丹佛大學教授高德納共同設計了KMP演算法，該演算法是詹姆斯·H·莫里斯獨立設計的，至今仍是已知最高效的通用字串搜尋演算法。[4]。他與曼紐爾·布盧姆、羅伯特·弗洛伊德、羅納德·李維斯特和羅伯特·塔揚一起描述中位數的中位數（英语：Median of medians），這是第一個最壞情況下的最佳選擇演算法[5]。

打造實用工具

普拉特開發了一些有用的工具。1976年，他撰寫一篇關於CGOL（英语：CGOL）的麻省理工學院人工智慧實驗室工作論文，CGOL是他根據自上而下的運算子優先級解析範式設計並實現的MACLISP的替代語法。[6]。他的解析器有時被稱為「普拉特解析器（英语：Operator-precedence parser）」[7]，並被用於後來的系統中，如MACSYMA（英语：Macsyma）。道格拉斯·克羅克福特也將其用作JSLint的底層解析器[8]。普拉特也實作了一個基於TECO（英语：TECO (text editor)）的文字編輯器，名為「DOC」，後來更名為「ZED」[9]。

1999年，普拉特建立了當時世界上最小的網頁伺服器——只有火柴盒大小[10][11]。

其他貢獻

普拉特在1995年《位元組（英语：Byte (magazine)）》雜誌的一篇文章中指出，奔騰浮點除錯誤造成的後果可能比英特爾或IBM當時預測的還要嚴重[12][13]。

如今的普拉特影響廣泛。除了史丹佛大學的教授職位外，他還是至少七個專業組織的成員。他是美國計算機協會會士，也是三大數學期刊的編委。他也是TIQIT電腦公司 （页面存档备份，存于互联网档案馆）的創始人、董事長兼執行長，該公司於2010年關閉。

參考資料

  1. ^ Vaughan Ronald Pratt: Shellsort and Sorting Networks. Garland Publishing, Inc., New York & London, 1979, ISBN 0-8240-4406-1
  2. ^ Designers: Vaughan Pratt. Logobook. [2021-08-07]. （原始内容存档于2020-08-09） （英语）. 
  3. ^ Vaughan Pratt. Every prime has a succinct certificate. SIAM Journal on Computing, vol.4, pp.214–220. 1975. Citations （页面存档备份，存于互联网档案馆）, Full-text （页面存档备份，存于互联网档案馆） (requires paid login)
  4. ^ Donald Knuth, James H. Morris, Jr., and Vaughan Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(2):323–350. 1977. Citations （页面存档备份，存于互联网档案馆）
  5. ^ Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E. Time bounds for selection (PDF). Journal of Computer and System Sciences. August 1973, 7 (4): 448–461 [2024-02-10]. doi:10.1016/S0022-0000(73)80033-9 可免费查阅. （原始内容存档 (PDF)于2019-03-31）. 
  6. ^ Pratt, V.R., Top Down Operator Precedence. Proceedings of the ACM Symposium on Principles of Programming Languages. 1973. pp41-51.
  7. ^ George J. Carrette A simple Pratt-Parser （页面存档备份，存于互联网档案馆） for SIOD. 1990.
  8. ^ https://github.com/douglascrockford/JSLint/blob/40e3f73127b56f24a12e5cb091a86d9a24130926/fulljslint.js jslint source code line 2224
  9. ^ Eric Fischer. Emacs and Other Editors （页面存档备份，存于互联网档案馆）. alt.folklore.computers. November 15, 2000.
  10. ^ BBC News.Surfing on a matchbox （页面存档备份，存于互联网档案馆）. 1999.
  11. ^ CNN News. Smallest Web server fits in shirt pocket （页面存档备份，存于互联网档案馆）. 1999.
  12. ^ "How to Bruise an Integer" 互联网档案馆的存檔，存档日期2008-10-07., Byte, March 1995.
  13. ^ "Chain Reaction in Pentiums" （页面存档备份，存于互联网档案馆）, Vaughan Pratt, 1994. In wdv-notes334, 22 Jan, 1995. Article is formatted from a newsgroup posting: Vaughan Pratt. "TECHNICAL: Chain reaction in Pentiums (Was: The Flaw: Pentium-Contaminated Data Persists)". Newsgroup: comp.sys.intel. 1994-12-30 [2006-06-03]. Usenet: [email protected]. （原始内容存档于2012-11-04）. 

外部連結

Read other articles:

Worsbrough Bridge Athletic F.C.

Association football club in England Football clubWorsbrough Bridge AthleticFull nameWorsbrough Bridge Athletic Football ClubNickname(s)The BriggersFounded1923GroundPark Road, WorsbroughCapacity2,000 (175 seated)[1]ChairmanMark BoothManagerLee MorrisLeagueNorthern Counties East League Division One2022–23Northern Counties East League Division One, 15th of 20WebsiteClub website Home colours Worsbrough Bridge Athletic Football Club is a football club based in Worsbrough, Barnsley, Sout...

 

العلاقات الأردنية السيراليونية

العلاقات الأردنية السيراليونية الأردن سيراليون   الأردن   سيراليون تعديل مصدري - تعديل   العلاقات الأردنية السيراليونية هي العلاقات الثنائية التي تجمع بين الأردن وسيراليون.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: و�...

 

AS Pro Gorizia

Italian football club Football clubPro GoriziaFull nameAssociazione SportivaPro GoriziaFounded1923; 101 years ago (1923)GroundStadio Campagnuzza,Gorizia, ItalyCapacity1,000ManagerFabio FrantiLeagueEccellenza – Friuli-Venezia GiuliaWebsiteClub website Home colours Away colours Associazione Sportiva Dilettantistica Pro Gorizia is an Italian association football club located in Gorizia, Friuli-Venezia Giulia. It plays in Eccellenza. Its colors are blue and white. The clu...

Silbermond

Silbermond Silbermond in 2017. Latar belakang Nama lain Exakt, JAST Asal Bautzen, Germany Genre German rock, alternative rock, pop rock Tahun aktif 2000–present Label Modul / Sony Situs web Official site Anggota Stefanie Kloß (lead singer) Andreas Nowak (drums) Johannes Stolle (bass) Thomas Stolle (guitar) Silbermond (dalam Bahasa Inggris berarti Silver Moon) adalah sebuah band rock berasal dari Bautzen, Sachsen, Jerman. Band ini terdiri dari Stefanie Kloß, Andreas Nowak, Johannes dan Th...

 

Allegany County, Maryland

Allegany County, MarylandPengadilan County Cumberland SealLokasi di negara bagian MarylandLokasi negara bagian Maryland di Amerika SerikatDidirikan1789Asal namaGunung AlleghenySeatCumberlandKota terbesarCumberlandWilayah • Keseluruhan42.982 sq mi (111.323 km2) • Daratan42.542 sq mi (110.183 km2) • Perairan440 sq mi (1.140 km2), 1.02%Populasi • (2010)75.087 • Kepadatan176/sq mi (68,1/k...

 

Cinema (Mexican TV channel)

Spanish-language pay television channel For other uses, see Cinema. Television channel CinemaCountryMexicoBroadcast areaLatin AmericaUnited StatesPuerto RicoProgrammingLanguage(s)SpanishPicture format1080i HDTV (downscaled to 480i/576i for the SD feed)OwnershipOwnerTV Azteca Internacional TV de Paga (TV Azteca)Sister channelsAzteca InternacionalCorazónClicAzteca Deportes NetworkHistoryLaunchedMay 5, 2015Former namesAz Cinema (2015–2019)LinksWebsitewww.tvazteca.com/tvpaga/videos/cinema Cin...

Damar Wulan

Damar WulanDamar Wulan, Wayang Klitik dari Jawa Timur.Dongeng rakyatNamaDamar WulanJuga dikenal sebagaiDamarwulanDataPengelompokanTokohMitologiHinduNegaraIndonesiaKawasanJawa Timur Damar Wulan (sering juga ditulis Damarwulan) adalah seorang tokoh legenda cerita rakyat Jawa. Kisah Damar Wulan cukup populer di tengah masyarakat dan banyak terdapat versi lakon, sendratari ataupun cerita tertulis yang telah dibuat mengenainya.[1][2][3] Umumnya, kisah-kisah tersebut adalah ...

 

Hanna-Barbera

Hanna-BarberaLogo L'ex edificio della Hanna-Barbera al 3400 Cahuenga Blvd. West a Hollywood, California, visto in una fotografia del 2007. La piccola struttura gialla (in basso a destra) era originariamente il posto di guardia per l'ingresso della proprietà ad est dell'edificio. Stato Stati Uniti Forma societariaSussidiaria Fondazione7 luglio 1957 a Los Angeles Fondata daWilliam HannaJoseph BarberaGeorge Sidney Chiusura2001 (assorbita dalla Warner Bros. Animation a seguito della mor...

 

哈萨克斯坦总统

此条目序言章节没有充分总结全文内容要点。 (2019年3月21日)请考虑扩充序言，清晰概述条目所有重點。请在条目的讨论页讨论此问题。 哈萨克斯坦總統哈薩克總統旗現任Қасым-Жомарт Кемелұлы Тоқаев卡瑟姆若马尔特·托卡耶夫自2019年3月20日在任任期7年首任努尔苏丹·纳扎尔巴耶夫设立1990年4月24日（哈薩克蘇維埃社會主義共和國總統） 哈萨克斯坦 哈萨克斯坦政府...

Pope Francis bibliography

Pope Francis bibliographyReferences and footnotes The Pope Francis bibliography contains a list of works by Pope Francis. Apostolic Letters See also: Ecclesiastical letter This list is incomplete; you can help by adding missing items. (October 2021) Issued motu proprio See also: Motu proprio Sanctuarium in ecclesia (February 11, 2017) Text Maiorem hac dilectionem (July 11, 2017) Text Magnum principium (September 3, 2017) Text Summa familiae cura (September 8, 2017) Text Imparare a congedarsi...

 

بوابة:بغداد

في ويكيبيديا عربية يوجد 1٬941 مقالة مرتبطة ببوابة بغداد. تحرير عن بغداد بغداد هي عاصمة جمهورية العراق، ومركز محافظة بغداد. يبلغ عدد سكانها 7,216,040 نسمة تقريباً حسب آخر الإحصائيات في العام 2011 للميلاد مما يجعلها أكبر مدينة في العراق وثاني أكبر مدينة في الوطن العربي بعد القاهر...

 

Javelin throw at the Olympics

Track and field event Javelin throwat the Olympic GamesThe 1948 javelin throw competition, Tapio Rautavaara (FIN)OverviewSportAthleticsGenderMen and womenYears heldMen: 1908 – 2020 Women: 1932 – 2020Olympic recordMen90.57 m Andreas Thorkildsen (2008)Women71.53 m Osleidys Menéndez (2004)Reigning championMen Neeraj Chopra (IND)Women Liu Shiying (CHN) The javelin throw at the Summer Olympics is one of four track and field throwing events held at the multi-sport event. Th...

Numeracy

Ability to apply numerical concepts This article is about the ability to apply numerical concepts. For the academic journal, see Numeracy (journal). Innumeracy redirects here. For the book, see Innumeracy (book). Children in Laos have fun as they improve numeracy with Number Bingo. They roll three dice, construct an equation from the numbers to produce a new number, then cover that number on the board, trying to get four in a row. Number bingo improves math skills. LPB Laos. Numeracy is the a...

 

Peloton

Main group of bicycle riders For other uses, see Peloton (disambiguation). Peloton at 2018 Giro d'Italia In a road bicycle race, the peloton (from French, originally meaning 'platoon') is the main group or pack of riders. Riders in a group save energy by riding close (drafting or slipstreaming) to (particularly behind) other riders. The reduction in drag is dramatic; riding in the middle of a well-developed group, drag can be reduced to as little as 5–10%.[1] Exploitation of this po...

 

Italians

Nation and ethnic group native to Italy This article is about the ethnic group. For the country, see Italy. For the language, see Italian language. Italian people redirects here. For other uses, see Italian people (disambiguation). Ethnic group ItaliansItalian: ItalianiTotal populationc. 140 million Italy: 55,551,000[1] Italian diaspora and ancestry: c. 80 million[2] Regions with significant populationsItaly        55,551,000[1]...

Marshall Fredericks

American sculptor Marshall FredericksBornMarshall Maynard Fredericks(1908-01-31)January 31, 1908Rock Island, Illinois, U.S.DiedApril 4, 1998(1998-04-04) (aged 90)Birmingham, Michigan, U.S.Alma materCleveland School of ArtNotable workThe Spirit of Detroit, Indian River Catholic Shrine, Fountain of Eternal LifeStyleArt DecoSpouseRosalind CookeAwardsNational Sculpture Society Medal of Honor, American Institute of Architects Gold Fine Arts Medal, Architectural League of New York Gold Me...

 

Вторжение

У этого термина существуют и другие значения, см. Вторжение (значения). Вторжение вермахта в СССР (1941 год) Вторже́ние — военная операция, заключающаяся в том, что вооружённые силы одного геополитического субъекта при помощи насилия входят на территорию, контролируемую...

 

Asclepiades of Bithynia

1st-century BC Greek physician Not to be confused with Caius Calpurnius Asclepiades of Prusa, born 88 CE. Bust of Asclepiades Asclepiades (Greek: Ἀσκληπιάδης; c. 129/124 BC – 40 BC[1][2]), sometimes called Asclepiades of Bithynia or Asclepiades of Prusa, was a Greek physician born at Prusias-on-Sea[3] in Bithynia in Anatolia and who flourished at Rome, where he practised and taught Greek medicine. He attempted to build a new theory of disease, based on th...

Chimfunshi Wildlife Orphanage

Chimfunshi Wildlife Orphanage is a sanctuary for chimpanzees, located in Zambia's Copperbelt Province. Chimfunshi started as a family-run wildlife orphanage, and today Chimfunshi is managed by a board of trustees to ensure the long-term sustainability of the sanctuary. Chimfunshi was founded in 1983 when a game ranger brought a badly wounded infant chimpanzee to the cattle ranch of David and Sheila Siddle. The Siddles nursed that chimp – named Pal – back to health, thereby establishing a ...

 

Muckamore Abbey Hospital

Mental health hospital in Muckamore, Northern Ireland Hospital in Antrim, Northern IrelandMuckamore Abbey HospitalBelfast Health and Social Care TrustMuckamore Abbey HospitalLocation in Northern IrelandGeographyLocationAbbey Road, Muckamore, Antrim, Northern IrelandCoordinates54°41′32″N 6°11′19″W / 54.6923°N 6.1887°W / 54.6923; -6.1887OrganisationCare systemHealth and Social Care in Northern IrelandTypeSpecialistServicesSpecialityMental healthHistoryOpened1...