Vendredi 17 février 2023
Apprentissage de cartes de conjectures sur des bornes précises des caractéristiques d’objet combinatoires
Jovial Cheukam Ngouonou
Doctorant au laboratoire de programmation par contraintes
Heure: 13h30
Local: PLT-2501
Visioconférence: Zoom
Résumé: En programmation par contraintes, la satisfaction de nombreuses contraintes globales peut être détectée en testant les propriétés d’un objet combinatoire. Par exemple, la contrainte All-Different sur N variables est satisfiable si et seulement s’il existe une correspondance de cardinalité N dans un graphe biparti particulier [Regin 1994]. En construction et traitement de preuves de théorèmes, on veut parfois prouver des conjectures sur des objets combinatoires tels que des graphes. Dans les deux domaines de recherche, les chercheurs bénéficieraient de la découverte automatique des relations qui lient entre elles les caractéristiques des objets combinatoires.
C’est ainsi que nous introduisons le concept de carte de conjectures sur des bornes précises des caractéristiques des objets combinatoires, qui fournit un ensemble de bornes précises interdépendantes pour lesdits objets combinatoires.
Nous décrivons ensuite un système basé sur la programmation par contraintes, qui acquiert progressivement des cartes de conjectures. Le système a été testé pour rechercher des conjectures sur les bornes des caractéristiques des graphes orientés : il construit 16 cartes impliquant 431 conjectures sur des bornes inférieures et supérieures précises de huit caractéristiques des graphes orientés.
