Cette unité d'enseignement a pour objectif d'initier les étudiants à la modélisation de situations réelles sous la forme de problèmes algorithmiques connus. Les domaines d'applications abordés seront les suivants :
Les modèles que nous allons utilisés pour la formalisation des problèmes réels sont les problèmes de graphes (plus court chemin, arbre couvrant, coloration, couplage, flot, etc), les programmes linéaires et les formules propositionnelles. Les algorithmes et méthodes utilisés pour résoudre les problèmes issus de ces domaines d'applications seront les suivants :
-
algorithmes dédiés
-
programmation dynamique
-
heuristiques (algorithme glouton, recherche locale, …)
-
utilisation de solveurs (programmation linéaire, SAT, …)