Graphes et optimisation
NFA010
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.
Public 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) .
Méthodes de validation :
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.
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 RCP104, RCP105, RCP106, RCP101 et RCP219).
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
Cette UE apparaît dans les diplômes et certificats suivants :
Informations, Orientation & Inscription
Prochaines sessions de formation
Filtres :
| Centre de formation |
Semestre
2023/2024 |
Jours de formation |
Modalité | Crédits | ||
|---|---|---|---|---|---|---|
| Paris | Semestre 2 | 6 crédits (1) | ||||
|
Date de début des cours (*) :
* Les dates fournies sont d'ordre général à toutes les formations. |
||||||
-
-
Paris
Semestre 2
Cours en ligne
-
Légende :
| Tarif (1) : |
|---|
|
Vous pouvez consulter nos tarifs ici. |
| Date de début de cours : |
Les dates fournies sont d'ordre général à toutes les formations. Les cours pour cette formation peuvent potentiellement commencer un peu plus tard dans le semestre. |
| Annuel : |
|
Il s'étend de fin septembre / début octobre à début juillet (dates indicatives, renseignez-vous auprès de votre centre). |
| Semestre 1 : |
|
Il s'étend de fin septembre / début octobre à fin janvier / début février (dates indicatives, renseignez-vous auprès de votre centre). |
| Semestre 2 : |
|
Il s'étend de fin février / début mars à début juillet (dates indicatives, renseignez-vous auprès de votre centre). |
| Cours du soir : | |
|---|---|
|
Les cours commencent le plus souvent à 18h30 dans les centres. |
|
| Cours en journée : | |
|
Se renseigner auprès du centre pour connaître les horaires. |
|
| Cours en ligne : | |
|
les cours sont diffusés sous forme de séances numériques via une plateforme d’e-learning animées et tutorées par un enseignant. Des séances de regroupement en visio sont proposées. |
|
| Classe virtuelle : | |
|
L'enseignant à distance intervient en direct et en visioconférence sur la plateforme d'e-learning. Il complète son intervention par des activités interactives (exercices échanges…) |
|
| Cours en ligne hybride : | |
|
Cette modalité associe des cours en ligne tutorées et des regroupements en présentiel obligatoires. |
|
| Cours hybrides : | |
|
Cette modalité mixe des cours en présentiel (en cours du soir ou en journée) et des cours en ligne. |
|
| Cours en ligne organisés par un autre centre CNAM Régional : |
|
|
Les cours sont diffusés sous forme de séances numériques via une plateforme d'e-learning animées et tutorées par un enseignant. |
