Leslie Valiant - Leslie Valiant

„Les Valiant“ přeadresuje tady. Nesmí být zaměňována s Statečný (disambiguation).

Leslie Valiant

FRS
Leslie Valiant (oříznuto) .jpg
2005 ve společnosti Oberwolfach
narozený
Leslie Gabriel Valiant

(1949-03-28) 28. března 1949 (věk 71)
Budapešť, Maďarská republika
NárodnostSpojené království
Alma mater
Známý jako
Ocenění
Vědecká kariéra
PoleMatematika
Teoretická informatika
Teorie výpočetního učení
Teoretická neurověda
Instituce
TezePostupy rozhodování pro rodiny deterministických automatů s rozbalováním  (1974)
Doktorský poradceMike Paterson[3]
Doktorandi
webová stránkalidémoře.harvard.edu/ ~ udatný

Leslie Gabriel Valiant FRS[4][5] (narozený 28 března 1949) je britský Američan[6] počítačový vědec a výpočetní teoretik.[7][8] V současné době je profesorem informatiky a aplikované matematiky T. Jeffersona Coolidgea na Harvardská Univerzita.[9][10][11][12] Valiant byl oceněn DOPOLEDNE. Turing Award v roce 2010 poté, co byly popsány A.C.M. jako hrdinská postava v teoretické informatice a vzor jeho odvahy a kreativity při řešení některých nejhlubších nevyřešených problémů ve vědě; zejména pro jeho „nápadnou kombinaci hloubky a šířky“.[6]

Vzdělávání

Valiant byl vzděláván v King's College v Cambridge,[13][6] Imperial College London,[13] [6] a University of Warwick kde v roce 1974 získal titul PhD v oboru počítačových věd.[14][3]

Výzkum a kariéra

Valiant je světově proslulý svou prací v teoretická informatika. Mezi jeho mnoho příspěvků teorie složitosti, představil pojem # P-úplnost („ostrý-P úplnost“), aby vysvětlil, proč jsou problémy s výčtem a spolehlivostí neřešitelné. Rovněž představil „pravděpodobně přibližně správné“ (PAC ) model strojového učení, který pomohl růst oblasti výpočetní teorie učení, a koncept holografické algoritmy. V počítačových systémech je nejznámější zavedením hromadně synchronní paralelně model zpracování. Jeho dřívější práce v teorie automatů zahrnuje algoritmus pro bezkontextovou analýzu, který je (od roku 2010) stále asymptoticky nejrychleji známý. Pracuje také v výpočetní neurověda se zaměřením na porozumění paměti a učení.

Kniha Valiant z roku 2013 je Pravděpodobně přibližně správné: Algoritmy přírody pro učení a prosperitu ve složitém světě.[15] V něm mimo jiné tvrdí, že evoluční biologie nevysvětluje rychlost evoluce, píše například: „Důkazy, že Darwinovo obecné schéma evoluce je v podstatě správné, jsou přesvědčivé pro velkou většinu biologů. byl v dostatečném počtu přírodovědných muzeí, aby se sám přesvědčil. To vše však neznamená, že současná evoluční teorie je adekvátně vysvětlující. V současné době evoluční teorie nemůže nabídnout žádný popis rychlosti, jakou evoluce postupuje k vývoji složitých mechanismů nebo je udržovat v měnícím se prostředí. “

Valiant začal učit v Harvardská Univerzita v roce 1982 a v současné době je profesorem výpočetní techniky a aplikované matematiky T. Jeffersona Coolidgea v USA Harvardská škola inženýrství a aplikovaných věd. Před rokem 1982 učil na Univerzita Carnegie Mellon, University of Leeds a University of Edinburgh.

Ceny a vyznamenání

Valiant obdržel Cena Nevanlinna v roce 1986 Knuth Prize v roce 1997 Cena EATCS v roce 2008,[16] a ACM Turing Award v roce 2010.[17][18] Byl zvolen a Člen Královské společnosti (FRS) v roce 1991,[4] člen týmu Sdružení pro povýšení umělé inteligence (AAAI) v roce 1992,[19] a člen Americká národní akademie věd v roce 2001.[20] Valiantova nominace na královská společnost zní:

