Complexité et graphes

Prérequis : EP2 « Algorithmique avancée : structures de données » de l’UE 4-2 « Algorithmique et développement » et EP2 « Programmation fonctionnelle » de l’UE 2-2 « Informatique fondamentale »
Objectifs : maîtriser les outils mathématiques nécessaires à l'analyse des performances d'un algorithme ; avoir une idée de ce qui est traitable actuellement avec un ordinateur, montrer comment améliorer les performances des algorithmes faciles ; savoir expliquer comment aborder les problèmes difficiles.
Compétences acquises : connaître les classes de problèmes traitables ou non dans l’algorithmique actuelle ; savoir estimer la performance d’un algorithme et améliorer cette performance ; connaître les principales techniques de parcours et de manipulation de graphe ; savoir comment contourner des problèmes difficiles sur les graphes, et utiliser des algorithmes d’exploration sur les graphes pour traiter des problèmes posés dans le domaine de l’intelligence artificielle.
Contenu : 1. Complexité : machine de Turing, les classes de complexité, les problèmes NP-complets, réduction et complétude, 2. Graphes : représentation et manipulation de base des graphes, exploration de graphes et composantes connexes, recherche de chemins optimaux, arbres de recouvrement minimaux, problèmes de flots, problèmes NP-complet sur les graphes (problème du voyageur de commerce, coloration de graphes) et méthodes de contournement (algorithmes d’approximation et heuristiques universelles). 3. Intelligence Artificielle : représentation et résolution de problèmes (graphes d’état et algorithmes de recherche), les algorithmes de recherche informés (meilleur d’abord, recherche gloutonne, l’algorithme A*, SMA*).