Optimisation (Combinatoire)

(Last updated: 2021-02-10)

Reprise du Cours + TD en présentiel à partir du 10 février

Contactez-moi si vous n'avez pas eu l'info! Je l'avais diffusée via le groupe optimisation-2021@googlegroups.com.

Tous les Mercredi, de 14:30 à 18:30

Cours: plan indicatif

  1. Graphes. Implémentations (C++). Composantes connexes. Tables de hachage. Parcours (BFS, DFS). Composantes fortement connexes. Dijkstra.
  2. Cours 2 "fusionné" avec le cours 1.
  3. Arbres et leurs algorithmes. Autres graphes particuliers (DAG, Tri topologique). Programmation dynamique: 1er exemple.
  4. Programmation dynamique: autres exemples.
  5. Arbre couvrant minimum et autres Algorithmes Gloutons: Vidéo
  6. Heuristiques, Monte-Carlo (exemples: diamètre d'un graphe. Miller-Rabin).
  7. Programmation linéaire (aka LP)
  8. Programmation linéaire entière (aka MIP)
  9. MIP: Modélisation avancée.
  10. Examen blanc commenté
Sujets que j'aimerais traiter si le temps le permet:

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

TD 10 Programmation par Contraintes

Modalités et Évaluation

Note = 50% Examen Final (sur papier) et 50% TD

Cours au tableau, en présentiel si possible

TP en C++, avec Auto-Tests