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

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 : tableaux , file et pile

 

Organisation
6Cré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éthodes MPM).

Flot maximum dans un réseau de transport : l'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).
 

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 Orleans Bourges Chateauroux Tours Vierzon Blois

Documents à télécharger

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