v2.6.4 (3846)

Electif - MOD-IFIE2-ELTIF-Mod3-SED&AO : MODSIM : Introduction à l'Optimisation Discrète

Descriptif

L'optimisation discrète est sous-domaine des mathématiques discrètes qui s'intéresse à déterminer dans un ensemble discret d'éléments un parmi les meilleurs sous-ensembles (ou solutions) réalisables. Pour ce faire, le passage obligé consiste à modéliser mathématiquement le problème considéré (Recherche Opértaionnelle), déterminer sa complexité théorique (Théorie de la complexité), et enfin utiliser la méthode de résolution adaptée (Algorithmique).

En optimisation discrète, nous distinguons les problèmes dit simple, c'est à dire pour lequel nous avons démontré qu'un algorithme polynomial en temps et en espace existe pour le résoudre, des problèmes dit difficiles, c'est à dire pour lequel nous ne savons pas exhiber un algorithme polynomial en temps et en espace pour le résoudre.   

Objectifs pédagogiques

Les objectifs de ce cours sont d'amener à une meilleure compréhension des problèmes combinatoires par le fait de savoir :

  • modéliser un problème combinatoire,
  • analyser sa complexité théorique,
  • afin de choisir de manière justifiée une méthode de résolution pertinente. 

34.5 heures en présentiel
réparties en:
  • Cours Magistraux : 10.5
  • Travaux Dirigés : 22.5
  • Evaluation des connaissances et capacités : DS, QCM, présentation orale : 1.5

Soit 75 heures de travail global estimé pour l’étudiant.

Diplôme(s) concerné(s)

UE de rattachement

Format des notes

Numérique sur 20

Pour les élèves du diplômeDiplôme d'Ingénieur IMT Mines Albi

Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)

    Le coefficient de l'enseignement est : 3

    Programme détaillé

    Le cours est découpé en trois temps :

    • Partie 1 : Introduction à l'optimisation discrète par la pratique d'une métaheuristique
    • Partie 2 : Notion de graphes, complexité et raisonnement
    • Partie 3 : Etude d'une métaheuristique - l'algorithme génétique
    Veuillez patienter