Graphes, recherche arborescente et complexité

Description du cours

Ce cous s’articule autour de deux axes.

• Le premier axe traitera de la complexité des problèmes avec comme objectif principal d’apprendre à distinguer les problèmes pour lesquels des algorithmes efficaces pour les résoudre existent, des autres. Les notions de réduction entre problèmes et complétude seront des outils privilégiés pour comparer et évaluer la difficulté des problèmes. On observera que, malheureusement, nombre problèmes de la vie courante n’ont a priori pas de traitement efficace.
• Le second axe traitera de la modélisation et de la résolution (exacte ou approchée) de problèmes difficiles. Nous aborderons la modélisation de problèmes (notamment de configuration comme le Taquin ou le problème des n dames) par des graphes à espace d’états ainsi que la résolution de tels problèmes, notamment avec l’algorithme A∗ . Nous introduirons également des notions de base concernant la modélisation et la résolution de problèmes de satisfaction de contraintes. Pour finir, quelques méthodes de résolutions approchées (heuristiques et méta-heuristiques) seront présentées. Les séances de TD et de TP permettront d’appliquer les notions de modélisation et de résolution vu en cours ainsi que de manipuler des solveurs de problèmes de satisfaction de contraintes.