Conservatoire national des arts et métiers

Je recherche une formation

Le Cnam le plus proche
Bordeaux Perigueux Agen Dax Mont-de-marsan Anglet Pau Poitiers Angoulême La Rochelle Chatellerault Limoges Brive Gueret
Être contacté
Tous les champs sont obligatoires
Etre rappelé sous 48h ouvrées
Votre demande concerne :
Projet de formation
Financement de formation
Validation des acquis
Autre
Précisez votre demande:
Vous souhaitez recevoir notre newsletter ?

Graphes et optimisation

Informatique et TIC


Code de l'UE : NFA010
Crédit ects : 6
Nb d'heures de formation : 51


 


Prérequis :

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


Objectifs :

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.


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.



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

Secrétariat : Mme Ranganadin , bureau 33-1-10B ; Tel 01 40 27 22 67
email : secretariat.ro@cnam. fr


Modalité 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 :

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.


Affiner les résultats par lieu d'enseignement

Angoulême, Bordeaux, Brive, Côte Basque, Guéret, La Rochelle, Limoges, Niort, Pau, Poitiers

Résultat(s) précis [+]

Lieu
d'enseignement
Informations
session 2019/2020
2019
2020
2020
2021
2021
2022
Tous centres
Formation à distance
1
Formation à distance
1
Formation à distance
1
Tous centres
Formation à distance
2
Formation à distance
2
Formation à distance
2

Tarifs (hors droit de base) :
Enseignement à distance : 1020 € (tarif réduit* : 120 €)


(*) Le tarif réduit s'applique aux formations pour lesquelles vous n'avez pu faire valoir de dispositif(s) de prise en charge (par votre employeur ou par un organisme paritaire collecteur agréé). Dans ce cas, vous y souscrivez à titre individuel et vous bénéficiez de l'aide du Conseil Régional d'Aquitaine.

Cnam Nouvelle-Aquitaine
16 cours de la Marne Bordeaux Nouvelle-Aquitaine 33800