Optimisation (Combinatoire)
(Last updated: 2022-12-02)
Tous les mercredi, de 15:00 à 18:30
- Cours de 15:00 à 16:30, salle 1003
- TP de 16:45 à 18:30, salle 2031 (+2036 si besoin)
Cours: plan indicatif
- Graphes. Implémentations (C++). Composantes connexes. Tables de hachage.
- [Fusionné avec le cours 1] Parcours de graphe (BFS, DFS). Composantes fortement connexes. Dijkstra.
- Arbres et leurs algorithmes. Autres graphes particuliers (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:
- La revolution SAT (CDCL)
- Max-Flow, Min-cost flow
- Revisions 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 + TD 2 (même séance, mais 2 rendus): Graphes, BFS, Dijkstra
TD 3 Arbre, DAG, Programmation dynamique
TD 4 Programmation dynamique
TD 5 Algorithmes Gloutons
TD 6 Heuristiques, Monte-Carlo, Approximations
TD 7 Programmation Linéaire
TD 8 Programmation Linéaire et Entière
TD 9 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.