formations:masters:ue:m2:op10 [UFR Informatique]

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.

~~NOTOC~~

====== Optimisation Combinatoire ======

===== Description =====

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.

===== Syllabus =====

==== Sujets centraux ====

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

==== Sujets potentiellement traités ====
  * Rappels d'algorithmique de base
  * Haute Performance en C++
  * SAT solving
  * Algorithmes de Flow (Max-Flow, Min-cost-Flow) et leurs applications

===== Pré-requis =====

  * Savoir programmer
  * Affinité pour l'algorithmique

Outils pour utilisateurs

Outils du site

Outils de la page