Programme de Doctorat en informatique
Département d’informatique et de génie logiciel
Faculté des sciences et de génie
Présentation orale de la proposition de projet de recherche
De
Jovial Cheukam Ngouonou
Mardi 10 mai 2022 à 9h00
Par vidéoconférence (voir lien ci-dessous)
Rejoindre la réunion Zoom :
https://ulaval.zoom.us/j/3054862029
« Apprentissage de cartes d’invariants dans le cadre d’objets combinatoires. »
Learning invariant maps in the context of combinatorial objects.
Membres du comité d’encadrement
Pr. Nicolas Beldiceanu, Ph.D., (co-directeur)
IMT Atlantique
HDR. Remi Douence, Ph.D., (co-directeur)
IMT Atlantique
Pr. Claude-Guy Quimper, Ph.D., (Co-directeur)
Département d’informatique et de génie logiciel, Université Laval
Pr. Nadia Tawbi, Ph.D., (évaluatrice)
Département d’informatique et de génie logiciel, Université Laval
Pr. Pascal Tesson, Ph.D., (évaluateur)
Département d’informatique et de génie logiciel, Université Laval
Résumé
Les invariants liant plusieurs caractéristiques d’un objet combinatoire (une permutation, un arbre, une forêt, un graphe orienté, une série temporelle) sont un composant essentiel pour une résolution efficace de problèmes combinatoire à l’aide de techniques de programmation par contraintes ou de programmation linéaire. Si ces invariants sont souvent recherchés manuellement pour un problème précis, quelques approches proposent de générer des conjectures, puis éventuellement de les prouver, pour certaines familles de problèmes ou sur plusieurs domaines. Cependant, aucune approche ne propose d’apprendre non seulement des invariants dépendants les uns des autres, mais également de mettre en évidence de manière explicite les relations entre ces invariants pour construire des « cartes d’invariants ». De plus, aucune n’exploite le potentiel de la programmation par contraintes pour la recherche d’invariants. Une carte d’invariants peut être vue comme un graphe dans lequel les sommets sont des invariants et les arcs correspondent à la relation entre deux invariants donnés, montrant comment un invariant se dérive à partir d’un invariant plus général. Nous proposons donc d’acquérir de telles cartes au travers des objectifs suivant:
* 1er objectif : pouvoir formaliser la notion de cartes d’invariants et construire un système d’acquisition automatique d’une telle carte en utilisant la programmation par contraintes.
* 2ème objectif : pouvoir faire de la régression pour l’apprentissage de conjectures sous forme de polynômes pouvant contenir des sous-termes correspondants à de simples fonctions arithmétiques.
* 3ème objectif : pouvoir trouver des invariants se présentant sous la forme d’arbres de décision.
Abstract
The invariants linking several characteristics of a combinatorial object (a permutation, a tree, a forest, a directed graph, a time series) are an essential component for an efficient solution of combinatorial problems using constraint programming or linear programming techniques. If these invariants are often searched manually for a specific problem, some approaches propose to generate conjectures, then eventually to prove them, for some families of problems or on several domains. However, no approach proposes to learn not only mutually dependent invariants, but also to explicitly highlight the relations between these invariants in order to build « invariant maps ». Moreover, none of them exploits the potential of constraint programming for finding invariants. An invariant map can be seen as a graph in which the vertices are invariants and the arcs correspond to the relationship between two given invariants, showing how an invariant derives from a more general invariant. We therefore propose to acquire such maps through the following objectives:
* 1st objective: to be able to formalise the notion of invariant maps and to build an automatic acquisition system of such a map using constraint programming.
* 2nd objective: to be able to perform regression for learning conjectures in the form of polynomials that can contain sub-terms corresponding to simple arithmetic functions.
* 3rd objective: to find invariants in the form of decision trees.
Note: La présentation sera donnée en français.
Bienvenue à tous!
