La Recherche Opérationnelle (RO) est un domaine très important de l'informatique théorique et appliquée, autant dans la recherche que l'industrie. Je préfère l'appeler Optimisation Combinatoire, car cela exprime mieux ce qu'on y fait: face à un problème combinatoire, comme la confection d'un emploi du temps, où toute décision locale peut avoir un impact à l'autre bout du problème par le jeux des contraintes liées, on cherche à trouver une solution optimale.

Ce cours donne un panorama assez large de la RO, en commençant par les bases assez algorithmiques et en s'attardant très vite sur des examples d'applications.

Le but est que l'étudiant soit capable d'identifier de tels problèmes d'optimisation à l'avenir, et sache quel(s) outil(s) utiliser, et comment. Un exemple de problème combinatoire: étant donnés l'ensemble des résultats d'un grand tournoi sportif où il n'est pas rare qu'A ait battu B qui a battu C qui a re-battu A, comment établir un classement global qui minimise à posteriori le nombre de matches “inattendus” où un joueur moins bien classé à gagné contre un mieux classé ?

Les TDs accompagnent naturellement le cours en mettant immédiatement en pratique les notions abordées. Ils sont en C++, mais d'un niveau adapté pour les débutants comme pour les confirmés. Ils ont des auto-tests qui permettent d'itérer et de progresser rapidement.

1. Graphes et algorithmes: BFS, Union-Find.
2. Arbres et algorithmes: Hauteur, Centre…
3. Programmation Dynamique.
4. Algorithms Gloutons, comme l'Arbre Couvrant Minimum.
5. Heuristiques et Approches Monte-Carlo (Diamètre d'un graphe, Miller-Rabin..).
6. Programmation Linéaire et Entière: Principe et Modélisation avancée.

• Rappels d'algorithmique de base
• Haute Performance en C++
• SAT solving
• Algorithmes de Flow (Max-Flow, Min-cost-Flow) et leurs applications

• Savoir programmer
• Affinité pour l'algorithmique