Soutenance de thèse de Jovial Cheukam Ngouonou

Résumé : Apprentissage automatique de cartes d’invariants d’objets combinatoires avec une application pour la synthèse d’algorithmes de filtrage. 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.