Etienne Grandjean (GREYC, Caen)

Après la présentation générale de ces thématiques faite par Etienne Grandjean, Florent Madelaine fera un focus long sur le sujet “Autour des problèmes de contraintes”, dont le résumé est ci-dessous.

Le sujet clé des automates cellulaires ne sera volontairement pas abordé lors de cette séance et sera abordé ultérieurement, notamment lors de la soutenance de la thèse de Nicolas Bacquey (le 4 décembre).

Focus : autour des problèmes de contraintes.

Dans cet exposé, je vais définir une famille de problèmes combinatoires – les problèmes de satisfaction de contraintes – qu’on retrouve sous des noms divers en informatique et mathématiques discrètes. Cette ubiquité rend ces problèmes particulièrement naturels comme objet d’étude, avec à la clé une pluridisciplinarité de la communauté s’y intéressant qui fait la richesse de ce domaine.

Ensuite je vais évoquer la complexité de ces problèmes en esquissant deux approches complémentaires bien établies; l’une, combinatoire, repose sur les notions de décompositions arborescentes et correspond intuitivement au cas où on peut décomposer le problèmes en petits sous-problèmes partageant peu de variables; l’autre approche repose sur des notions d’algèbre et correspond intuitivement au cas où le langage des contraintes est restreint (le langage permettant de décrire les valeurs autorisées pour une contrainte donné).

Au gré de cet exposé, j’expliquerai aussi comment décider quelles personnes il faut inviter pour garantir que la fête soit la plus amusante possible. Une application qui aurait presque sa place dans le thème 3.