| Année
|
Récipiendaire
|
Lieu de la conférence
|
Travaux récompensés
|
| 2022
|
Patrick Cousot[3]
|
ICALP (Paris)
|
Pour son introduction en 1977, de l'interprétation abstraite qui est devenue l'un des concepts fondamentaux des langages de programmation. Cousot a formulé les mathématiques au cœur du cadre, et dirigé sa transition vers une utilisation industrielle. Cousot a décrit le concept dans le manuel Principles of Abstract Interpretation.
|
| 2021
|
Toniann Pitassi
|
ICALP (Glasgow)
|
Pour ses contributions en théorie de la complexité, entre autres en complexité des preuves, l'introduction de nouveaux modèles, le développement de nouvelles techniques et l'établissement de nouvelles connexions entre différents domaines. Ses travaux sconcernent l'apprentissage et l'optimisation informatiques, la vérification et la résolution de problèmes SAT, la complexité des circuits et la complexité des communications, ainsi que leurs applications.
|
| 2020
|
Mihalis Yannakakis
|
ICALP (Sarrebruck)
|
Pour ses contributions nombreuses et variées à l'algorithmique, la théorie de la complexité, optimisation combinatoire, les bases de données, et la vérification. En particulier sur les limitations de l'optimisation linéaire, l'introduction des classes de complexité max-SNP (voir APX (complexité)) et PLS (en), des travaux autour du théorème PCP, et des travaux fondamentaux sur la vérification de modèles.
|
| 2019
|
Thomas Henzinger
|
ICALP (Patras)
|
Vérification et synthèse formelles des systèmes réactifs, en temps réel et hybrides, et application de méthodes formelles aux systèmes biologiques.
|
| 2018
|
Noam Nisan
|
ICALP (Prague)
|
Théorie de la complexité (complexité de la communication, apprentissage, parallélisme, théorie de l'aléa...) et théorie algorithmique des jeux
|
| 2017
|
Éva Tardos
|
ICALP (Varsovie)
|
Algorithmes fortement polynomiaux, programmation linéaire et conception des algorithmes, algorithmes d’approximation, théorie algorithmique des jeux.
|
| 2016
|
Dexter Kozen
|
ICALP (Rome)
|
Complétude de la logique dynamique propositionnelle, machine de Turing alternante, logique modale, algèbre de Kleene, complexité des théories algébriques réelles, décomposition de Kozen-Landau en calcul formel, sémantique probabiliste. Auteur de manuels fondamentaux en informatique théorique.
|
| 2015
|
Christos Papadimitriou
|
ICALP (Kyōto)
|
Algorithmique, théorie de la complexité, théorie algorithmique des jeux, théorie des bases de données, optimisation, robotique. « Christos Papadimitriou combine un corpus de résultats scientifiques large, influent et varié avec les dons d'un enseignant inspirant et d'un grand communicateur ».
|
| 2014
|
Gordon Plotkin
|
ICALP (Copenhague)
|
Sémantique opérationnelle structurelle (SOS), sémantique dénotationnelle, théorie des types, théorie des domaines et analyse catégorielle, plus généralement en théorie de la démonstration, sémantique des langues naturelles, algèbres de processus.
|
| 2013
|
Martin Dyer
|
ICALP (Riga)
|
Algorithmes linéaires en temps pour des programmes linéaires en basse dimension, avec applications en géométrie algorithmique. Analyse probabiliste d'algorithmes. Algorithme randomisé en temps polynomial d'approximation du volume d'un objet convexe en grande dimension. Complexité du dénombrement de problèmes de satisfaction de contraintes.
|
| 2012
|
Moshe Vardi
|
ICALP (Warwick)
|
Application de la logique à l'informatique, la théorie des bases de données, la théorie des modèles finis, la modélisation de la connaissance dans les systèmes multi-agents, vérification de modèles. Moshe Vardi est coauteur des ouvrages Reasoning about Knowledge et Finite Model Theory and its Applications.
|
| 2011
|
Boris Trakhtenbrot
|
ICALP (Zurich)
|
Un des pères fondateurs de l'informatique théorique, visionnaire, pionnier dans plusieurs directions : en théorie de la complexité, le « gap theorem » ou « théorème de la lacune » ; en théorie des modèles le théorème de Trakhtenbrot. Trakhtenbrot d'une part, J. Büchi et C. Elgot d'autre part démontrent de manière indépendante l'équivalence entre les automates finis et la logique monadique du second ordre (MSO), résultat appelé le théorème de Büchi-Elgot-Trakhtenbrot.
|
| 2010
|
Kurt Mehlhorn
|
ICALP (Bordeaux)
|
Auteur de plusieurs livres. Contributions fondamentales en structures de données, la géométrie algorithmique, le calcul formel, le calcul parallèle, technologie VLSI, et théorie de la complexité, combinatorial optimization, et algorithmique des graphes, complexité de la communication. Création avec Stefan Näher de LEDA .
|
| 2009
|
Gérard Huet
|
ICALP (Rhodes)
|
Unification de termes typés du Lambda-calcul. Théorie des types. Réécriture et complétion de Knuth-Bendix. Assistant de preuve Coq.
|
| 2008
|
Leslie Valiant
|
ICALP (Reykjavik)
|
Introduction de la classe de complexité #P, théorème de Vazirani-Valiant, apprentissage automatique, en particulier l'apprentissage PAC, algorithmes holographiques. Familles d'automates à pile déterministes ; calcul distribué et parallèle.
|
| 2007
|
Dana S. Scott
|
ICALP (Wrocław)
|
Théorie des automates, sémantique des langages de programmation, logique modale, topologie, et théorie des catégories. Sa collaboration avec Christopher Strachey a jeté les bases des approches modernes de la sémantique des langages de programmation.
|
| 2006
|
Mike Paterson
|
ICALP (Venise)
|
Conception et analyse des algorithmes et théorie de la complexité. Théorie des langages, algorithmique distribuée, théorie des automates. Coauteur d'un livre sur les groupes automatiques. Réputé comme inventeur de jeux, comme les vers de Paterson ou les sprouts.
|
| 2005
|
Robin Milner
|
ICALP (Lisbonne)
|
Démonstrateur de théorèmes Logic for Computable Functions ou LCF. Langage de programmation ML avec inférence de types polymorphe et un système de gestion d'exceptions typé. Calculus of Communicating Systems (CCS) pour l'analyse de systèmes concurrents. pi-calcul et bisimulation.
|
| 2004
|
Arto Salomaa
|
ICALP (Turku)
|
langages formels, la théorie des automates, la combinatoire des mots et la cryptographie. Il est, avec notamment Maurice Nivat et Grzegorz Rozenberg, l'un des fondateurs de l'informatique théorique européenne. Auteur et éditeur de nombreux ouvrages, initiateur et animateur à tous les niveaux de la recherche.
|
| 2003
|
Grzegorz Rozenberg
|
ICALP (Eindhoven)
|
Théorie des langages formels et des automates, réécriture des graphes, systèmes de Lindenmayer, réseaux de Petri, théorie des traces. Il s'est fait le promoteur et le héraut du natural computing et du DNA computing, lui a donné son nom actuel et en a dessiné les contours. Il est fondateur du périodique International Journal on Natural Computing. Auteur et éditeur de nombreux traités.
|
| 2002
|
Maurice Nivat
|
ICALP (Malaga)
|
Avec Arto Salomaa et Grzegorz Rozenberg, l'un des fondateurs de l'informatique théorique européenne. Il s'est fait le porte-drapeau de la science informatique au sens de Marcel-Paul Schützenberger. Théorie des langages et des automates, sémantique des langages de programmation, il est à l'origine d'une importante école française d'informatique théorique.
|
| 2001
|
Corrado Böhm
|
ICALP (Crète)
|
Informaticien et logicien, auteur du structured program theorem dans la « programmation sans Goto ». Lambda-calcul, notamment comparaison des β-conversion et la η-conversion. Machine abstraite CUCH. Codage de Böhm-Berarducci. Un des fondateurs de l'école italienne d'informatique théorique et de programmation fonctionnelle.
|
| 2000
|
Richard Karp
|
ICALP (Genève)
|
Classe des problèmes NP-complets. Nombreux algorithmes : algorithme d'Edmonds-Karp pour le problème de flot maximum ; algorithme de Hopcroft-Karp pour un problème de couplage ; le théorème de Karp-Lipton en théorie de la complexité ; algorithme de Rabin-Karp de recherche de motifs. Test de primalité probabiliste. Un pilier de l'informatique théorique.
|
