MITRO203 est un pré-requis pour suivre MITRO205
Ce cours contient essentiellement deux parties.
L'une porte sur des méthodes d'optimisation combinatoire générales permettant de résoudre des problèmes difficiles (plus précisément, NP-difficiles). On décrit en particulier les méthodes arborescentes par séparation et évaluation, la programmation dynamique, la relaxation lagrangienne, certaines métaheuristiques. On y aborde aussi des problèmes classiques en recherche opérationnelle, comme le problème du voyageur de commerce, le problème du sac à dos ou encore le problème de la coloration de graphes. Des travaux pratiques en C ou en Java viennent compléter la présentation théorique de ces méthodes.
L'autre, issue des mathématiques discrètes, est consacrée à l'analyse combinatoire, autrement dit à l'art du dénombrement ou encore à l'art de compter. On y définit les séries génératrices ordinaires ou exponentielles, le nombre de combinaisons avec ou sans répétitions, le principe d'inclusion-exclusion (théorème de Poincaré), les dérangements, le dénombrement de partitions (nombres de Stirling), etc.
L'une porte sur des méthodes d'optimisation combinatoire générales permettant de résoudre des problèmes difficiles (plus précisément, NP-difficiles). On décrit en particulier les méthodes arborescentes par séparation et évaluation, la programmation dynamique, la relaxation lagrangienne, certaines métaheuristiques. On y aborde aussi des problèmes classiques en recherche opérationnelle, comme le problème du voyageur de commerce, le problème du sac à dos ou encore le problème de la coloration de graphes. Des travaux pratiques en C ou en Java viennent compléter la présentation théorique de ces méthodes.
L'autre, issue des mathématiques discrètes, est consacrée à l'analyse combinatoire, autrement dit à l'art du dénombrement ou encore à l'art de compter. On y définit les séries génératrices ordinaires ou exponentielles, le nombre de combinaisons avec ou sans répétitions, le principe d'inclusion-exclusion (théorème de Poincaré), les dérangements, le dénombrement de partitions (nombres de Stirling), etc.
- Enseignant responsable de l'UE: Olivier Hudry