Optimisation

Catalogue des cours de Télécom SudParis

Code

IUSF MAT 3602

Niveau

L3

Graduate

UnderGraduate

Semestre

Spring

Domaine

Mathématiques

Programme

Programme Ingénieur

Langue

Français/French

Crédits ECTS

2

Heures programmées

28.5

Charge de travail

60

Coordonnateur(s)

Département

  • Réseaux et Services Multimédia Mobiles

Equipe pédagogique

Organisation

Cours/TD/TP/projet/examen : Heures Cours/TD/TP/CF1 : 0/28.5/0/3

Acquis d'apprentissage

Au terme du module MAT 3602, l’étudiant de première année sera capable de :
- démontrer des résultats de base en théorie des graphes et théorie de l'optimisation;
- modéliser des situations pratiques par des problèmes d’optimisation dans des graphes ou sous la forme de programmes mathématiques en variables continues;
- proposer et mettre en œuvre des méthodes pour résoudre ces problèmes.

Compétences CDIO

  • 1.1.1 - Mathématiques (y compris statistiques)
  • 2.1.1 - Apprendre à poser et formuler les problèmes
  • 2.1.2 - Modélisation

Prérequis

Programme de mathématiques des classes préparatoires aux grandes écoles

Mots-clés

Optimisation, modélisation, graphes, programmation mathématique (linéaire et non linéaire).

Contenu

-CI 1 (3h) : introduction à la théorie des graphes
-CI 2 (3h) : problème de l’arbre couvrant de poids minimal : algorithmes de Kruskal et Prim
-CI 3 (3h) : problème du plus court chemin : algorithmes de Moore-Dijkstra et Bellman-Ford
-CI 4 (3h) : flots dans les réseaux de transport : algorithme de Ford-Fulkerson
-CI 5 (3h) : algorithme de Busacker- Gowen. Ordonnancements
-CI 6 (3h) : programmation linéaire
-CI 7 (1h30) : dualité
-CI 8 (3h) : éléments d’analyse convexe
-CI 9 (3h) : programmation non linéaire sans contrainte
-CI 10 (3h) : programmation non linéaire avec contraintes

Evaluation

- 1re session : contrôle continu par une note de participation (B : bonus de 1,5 points maximum - questionnaire) et un contrôle écrit 3h (C1), documents autorisés : polycopiés distribués
- 2e session : Contrôle écrit 3 heures (C2), documents autorisés : polycopiés distribués
- Note finale : NF = max (C1+B, min(C2+B,13))

Bibliographie

T. Cormen, C. Leiseron et R. Rivest, Introduction à l’algorithmique, Dunod, 2002
J. C. Culioli, Introduction à l'optimisation, Ellipses, 2012
M. Gondran et M. Minoux, Graphes et algorithmes, Tec & Doc Lavoisier, 2009
M. Minoux, Programmation mathématique, Tec & Doc Lavoisier, 2007

Fiche mise à jour le 14/07/2019