Le prix Turing 2010 a récompensé Leslie Valiant pour son influence transformatrice sur l'informatique théorique, un domaine qu'il a façonné grâce au développement de modèles fondamentaux pour l'apprentissage et le traitement parallèle. Né à Budapest en 1949, il a consacré sa carrière à établir les limites mathématiques de ce que les ordinateurs peuvent accomplir, jetant un pont entre la logique abstraite et le calcul complexe du monde réel.
Fondements académiques et début de carrière
Valiant a poursuivi ses études supérieures au King's College de Cambridge, à l'Imperial College de Londres et à l'Université de Warwick, où il a obtenu son doctorat en 1974. Ses débuts dans l'enseignement incluent des postes à l'Université Carnegie Mellon de 1973 à 1974 et à l'Université de Leeds entre 1974 et 1976. Il a ensuite occupé un poste à l'Université d'Édimbourg de 1976 à 1982, avant de rejoindre le corps professoral de l'Université Harvard, où il occupe actuellement le poste de professeur T. Jefferson Coolidge d'informatique et de mathématiques appliquées.
Contributions à la théorie de la complexité
Ses recherches sur la complexité theorique ont conduit à l'introduction de la complétude #P, un cadre conçu pour expliquer pourquoi des problèmes spécifiques d'énumération et de fiabilité sont intrinsèquement difficiles à résoudre. Ces travaux ont permis aux chercheurs de classifier les problèmes de dénombrement en fonction de leur traitabilité informatique. De plus, il a développé un algorithme d'analyse syntaxique hors contexte qui demeure l'approche la plus rapide connue sur le plan asymptotique.
Modèles d'apprentissage et systèmes parallèles
Valiant a créé le modèle PAC (Probably Approximately Correct), qui a fourni un fondement théorique à l'apprentissage automatique en définissant la faisabilité de l'apprentissage inductif. Dans le domaine de l'architecture des systèmes, il a introduit le modèle BSP (Bulk Synchronous Parallel). Ce cadre offre une structure pour le calcul parallèle et distribué, analogue au modèle de von Neumann, et a été adopté par des systèmes tels que MapReduce, Pregel, ainsi que divers projets open source comme Hadoop et Spark.
Vingt questions, huit minutes au chronomètre et un centile mesuré face à tous ceux qui l’ont passé. Sans inscription.
Passer le test de QI →Distinctions et nominations professionnelles
Citoyen du Royaume-Uni et des États-Unis, Valiant est membre élu de la National Academy of Sciences, de la Royal Society et de l'American Academy of Arts and Sciences. Outre son prix Turing, sa carrière a été marquée par le prix Nevanlinna en 1986, le prix Knuth en 1997 et le prix de l'EATCS en 2008. Il est également membre de l'Association for the Advancement of Artificial Intelligence.
En bref
- Naissance : 1949, Budapest - Poste actuel : Professeur à l'Université Harvard - Domaines principaux : Informatique, Mathématiques - Éducation : Université de Warwick, Imperial College London, King's College - Distinction notable : Prix Turing (2010) - Nationalité : Royaume-Uni, États-Unis
Questions fréquentes
### Quelle est la principale contribution du modèle PAC ?
Il a introduit une base théorique pour l'apprentissage automatique en conciliant la faisabilité informatique et les règles logiques à apprendre.
### Pourquoi le modèle BSP est-il important ?
Il sert de modèle influent pour les architectures de calcul parallèle et distribué, permettant le traitement de données à grande échelle.
