Graphes et optimisation

Public concerné et conditions d'accès
Cours de premier cycle. Il est conseillé d'avoir suivi ( ou de suivre en parallèle) les 2 UE de "Mathématiques pour l'informatique" (MVA 003 et MVA 004) .
Finalités de l'unité d'enseignement
Objectifs pédagogiques :
Se familiariser avec des modèles classiques de problèmes d'optimisation,notamment des modèles basés sur  les  graphes.  Apprendre  à  modéliser  de  tels  problèmes,qui  sont  issus  de  l'informatique  et  de  la recherche  opérationnelle,  puis  à  les  résoudre  à  l'aide  d'un  algorithme  et  d'une  structure  de  données appropriés.

Capacités et compétences visées :
Aptitude à formuler et modéliser un problème via les graphes ou la programmation linéaire.
Connaissance d'algorithmes fondamentaux sur les graphes.

Organisation
Nombre de crédits enseignements ECTS : 6 ECTS
Modalités de validation : Examen  écrit  .  Le  professeur,  responsable  national  pour  cette  U.E.,  procède  à  la  vérification  et  à  la validation des sujets d'examen proposés par les CRA.
Projet, mémoire
L'U.E  est  partagée  pour  moitié  du  cours  et  pour  moitié  des  TD.Les  travaux  dirigés  ,  indissociables  du cours, doivent être précédés par un travail personnel.

Contenu de la formation
Les problèmes combinatoires : généralités, difficultés.
Théorie des graphes et algorithmes pour les graphes non valués
Introduction : vocabulaire et concepts de base (connexité, forte connexité, mise en ordre).
Représentations des graphes : matricielles (adjacence, incidence) ; listes (successeurs, prédécesseurs).
Les graphes en tant qu'outil de modélisation ; exemples en informatique et en R. O.
Parcours  des  graphes  :  en  largeur  ;  en  profondeur  ;  applications  ;  détermination  des  composantes connexes, etc.
Fermeture transitive ; détermination, méthode matricielle : algorithme de ROY-WARSHALL ; parcours en profondeur (cas d'un graphe sans circuit).
initiation à la complexité des algorithmes dans le cas polynômial par l'évaluation du nombre d'opérations élémentaires.
Algorithmes d'optimisation dans les graphes valués
Chemins optimaux dans un graphe valué : algorithmes de Bellman, de FORD, de DIJKSTRA. Application :
ordonnancements de projets (méthodes MPM).
Flots maximaux dans un réseau de transport : l'algorithme de FORD-FULKERSON (exemple ; preuve ; complexité).
Arbres couvrants de poids extrémal : algorithmes de KRUSKAL, de PRIM.
Programmation linéaire
Définition, historique ; panorama des applications industrielles, performances et rentabilité.
Approche  géométrique  de  l'optimum  (sommet)  ;  caractérisation  géométrique  du  cheminement  vers  le sommet optimum.
(Un approfondissement de ces concepts de base et des algorithmes associés fait l'objet d' U. E. de niveau au moins égal à BAC+3 en  RCP 110 ou RCP104, RCP105, RCP106 ou encore RCP101).

Téléchargez la fiche de la formation: