Programme de doctorat
Département d’informatique et de génie logiciel
Faculté des sciences et de génie
SOUTENANCE DE THÈSE
de
Jovial Cheukam Ngouonou
Le jeudi 3 octobre 2024 à 9 h
Local 2510, Pavillon Adrien-Pouliot
Lien Zoom:
https://ulaval.zoom.us/j/3054862029
« Apprentissage automatique de cartes d’invariants d’objets combinatoires
avec une application pour la synthèse d’algorithmes de filtrage »
Membres du jury
Présidente
Madame Josée Desharnais, Ph.D.
Département d’informatique et de génie logiciel
Université Laval
Examinateurs
Monsieur Claude-Guy Quimper, Ph.D. (Directeur de recherche)
Département d’informatique et de génie logiciel
Université Laval
Monsieur Nicolas Beldiceanu, Ph.D. (Directeur de recherche en cotutelle)
Département Automatique Productique Informatique
IMT Atlantique, France
Madame Nadia Tawbi, Ph.D. (Examinatrice)
Département d’informatique et de génie logiciel
Université Laval
Madame Christine Solnon, Ph.D. (Examinatrice)
INSA de Lyon, France
Monsieur Christophe Lecoutre, Ph.D. (Examinateur)
Université d’Artois, France
Monsieur François Fages, Ph.D. (Examinateur)
École Polytechnique, France
Pour améliorer l’efficacité des méthodes de résolution de nombreux problèmes d’optimisation combinatoires de notre vie quotidienne, nous utilisons la programmation par contraintes pour générer automatiquement des conjectures. Ces conjectures caractérisent des objets combinatoires utilisés pour modéliser ces problèmes d’optimisation. Ce sont notamment les graphes, les arbres, les forêts, les partitions et les séquences. Contrairement à l’état de l’art, le système, dénommé Bound Seeker, que nous avons élaboré ne génère pas seulement de manière indépendante les conjectures, mais il explicite aussi des liens existant entre les conjectures. Ainsi, il regroupe les conjectures sous forme de bornes précises sur une même variable associée à un même objet combinatoire. Ce regroupement est appelé carte de bornes de l’objet combinatoire considéré. Enfin, une étude consistant à établir des liens entre les cartes générées est faite. Le but de cette étude est d’approfondir les connaissances sur les objets combinatoires et de développer des prémices de preuves automatiques des conjectures. Pour montrer la cohérence des cartes générées par le Bound Seeker, nous élaborons quelques preuves manuelles des conjectures découvertes par le Bound Seeker, ce qui permet de démontrer la pertinence de quelques nouveaux théorèmes de bornes. Pour illustrer l’une des utilités pratiques de ces bornes, nous introduisons une méthode de génération semi-automatique d’algorithmes de filtrage qui réduisent l’espace de recherche des solutions d’un problème d’optimisation combinatoire. Cette réduction est faite grâce aux nouveaux théorèmes de bornes que nous avons établis après les avoir sélectionnés automatiquement parmi les conjectures générées par le Bound Seeker. Pour montrer l’efficacité de cette technique, nous l’appliquons avec succès au problème d’élaboration des cursus académiques équilibrés d’étudiants.
Note: La présentation sera donnée en français.
Bienvenue à tous !
