Equipe "Calculs, Graphes et Logique" (CGL)

Présentation

Tous les sujets étudiés par l'équipe font partie de domaines de l'informatique théorique. C'est en effet l'informatique théorique qui est le point commun des activités de recherche et de l'intéret des chercheurs de l'équipe.

L'informatique théorique est l'étude des fondements logiques et mathématiques de l'informatique. L'informatique théorique se caractérise par une approche par nature plus mathématique et moins empirique. Ses objectifs ne sont pas toujours directement reliés r des enjeux technologiques. De nombreuses disciplines peuvent etre regroupées sous cette dénomination diffuse, y compris la théorie de la calculabilité, l'algorithmique (en anglais: analysis and design of algorithms) et la théorie de la complexité, l'étude de la sémantique des langages de programmation et la théorie des automates et langages formels. Cela inclut aussi une grande partie de la logique en informatique.

Le but principal des recherches de l'équipe est de mieux comprendre et de mieux développer des objets théoriques d'informatique reliés plus ou moins r la notion de calcul: construction et analyse d'algorithmes, modcles du calcul, sémantique de programmes et programmation automatique.

Les activités de recherche de l'équipe couvrent et vont couvrir plusieurs branches fondamentales de l'informatique théorique. Le but principal de ces recherches est de contribuer r l'élargissement des connaissances et des savoir faire sur quelques questions fondamentales de l'informatique et r développer des méthodes et outils pour de nouvelles approches permettant de résoudre de façon calculatoire des problcmes théoriquement et pratiquement importants.

Actions

Action 1 : Algorithmes de Graphes

De nombreux problèmes sont difficiles à résoudre algorithmiquement. Les plus connus sont les problèmes NP-complets qui couvrent un grand nombre de problèmes très importants en pratique (informatique, ingénierie, télécommunication, biologie, etc.) qu'on ne peux pas résoudre exactement par un logiciel pour des entrées de grande taille. Néanmoins, une solution exacte est souvent souhaitable, au moins pour des instances de taille modeste, par exemple, pour un graphe d'entrée avec une centaine de sommets pour un problème de graphes (par exemple le calcul du nombre chromatique).

Une des approches utilise ce qu'on appelle les algorithmes exacts en temps exponentiel. Une grande partie des recherches de Dieter Kratsch y est dédiée et va s'employer à la construction et à l'analyse d'algorithmes exacts pour des problcmes difficiles de graphes. Plusieurs questions naturelles reliées aux algorithmes exacts et exponentiels seront étudiées, par exemple les algorithmes sous-exponentiels, les algorithmes pour des problèmes d'énumération (qui arrivent souvent dans des applications biologiques) et les algorithmes pour des problcmes PSPACE-complets. En plus, on utilisera l'idée de l'exploitation de structures (de graphes) et l'algorithmique de paramètre fixe pour la construction et l'analyse des algorithmes exacts et exponentiels.

Action 2 : Modèles de Calcul

Les résultats les plus marquants de Maurice Margenstern dans la période 2007-2011 sont ses travaux sur les automates cellulaires hyperboliques et sur les pavages dans le plan hyperbolique. En 2007, Maurice Margenstern a résolu une conjecture ouverte depuis 1971, en démontrant que le pavage du plan hyperbolique est indécidable. Par ailleurs, il envisage d'obtenir de nouveaux résultats en matière d'automates cellulaires hyperboliques universels. Maurice Margenstern espère parvenir à deux états aussi bien dans le plan que dans l'espace.

Il a aussi des activités importantes dans les calculs moléculaires, ce domaine de l'informatique théorique ou l'on cherche à modéliser des phénomènes de biologie moléculaire. Maurice Margenstern s'intérèsse à ces thèmes de recherche principaux : indécidabilité – décidabilité, calculs moléculaires et automates cellulaires. Ainsi, il espère améliorer les meilleurs résultats actuels en universalité faible (configuration initiale non finie mais au plus périodique) : quatre états dans le plan et trois états dans l'espace.

Action 3 : Sémantique de Programme et Programmation Automatique

Les thèmes de recherches de Sorin Stratulat et Loïc Colson sont très liés.

En sémantique des programmes, Loïc Colson a imaginé il y a quelques années un nouveau paradigme de système logique qu'il a appelé systèmes pédagogiques. L'idée de ces systèmes est que toute invocation d'un élément dans une démonstration doit s'appuyer sur un exemple concret d'un tel élément. L'étude approfondie de ce système sera un but principal de ses recherches localisées en logique.

Sorin Stratulat va poursuivre ses recherches en démonstration automatique, notamment ses travaux concernant l'utilisation de la récurrence implicite.

Projet de recherche

Le principal destinataire direct des activités de l'équipe est et sera le monde de la recherche. Les produits typiques de nos recherches sont des publications dans les actes de conférences et dans les journaux scientifiques dont le public et essentiellement constitué par confrères.

Les résultats attendus des recherches dans les différents axes de l'informatique théorique concerneront typiquement les questions fondamentales et contribueront à la recherche internationale sur les sujets de grand intéret pour ces thèmes et, dans le meilleur des cas, elles contribueront à promouvoir de nouvelles techniques et de nouvelles méthodes pour faire progresser la connaissance significativement.

Membres

Responsable

Membres permanents

Membres non permanents