NFA010 - Graphes et optimisation  [ 6  crédits ]

Public Concerné

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) .


L'avis des auditeurs
Les dernières réponses à l'enquête d'appréciation pour cet enseignement :

Finalité 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é et compétences acquises
  • Aptitude à formuler et modéliser un problème d'optimisation.
  • Connaissance d'algorithmes fondamentaux sur les graphes.
  • Utilisation de structures de données fondamentales : tableau, file et pile.
Organisation
6 Crédits 
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, propriétés de connexité et forte connexité.
  • Représentations des graphes : matricielles (adjacence, incidence) ; listes (successeurs, prédécesseurs) ; tableaux.
  • Les graphes en tant qu'outil de modélisation ; exemples en informatique et en R. O.
  • Fermeture transitive : détermination, méthode matricielle : algorithme de Roy-Warshall.
  • Initiation à la complexité des algorithmes dans le cas polynomial par l'évaluation du nombre d'opérations élémentaires.
  • Parcours des graphes : en largeur ; en profondeur ; applications ; détermination des composantes connexes, etc.

 

Algorithmes d'optimisation dans les graphes valués :

  • Chemins optimaux dans un graphe valué : algorithmes de Bellman, de Ford et de Dijkstra.
  • Application : ordonnancements de projets (méthode MPM).
  • Flot maximum dans un réseau de transport : algorithme de Ford-Fulkerson.
  • Arbres couvrants de poids extrémal : algorithmes de Kruskal et de Prim.

 

Programmation linéaire :

  • Définition, historique.
  • 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).

Modalités d'évaluation

L'enseignante, responsable nationale pour cette U.E., procède à la vérification et à la validation des sujets d'examen proposés par les CCR.

Bibliographie
  • R. FAURE, B. LEMAIRE, C. PICOULEAU : Précis de recherche opérationnelle (Dunod).5ème édition.
  • Groupe ROSEAUX : Exercices et problèmes résolus de R.O., T1 : Graphes, T3 : Programmation Linéaire (Masson).
  • Amélie Lambert et Agnès Plateau : Informatique Inf (Dunod, 2017) chapitre 11 : Algorithmique de graphes

Trouvez votre formation

Trouvez une Unité d'Enseignement

Contacter nos centres d'enseignements

02 18 69 18 30
Numéro régional, coût d'un appel local
Lundi : 14h - 18h
Du mardi au vendredi : 10h - 12h / 14h - 18h

Région

centre-region Chartres Dreux Pithiviers Orléans Bourges Chateauroux Tours Vierzon Blois

Documents à télécharger

Formation ALTERNANCE Modalités de cours VAE Formation à distance Espace numérique de formation CPF