Valiant rozhodujícím způsobem přispěl k růstu téměř každého odvětví teoretické informatiky. Jeho práce se zabývá hlavně matematickým vyčíslením nákladů na zdroje při řešení problémů na počítači. V rané práci (1975) našel asymptoticky nejrychlejší algoritmus známý pro rozpoznávání bezkontextových jazyků. Zároveň propagoval využití komunikačních vlastností grafů pro analýzu výpočtů. V roce 1977 definoval pojem # P-úplnosti („sharp-P“) a založil svou užitečnost při klasifikaci problémů s počítáním nebo výčtem podle výpočetní traktability. První aplikací bylo počítání shody (permanentní funkce matice). V roce 1984 Valiant představil definici indukčního učení, která poprvé srovnává výpočetní proveditelnost s použitelností logických pravidel, která se mají naučit netriviální třídy. * V poslední době navrhl schéma pro efektivní směrování komunikace v systému s více procesory. Ukázal, že režie spojené s řídkou sítí nemusí růst s velikostí systému. Tím se z teoretického hlediska stanoví možnost efektivních paralelních počítačů pro všeobecné účely.[5]

Citace jeho A.M. Turing Award zní:

Pro transformační příspěvky k teorii výpočtu, včetně teorie pravděpodobně přibližně správného (PAC) učení, složitosti výčtu a algebraických výpočtů a teorie paralelních a distribuovaných výpočtů.[6]

Osobní život

Jeho dva synové Gregory Valiant[21] a Paul Valiant[22] jsou oba teoretičtí počítačoví vědci jako fakulty na Stanfordská Univerzita a Brown University resp.[8]

Reference

  1. ^ Valiant, L .; Vazirani, V. (1986). „NP je stejně snadné jako detekce jedinečných řešení“ (PDF). Teoretická informatika. 47: 85–93. doi:10.1016/0304-3975(86)90135-0.
  2. ^ Valiant, L. G. (1979). "Složitost výčtu a problémy se spolehlivostí". SIAM Journal on Computing. 8 (3): 410. doi:10.1137/0208032.
  3. ^ A b C Leslie Valiant na Matematický genealogický projekt
  4. ^ A b „Leslie Valiant FRS“. Londýn: královská společnost. 1991.
  5. ^ A b http://royalsociety.org/DServe/dserve.exe?dsqIni=Dserve.ini&dsqApp=Archive&dsqDb=Catalog&dsqCmd=show.tcl&dsqSearch=(RefNo==%27EC%2F1991%2F35%27)
  6. ^ A b C d E „Leslie G. Valiant - laureát ceny A.M. Turinga“. DOPOLEDNE. Turing Award. Citováno 9. ledna 2019.
  7. ^ Hoffmann, L. (2011). „Otázky a odpovědi: Leslie Valiant pojednává o strojovém učení, paralelních výpočtech a výpočetní neurovědě.“. Komunikace ACM. 54 (6): 128. doi:10.1145/1953122.1953152.
  8. ^ A b Anon (2017). „Statečný, Prof. Leslie Gabriel“. Kdo je kdo. ukwhoswho.com (online Oxford University Press vyd.). A & C Black, otisk Bloomsbury Publishing plc. doi:10.1093 / ww / 9780199540884.013.U40928. (předplatné nebo Členství ve veřejné knihovně ve Velké Británii Požadované) (vyžadováno předplatné)
  9. ^ Leslie Valiant stránka s profilem autora na ACM Digitální knihovna
  10. ^ Wigderson, A. (2009). „Práce Leslie Valiantové“. Sborník 41. ročníku sympozia ACM o Sympóziu o teorii výpočetní techniky - STOC '09. str. 1. doi:10.1145/1536414.1536415. ISBN  9781605585062.
  11. ^ Leslie G. Valiant na DBLP Bibliografický server Upravte to na Wikidata
  12. ^ Valiant, Leslie (1984). „Teorie učitelného“ (PDF). Komunikace ACM. 27 (11): 1134–1142. doi:10.1145/1968.1972.
  13. ^ A b „Životopis Leslie G. Valiantové“ (PDF). Harvardská Univerzita. Citováno 9. ledna 2019.
  14. ^ Valiant, Leslie (1973). Rozhodovací postupy pro rodiny deterministických automatů. warwick.ac.uk (Disertační práce). University of Warwick. OCLC  726087468. EThOS  uk.bl.ethos.475930.
  15. ^ Základní knihy, ISBN  9780465032716
  16. ^ David Peleg Cena EATCS 2008 - Laudatio pro profesora Leslie Valiant Evropská asociace teoretické informatiky.
  17. ^ Josh Fishman „„ Pravděpodobně přibližně správný “vynálezce z Harvardu U., získal Turingovu cenu.“ Kronika vysokoškolského vzdělávání 9. března 2011.
  18. ^ Ocenění ACM Turing Award získává inovátor ve strojovém učení ACM Computing News
  19. ^ Zvolení členové AAAI Sdružení pro povýšení umělé inteligence.
  20. ^ Členský adresář: Leslie G. Valiant Národní akademie věd.
  21. ^ http://theory.stanford.edu/~valiant/
  22. ^ http://cs.brown.edu/~pvaliant/

Tento článek zahrnuje text k dispozici pod CC BY 4.0 licence.