# Prix EATCS

Le prix EATCS est un prix, remis par l'European Association for Theoretical Computer Science (EATCS) à un chercheur pour honorer sa brillante carrière en informatique théorique.

## Description

Le prix EATCS est remis chaque année depuis 2000. Il récompense un chercheur pour des travaux étendus et largement reconnus en informatique théorique tout au cours d'une carrière scientifique. Le prix est remis à l'occasion de la conférence ICALP. Il est accompagné d'une somme de 1000 euros.

## Lauréats

    Année Récipiendaire Lieu de la conférence Travaux récompensés 2022 Patrick Cousot 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.