Le 14 décembre 2016, à 10h, amphithéatre S19 de la faculté Jean Perrin

Résumé :

Le comptage de modèles (i.e., des affectations de valeurs aux variables qui satisfont toutes les contraintes) constitue un traitement clé pour divers problèmes d’intelligence artificielle dans lesquels la programmation par contraintes est employée. La compilation de connaissances est l’une des approches possibles permettant de réaliser efficacement une telle requête de comptage. Dans cette thèse, nous introduisons plusieurs nouveaux langages de compilation de formules propositionnelles, basés sur un connecteur peu utilisé jusqu’ici dans les langages cibles pour la compilation, le ou exclusif. Nous définissons en particulier le langage des arbres de décision affine (ADT) et le langage des arbres de décisions affine étendus (EADT). Nous proposons également un compilateur CNF vers EADT que nous avons évalué et nous présentons les résultats expérimentaux obtenus. Ces résultats montrent qu’une approche basée sur le langage EADT concurrence, et est parfois même plus performante, que des algorithmes directs (sans compilation) de l’état de l’art pour le comptage de modèles. Nous nous sommes également intéressés à la compilation de réseaux de contraintes. En effet, il existe jusqu’ici peu de méthodes permettant de compter le nombre de modèles d’un réseau de contraintes. Nous avons introduit et étudié le langage cible des graphes de décision décomposables multivalués (MDDG). Nous avons développé un compilateur de réseaux de contraintes vers MDDG dans lequel plusieurs ingrédients originaux ont été testés, comme l’utilisation d’une heuristique de choix de variables basée sur la centralité d’intermédiarité ou encore la détection et la prise en compte des contraintes universelles.

Composition du jury :

  • Hélène Fargier (IRIT-CNRS)
  • Bruno Zanuttini (Université de Caen - Base Normandie)
  • Frédéric Koriche (Université d’Artois)
  • Jean-Marie Lagniez (Université d’Artois)
  • Pierre Marquis (Université d’Artois)
  • Laurent Simon (Université de Bordeaux)