Leslie Valiant

"Les Valiant" leitet hier weiter. Nicht zu verwechseln mit Tapfer (Disambiguierung).
Leslie Valiant

FRS
Leslie Valiant (34913684313).jpg
Valiant im Jahr 2012
Geboren
Leslie Gabriel Valiant

28. März 1949 (Alter 73)
Budapest, Ungarische Republik
Staatsangehörigkeit britisch
Alma Mater
Bekannt für
Auszeichnungen
Wissenschaftliche Karriere
Felder Mathematik
Theoretische Informatik
Computerlerntheorie
Theoretische Neurowissenschaften
Institutionen
These Entscheidungsverfahren für Familien deterministischer Pushdown -Automaten (1974)
Doktorand Mike Paterson[3]
Doktorand
Webseite Personen.Seas.Harvard.edu/~ valiant

Leslie Gabriel Valiant FRS[4][5] (Geboren am 28. März 1949) ist Britisch -Amerikaner[6] Informatiker und Computertheoretiker.[7][8] Derzeit ist er T. Jefferson Coolidge Professor für Informatik und angewandte Mathematik bei Harvard Universität.[9][10][11][12] Valiant wurde mit dem ausgezeichnet Turing Award Im Jahr 2010 wurde von der beschrieben A.C.M. als heldenhafte Figur in der theoretischen Informatik und als Vorbild für seinen Mut und seine Kreativität, einige der tiefsten ungelösten Probleme in der Wissenschaft anzugehen; insbesondere für seine "auffällige Kombination aus Tiefe und Breite".[6]

Ausbildung

Valiant wurde beigebildet King's College, Cambridge,[13][6] Imperial College London,[13][6] und die Universität von Warwick wo er 1974 einen Doktortitel in Informatik erhielt.[14][3]

Forschung und Karriere

Valiant ist weltbekannt für seine Arbeit in Theoretische Informatik. Unter seinen vielen Beiträgen zu Komplexitätstheorieer führte den Begriff von vor #P-Completness ("Sharp-P-Vollständigkeit") Um zu erklären, warum Aufzählungs- und Zuverlässigkeitsprobleme unlösbar sind. Er stellte auch die "wahrscheinlich ungefähr korrekt" vor (PAC) Modell des maschinellen Lernens, das dem Gebiet der rechnerischen Lerntheorie geholfen hat, und das Konzept von Holographische Algorithmen. In Computersystemen ist er am bekanntesten für die Einführung der Bulk -synchroner Parallele Verarbeitungsmodell. Seine frühere Arbeit in Automatenheorie enthält an Algorithmus für kontextfreies Parsen, das ist (ab 2010) immer noch der asymptotisch am schnellsten bekannte. Er arbeitet auch in Rechenneurowissenschaften Konzentration auf das Verständnis von Gedächtnis und Lernen.

Das Buch von Valiant 2013 ist Wahrscheinlich ungefähr korrekt: Naturalgorithmen zum Lernen und Erfolg in einer komplexen Welt.[15] Darin argumentiert er unter anderem, dass die Evolutionsbiologie die Rate, mit der die Evolution auftritt Es war in genügend Naturgeschichte Museen, um sich selbst zu überzeugen. All dies bedeutet jedoch nicht oder um sie in sich ändernden Umgebungen zu erhalten. "

Valiant begann zu unterrichten Harvard Universität 1982 und derzeit der T. Jefferson Coolidge Professor für Informatik und angewandte Mathematik in der Harvard School of Engineering and Applied Sciences. Vor 1982 unterrichtete er bei Carnegie Mellon Universität, das Universität Leeds, und die Universität von Edinburgh.

Auszeichnungen und Ehrungen

Valiant erhielt die NevanLinna -Preis 1986 die Knuth -Preis Im Jahr 1997 die Eatcs Award in 2008,[16] und die Turing Award in 2010.[17][18] Er wurde a gewählt a Fellow der Royal Society (FRS) im Jahr 1991,[4] Ein Fellow der Vereinigung für die Weiterentwicklung der künstlichen Intelligenz (AAAI) im Jahr 1992,[19] und ein Mitglied der Nationale Akademie der Wissenschaften der Vereinigten Staaten im Jahr 2001.[20] Valiants Nominierung für die königliche Gesellschaft liest:

