Objectifs – acquis d’apprentissage
Applications des graphes.
Prérequis
L’unité de programmation de mathématiques discrètes 1.
Contenu pédagogique
- Graphes orientés : représentations, théorème d’Euler, Kuratowvski, connexité, chemins, cycles.
- Explorations des graphes : parcours en profondeur; largeur, décomposition par niveaux, recherche des composantes connexes et fortement connexes, graphe réduit.
- Graphes valués : algorithmes de Djikstra, Bellman, programmation dynamique et applications, chemin de débit maximal, le plus sûr, …
- Introduction au problème d’ordonnancement : méthodes potentiels-tâches, PERT, ordonnancement de projet.