Quelques présentations et exposés

 

 

Séminaires sur mes intérêts de recherche (printemps 2005)

 

Titre: Théorie algébrique des automates et complexité de communication   fichier (pdf)

Résumé:
L'algèbre des semigroupes constitue un outil puissant pour analyser les automates finis et classifier les langages réguliers qu'il
reconnaissent. Je donnerai un aperçu de cette approche et du type de résultats qui peuvent en découler. En particulier, je proposerai le
problème suivant. Supposons qu'Alice et Bob reçoivent une chaîne de n caractères a_1a_2 ... a_n tel qu'Alice ne connait que les a_i où i est
impair et Bob les a_i où i est pair. Pour un langage L de A*, on appelle complexité de communication le minimum de bits d'information qu'Alice et Bob doivent échanger afin de déterminer si le mot qu'ils ont reçu fait partie du langage L. En utilisant un point de vue algébrique, il est possible de déterminer, à une constante près, la complexité de communication de n'importe quel langage régulier.

 

 

Titre: Satisfaisabilité de contraintes et algèbre universelle   fichier (pdf)


Résumé:
On appelle problème de satisfaisabilité de contraintes (CSP) un problème de décision de la forme suivante. Les données sont constituées d'une liste de variables x_1, ... ,x_n et d'une liste de contraintes qui relient et contraignent ces variables (e.g. (x_3,x_7) appartient à une relation R). Le problème est de décider si on peut assigner aux variables des valeurs telles que toutes les contraintes soient satisfaites. Ce schéma très général englobe la plupart des problème d'intérêt dans NP (satisfaisabilité, 3-coloriage de graphe et autres problèmes combinatoires) et apparaît naturellement dans des contextes d'IA ou de bases de données. Une conjecture prétend que tout  CSP est soit dans P soit NP-complet. Nous montrerons comment des outils algébriques ont permis des avancées importantes vers la confirmation de cette hypothèse.

 

 

Titre: complexité paramétrée des problèmes de satisfaisabilité de contraintes  fichier (pdf)


Résumé:
Le problème de la couverture par sommets (trouver un ensemble V de k sommets tels que toute arête a un sommet dans V) d'un graphe est
NP-complet  et n'admet donc probablement pas d'algorithme efficace. Pourtant, il existe un algorithme de complexité O(kn + 1.3^k) qui résoud ce problème et qui est efficace si k est petit. De façon générale, la complexité paramétrée permet ainsi de distinguer les problèmes qui ont un algorithme efficace à condition qu'un certain paramètre k du problème soit relativement petit des problèmes qui n'ont probablement pas d'algorithme de temps o(n^k).
Je présenterai quelques résultats sur la complexité paramétrée des problèmes de satisfaisabilité Booléens et proposerai une extension de
ceux-ci aux domaines plus grands.

 

 

Séminaire d’introduction à la complexité

 

 

 

Quelques exposés de conférences