Descriptif
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.
Objectifs pédagogiques
Acquis d'apprentissage
À l'issue de ce module, l'élève sera capable de:
- Dénombrer des structures discrètes définies par des propriétés combinatoires.
- Appliquer des méthodes de dénombrement (résolution de relations de récurrence, séries génératrices, principe d'inclusion-exclusion) à des problèmes issus de domaines variés (ensembles ordonnés, probabilités, complexité algorithmique, etc.).
- Résoudre, de manière exacte ou approchée, des problèmes d'optimisation combinatoire difficiles (typiquement, NP-difficiles).
- Adapter des méthodes générales à la résolution d'autres problèmes que ceux vus en cours en concevant les ingrédients spécifiques mis en oeuvre par ces méthodes.
Compétences de rattachement (et justification)
- BC1.3 – Elaborer une ou plusieurs solutions technologiques, en s’appuyant sur la modélisation théorique et la méthode scientifique de manière à faire ressortir la pertinence desdites solutions permettant une prise de décision; Justification : La partie de l'UE consacrée à l'optimisation combinatoire présente des méthodes algorithmiques permettant d'élaborer des solutions logicielles destinées à résoudre des problèmes d'optimisation combinatoire, de manière exacte ou approchée.
- BC10.2 – Analyser et résoudre des problèmes mathématiques et algorithmiques nécessaires dans des étapes de réalisation d’un projet en s’appuyant, si besoin est, sur des simulations et dans l’objectif d’implémenter des solutions compétitives; Justification : L’UE amène les élèves à analyser et résoudre divers problèmes mathématiques issus de l'analyse combinatoire et divers problèmes algorithmiques dans le cadre de l'optimisation combinatoire.
Diplôme(s) concerné(s)
UE de rattachement
- CSC_4MIS2_TP : Filière Mathématique, Informatique théorique et Recherche opérationnelle (créneau B) - Semestre 2
Format des notes
Numérique sur 20Pour les étudiants du diplôme Diplôme d'ingénieur
Vos modalités d'acquisition :
Contrôle de connaissance écrit de trois heures.
Le rattrapage est autorisé (Note de rattrapage conservée)- le rattrapage est obligatoire si :
- Note initiale < 10
Le coefficient de l'UE est : 1
Pour les étudiants du diplôme Echange international non diplomant
Vos modalités d'acquisition :
Contrôle de connaissance écrit de trois heures.
Le rattrapage est autorisé (Note de rattrapage conservée)- le rattrapage est obligatoire si :
- Note initiale < 10
Le coefficient de l'UE est : 1
Programme détaillé
