Au pays des graphes, des arbres et des polyèdres
Recherche algorithmique ● Mathématiques ● Informatique
#structures combinatoires #arbres #graphes
Brochure pliable avec poster au dos
Mathilde Boussange
Graphiste et illustratrice
www.mathildeboussange.be
Jean Cardinal
Professeur, chercheur et co-directeur du Groupe de Recherche en Algorithmique (ALGO) Département d’informatique, Faculté des Sciences, ULB
« J’ai aimé m’emparer d’un sujet que je ne connaissais pas, avec des termes techniques qui au début m’ont fait peur. J’ai aussi beaucoup aimé travailler avec une personne experte et passionnée par son sujet. C’est très agréable de travailler quand le contenu est déjà là et que je n’ai plus qu’à me plonger dans un travail graphique et visuel. Je me suis sentie quand même très libre d’aller dans la direction que je voulais. Franchement, j’ai beaucoup aimé ce cours, merci. »
Arbres sur les graphes : structures de données, génération combinatoire, polyèdres
Mathématiques discrètes et structures combinatoires appliquées à l’informatique
Ce projet concerne des questions de mathématiques discrètes appliquées à l’informatique. Le cadre est donc théorique : on cherche d’abord à bien comprendre certaines structures mathématiques en vue d’améliorer la complexité de certains algorithmes, et d’en concevoir de nouveaux. Ces recherches sont effectuées en collaboration avec plusieurs autres équipes, notamment au Canada, au Royaume-Uni et en Allemagne.
Deux structures mathématiques interviennent : les graphes, constitués d’un ensemble d’objets dont certains sont reliés entre eux, et les arbres. Un arbre est une abstraction mathématique d’une hiérarchie, ou d’un système de décision, dans lequel chaque décision correspond à un embranchement, et les sous-arbre correspondent aux conséquences de cette décision et aux décisions futures. Les arbres sont utilisés dans les bases de données et les réseaux, entre autres. Une structure de donnée classique basée sur les arbres est appelée « arbre binaire de recherche », qui permet de rechercher de l’information dans un ensemble ordonné.
Deux résultats ont été publiés récemment sur certaines familles d’arbres construits sur des graphes. Nous avons montré d’abord que ces arbres permettaient d’effectuer des recherches dans un espace structuré également comme un arbre (« trees on trees »), étendant la notion d’arbre binaire de recherche. On généralise donc la recherche dans un ensemble « ordonné » à la recherche dans un ensemble « arborescent ». On étudie les performances théoriques de ces nouveaux algorithmes, en utilisant des raisonnements combinatoires.
Nous avons également étudié des algorithmes efficaces pour la génération exhaustive de tels arbres : donner rapidement la liste de tous les arbres sur un graphe donné. Ce faisant, on généralise également certains algorithmes existants pour des cas particuliers et on établit des liens entre des problèmes de structures de données et des objets géométriques tels que les polyèdres.
L’impact espéré à long terme est une meilleure compréhension de certaines notions mathématiques et algorithmiques, l’unification de certains concepts présents dans différents sous-domaines de recherche, et la généralisation d’algorithmes existants pour des cas particuliers.