Optimisation (Combinatoire)
(Last updated: 2025-01-15)
Tous les mercredi, de 16h à 19h: Cours de 16:00 à 17:30 en salle 1009, TP de 17:30 à 19:00 en salle 2001
Cours: plan indicatif
-
Graphes. Implémentations (C++). Composantes connexes. Tables de hachage. Parcours (BFS, DFS). Union-Find.
Dijkstra
-
Arbres et leurs algorithmes. DAG, Tri topologique.
Programmation dynamique: 1er exemple.
- Programmation dynamique: autres exemples.
- Arbre couvrant minimum et autres Algorithmes Gloutons
- Heuristiques, Monte-Carlo (exemples: diamètre d'un graphe. Miller-Rabin).
- Programmation linéaire (aka LP)
- Programmation linéaire entière (aka MIP)
- MIP: Modélisation avancée.
- Examen blanc commenté
Sujets que j'aimerais traiter si le temps le permet:
- Max-Flow, Min-cost flow
- La revolution SAT (CDCL)
- Dualité
- Autres révisions d'algorithmique: Hash tables. Tas. Complexité.
TDs
Tous les TDs sont évalués.
La note globale de contrôle continue sera une "moyenne/médiane" des notes de TD.
Voir la page de Rendu
TD 1 Graphes, BFS, Dijkstra
TD 2 Arbre, DAG, Programmation dynamique
TD 3 Programmation dynamique
TD 4 Algorithmes Gloutons
TD 5 Heuristiques, Monte-Carlo, Approximations
TD 6 Programmation Linéaire
TD 7 Programmation Linéaire et Entière
TD 8 Programmation Linéaire et Entière - Avancée
-
Modalités et Évaluation
Note = 50% Examen Final (sur papier) et 50% TD
Cours au tableau (en présentiel)
Pas de support de cours, mais des vidéos (dispo après chaque cours)
TD en C++, avec Auto-Tests et corrigés dispos après le TD.
- Adaptés aux débutants en C++ (mais aux experts aussi)
- TD = application directe du cours.