Der Turing-Preis 2010 ehrte Leslie Valiant für seinen prägenden Einfluss auf die theoretische Informatik, ein Fachgebiet, das er durch die Entwicklung fundamentaler Modelle für das Lernen und die Parallelverarbeitung mitgestaltet hat. 1949 in Budapest geboren, hat er seine Karriere der Bestimmung der mathematischen Grenzen dessen gewidmet, was Computer leisten können, und damit eine Brücke zwischen abstrakter Logik und komplexer realer Datenverarbeitung geschlagen.
Akademische Grundlagen und frühe Karriere
Valiant absolvierte sein Studium am King's College in Cambridge, am Imperial College London und an der University of Warwick, wo er 1974 promovierte. Zu seinen frühen akademischen Stationen gehörten Tätigkeiten an der Carnegie Mellon University von 1973 bis 1974 sowie an der University of Leeds zwischen 1974 und 1976. Anschließend war er von 1976 bis 1982 an der University of Edinburgh tätig, bevor er an die Fakultät der Harvard University wechselte, wo er derzeit als T. Jefferson Coolidge Professor für Informatik und Angewandte Mathematik wirkt.
Beiträge zur Komplexitätstheorie
Seine Forschungen zur Rechenkomplexität führten zur Einführung der #P-Vollständigkeit, eines Rahmens, der erklären soll, warum bestimmte Aufzählungs- und Zuverlässigkeitsprobleme von Natur aus schwer zu lösen sind. Diese Arbeit ermöglichte es Forschern, Zählprobleme anhand ihrer algorithmischen Lösbarkeit zu klassifizieren. Zudem entwickelte er einen Algorithmus für das kontextfreie Parsen, der in asymptotischer Hinsicht nach wie vor der schnellste bekannte Ansatz ist.
Lernmodelle und parallele Systeme
Valiant entwickelte das Modell des wahrscheinlich ungefähr Richtigen Lernens (PAC-Modell), das eine theoretische Grundlage für das maschinelle Lernen schuf, indem es die Machbarkeit des induktiven Lernens definierte. Im Bereich der Systemarchitektur führte er das Bulk Synchronous Parallel (BSP)-Modell ein. Dieses Konzept bietet eine Struktur für paralleles und verteiltes Rechnen, analog zum Von-Neumann-Architekturmodell, und wurde von Systemen wie MapReduce, Pregel sowie verschiedenen Open-Source-Projekten wie Hadoop und Spark übernommen.
Zwanzig Fragen, acht Minuten auf der Uhr und ein Perzentil, gemessen an allen bisherigen Teilnehmern. Ohne Anmeldung.
IQ-Test starten →Ehrungen und berufliche Auszeichnungen
Als Staatsbürger des Vereinigten Königreichs und der Vereinigten Staaten ist Valiant gewähltes Mitglied der National Academy of Sciences, der Royal Society und der American Academy of Arts and Sciences. Neben dem Turing-Preis war seine Laufbahn durch den Nevanlinna-Preis 1986, den Knuth-Preis 1997 und den EATCS-Preis 2008 geprägt. Er ist außerdem Fellow der Association for the Advancement of Artificial Intelligence.
Steckbrief
- Geboren: 1949, Budapest - Aktuelle Position: Professor an der Harvard University - Hauptarbeitsgebiete: Informatik, Mathematik - Ausbildung: University of Warwick, Imperial College London, King's College - Bedeutende Auszeichnung: Turing-Preis (2010) - Staatsbürgerschaft: Vereinigtes Königreich, Vereinigte Staaten
Häufig gestellte Fragen
### Was ist der Hauptbeitrag des PAC-Modells?
Es schuf eine theoretische Grundlage für das maschinelle Lernen, indem es die rechnerische Machbarkeit mit den zu erlernenden logischen Regeln in Einklang brachte.
### Warum ist das BSP-Modell von Bedeutung?
Es dient als einflussreiches Modell für parallele und verteilte Computerarchitekturen und ermöglicht eine groß angelegte Datenverarbeitung.
