La combinatoire est l’analyse de configurations d’objets comme, par exemple, les mots ou séquences, les arbres, les graphes ou réseaux qui sont des objets premiers en modélisation et algorithmique informatique.
L’étude combinatoire des suites discrètes (suites de symboles aussi appelées mots ou séquences) s’intéresse aux propriétés que peuvent avoir ou non certaines suites de symboles ainsi qu’aux moyens (automates, fonctions itérées, …) pour engendrer des mots ayant des caractéristiques données. Nous nous intéressons plus particulièrement à des propriétés comme l'absence de certains motifs ou de certaines répétitions, le nombre maximal de palindromes, la quasipériodicité, ... Les problèmes étudiés sont inspirés ou issus de domaines variés comme la géométrie discrète ou l’algorithmique du texte.
L'optimisation combinatoire consiste à trouver la meilleure solution parmi un nombre fini (mais souvent très grand) de choix. C'est une branche de la programmation mathématique qui recouvre les méthodes servant à déterminer l'optimum d'une fonction sous des contraintes données. Les modèles étudiés sont généralement issus de problèmes réels (optimisation dans les réseaux, problèmes d’affectations, de tournées, ...). Nous nous intéressons aux propriétés de ces problèmes et au développement d'outils permettant de les résoudre efficacement (méthodes exactes, heuristiques, algorithmes d'approximation, ...). Ces outils peuvent être théoriques ou appliqués à la résolution de problèmes concrets dans une approche de recherche opérationnelle de solutions.
- L'Unité
- Membres
- Formation
Combinatoire