Différences

Ci-dessous, les différences entre deux révisions de la page.

--- formations:masters:ue:m2:op10 [2023/04/21 09:17] – supprimée - modification externe (Unknown date) 127.0.0.1
+++ formations:masters:ue:m2:op10 [2023/09/08 13:30] (Version actuelle) – [Description] viger
@@ Ligne 1: / Ligne 1: @@
+~~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

Différences

Outils de la page