Valiant hat auf entscheidende Weise zum Wachstum fast jeder Zweigstelle der theoretischen Informatik beigetragen. Seine Arbeit geht hauptsächlich darum, die Ressourcenkosten für die Lösung von Problemen auf einem Computer mathematisch zu quantifizieren. In frühen Arbeiten (1975) fand er den asymptotisch schnellsten Algorithmus, der für die Erkennung kontextfreier Sprachen bekannt ist. Gleichzeitig war er Pionier der Verwendung von Kommunikationseigenschaften von Graphen zur Analyse von Berechnungen. 1977 definierte er den Begriff der #P-Completness ("Sharp-P") und etablierte seinen Nutzen bei der Klassifizierung von Zähl- oder Aufzählungsproblemen gemäß der Rechenverfolgung. Die erste Anwendung war das Zählen von Übereinstimmungen (die matrix -dauerhafte Funktion). 1984 führte Valiant eine Definition des induktiven Lernens ein, das zum ersten Mal die machbarkeit der rechnerischen Durchführbarkeit mit der Anwendbarkeit auf nicht triviale Klassen logischer Regeln in Einklang bringt. Er zeigte, dass die Overheads auch in einem spärlichen Netzwerk mit der Größe des Systems nicht wachsen müssen. Dies legt aus theoretischer Sicht die Möglichkeit effizienter allgemeine Zwecke paralleler Computer fest.[5]

Das Zitat für seinen A.M. Turing Award lautet:

Für transformative Beiträge zur Berechnungstheorie, einschließlich der Theorie des wahrscheinlich ungefähr korrekten (PAC) -Lernens, der Komplexität der Aufzählung und der algebraischen Berechnung sowie der Theorie des parallelen und verteilten Computers.[6]

Persönliches Leben

Seine beiden Söhne Gregory Valiant[21] und Paul Valiant[22] sind beide auch theoretische Informatiker.[8]

Verweise

  1. ^ Valiant, L.; Vazirani, V. (1986). "NP ist so einfach wie das Erkennen von einzigartigen Lösungen" (PDF). Theoretische Informatik. 47: 85–93. doi:10.1016/0304-3975 (86) 90135-0.
  2. ^ Valiant, L. G. (1979). "Die Komplexität der Aufzählung und Zuverlässigkeitsprobleme". Siam Journal über Computing. 8 (3): 410–421. doi:10.1137/0208032.
  3. ^ a b c Leslie Valiant Bei der Mathematik Genealogie -Projekt
  4. ^ a b "Leslie Valiant FRS". London: königliche Gesellschaft. 1991.
  5. ^ a b Dserve Archivkatalogshow
  6. ^ a b c d e "Leslie G. Valiant - A. M. Turing Award Laureate". BIN. Turing Award. Abgerufen 9. Januar 2019.
  7. ^ Hoffmann, L. (2011). "Fragen und Antworten: Leslie Valiant diskutiert maschinelles Lernen, parallele Computer und Computerneurowissenschaften". Kommunikation der ACM. 54 (6): 128. doi:10.1145/1953122.1953152.
  8. ^ a b Anon (2017). "Valiant, Prof. Leslie Gabriel". Wer ist wer. UKHOSWHO.com (online Oxford University Pressed.). A & C Black, ein Abdruck von Bloomsbury Publishing Plc. doi:10.1093/ww/9780199540884.013.U40928. (Abonnement oder Großbritannien öffentliche Bibliothek Mitgliedschaft erforderlich.) (Abonnement erforderlich)
  9. ^ Leslie Valiant Autorenprofilseite am ACM Digitale Bibliothek
  10. ^ Wigderson, A. (2009). "Die Arbeit von Leslie Valiant". Verfahren des 41. jährlichen ACM -Symposiums über Symposium über die Theorie des Computing - STOC '09. S. 1–2. doi:10.1145/1536414.1536415. ISBN 9781605585062. S2CID 15370663.
  11. ^ Leslie G. Valiant bei DBLP Bibliographieserver Edit this at Wikidata
  12. ^ Valiant, Leslie (1984). "Eine Theorie des Lernbaren" (PDF). Kommunikation der ACM. 27 (11): 1134–1142. doi:10.1145/1968.1972. S2CID 12837541.
  13. ^ a b "Lebenslauf von Leslie G. Valiant" (PDF). Harvard Universität. Abgerufen 9. Januar 2019.
  14. ^ Valiant, Leslie (1973). Entscheidungsverfahren für Familien deterministischer Pushdown -Automaten. Warwick.ac.uk (Doktorarbeit). Universität von Warwick. OCLC 726087468. Ethos uk.bl.ethos.475930.
  15. ^ Grundbücher, ISBN9780465032716
  16. ^ David Peleg Der Eatcs Award 2008 - Laudatio für Professor Leslie Valiant Europäische Vereinigung der theoretischen Informatik.
  17. ^ Josh Fishman "" Wahrscheinlich ungefähr korrekt "Erfinder aus Harvard U. gewinnt Turing Award" Chronik der Hochschulbildung 9. März 2011.
  18. ^ Der ACM Turing Award geht an Innovator im maschinellen Lernen ACM Computing News
  19. ^ Gewählte AAAI -Stipendiaten Assoziation zur Weiterentwicklung künstlicher Intelligenz.
  20. ^ Mitgliedsverzeichnis: Leslie G. Valiant Nationale Akademie der Wissenschaften.
  21. ^ Gregory Valiant Homepage
  22. ^ Paul Valiants Homepage

Externe Links

Dieser Artikel enthält Text Verfügbar unter dem CC um 4.0 Lizenz.