INGI Seminar

À propos d'une famille d'algorithmes pour compresser/abstraire une table de valeurs en une table de conditions sur/entre ces valeurs

par Baudouin Le Charlier, professeur ordinaire émérite à l'université catholique de Louvain

Le problème discuté dans cette présentation a potentiellement de l'intérêt en programmation par contraintes et en data mining. On considère des tableaux à deux dimensions dont les colonnes correspondent à des variables prenant leurs valeurs dans des domaines finis. Les lignes des tableaux (ou tables) énumèrent les tuples de valeurs autorisées pour les variables. Le nombre de ces tuples est en général exponentiel dans le nombre de variables. Dans certains cas, dits "intéressants", ces tuples peuvent être décrits de manière beaucoup plus compacte par des conditions arithmétiques sur et entre ces variables. On s'intéresse alors à "découvrir" un tableau de telles conditions, aussi réduit que possible, équivalent à un tableau de tuples de valeurs, donné.

Dans cette présentation, je décrirai diverses améliorations apportées à l 'algorithme présenté lors de la conférence IJCAI 2017 "Automatic Synthesis of Smart Table Constraints by Abstraction of Table Constraints", en les illustrant par des exemples et des résultats expérimentaux. Je donnerai, notamment, une meilleure caractérisation conceptuelle de la méthode utilisée, en montrant sa similitude avec le problème "bien connu" de la minimisation d'une formule booléenne écrite sous forme normale disjonctive. De cette caractérisation, on tire une méthode théorique pour résoudre optimalement le problème mais la méthode n'est applicable strictement que sur des problèmes (i.e. des tables de valeurs) de petite taille ou "bien conditionnés". Je proposerai alors un choix de stratégies pour résoudre le problème de façon approchée avec divers compromis entre la précision et le temps d'exécution. J'illustrerai les stratégies sur divers types de tables "faciles" ou "difficiles" à compresser, avec des comparaisons de mesures expérimentales. Pour obtenir une précision optimale, l'algorithme doit potentiellement mémoriser et comparer des sous-tableaux arbitraires de la table à compresser, en les triant lexicographiquement selon une permutation quelconque des variables (colonnes). Je montrerai comment on peut le faire sans jamais construire ces sous-tableaux explicitement, en utilisant des tableaux d'indices à une dimension, deux niveaux d'indirection pour les lignes et deux niveaux pour les colonnes. Je montrerai expérimentalement la supériorité de cette implémentation sur celle décrite dans [1].

Baudouin Le Charlier est actuellement professeur ordinaire émérite à l'université catholique de Louvain, attaché à l'institut de recherche ICTEAM. Auparavant, il a été chercheur, assistant et professeur à l'institut d'informatique des facultés notre-dame de la paix, à Namur, puis professeur à la faculté des sciences appliquées de Louvain, renommée par la suite école polytechnique. Il a donné des cours de méthodes de programmation et de théorie des langages de programmation avec le souci de justifier rigoureusement ses dires et de convaincre son auditoire. Pour survivre dans la carrière académique, il a signé et co-signé, dans divers domaines tels que, par exemple, l'analyse statique des programmes ou la sécurité informatique, quelques articles totalement dispensables. Durant toute sa "carrière" de chercheur et d'enseignant, il a mené sa petite croisade contre les vertus supposées de la formalisation dans les sciences mathématique et informatique.