Catalogue de formations à distance

Graphes et optimisation

CNAM de Paris, Conservatoire national des arts et métiers (Cnam Paris)

292 rue Saint-Martin
75141
PARIS Cedex 03
France

CNAM de Grand Est, Conservatoire national des arts et métiers (Cnam Grand Est)

4 rue du Dr Heydenreich CS 65228
54052
NANCY Cedex
France

CNAM de Paris, Conservatoire national des arts et métiers (Cnam Paris)

292 rue Saint-Martin
75141
PARIS Cedex 03
France

INSCRIPTION

Repère

Crédits ECTS
6
Formation
formation entièrement à distance
Diplôme
Autres formations du supérieur

Tarif

Dates

Partagez !

LOCALISATION

Régions(s) :
Île-de-France, Grand Est, Île-de-France
Académie(s) :
Paris, Nancy-Metz, Paris

CONTACT

Le Conservatoire National des Arts et Métiers
292, rue Saint-Martin
75003
Paris
http://www.cnam.fr
Description

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

Objectif

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.

Conditions d'admission

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

Public visé
  • Tout public

Critères de réferencement

Pour figurer dans le catalogue Sup-Numerique, les formations doivent être :

  • portées par des établissements d'enseignement supérieur français dûment identifiés par le M.E.S.R.I. au titre du service public (établissements publics d'Enseignement supérieur français, établissements publics ou privés qui proposent des formations dont les diplômes sont visés par le M.E.S.R.I.)
  • en partenariat avec :.
    • le Centre national d'enseignement à distance (CNED)
    • le Conservatoire national des arts et métiers (CNAM)
    • la Fédération interuniversitaire de l'enseignement à distance (FIED)

Contactez la FIED pour faire référencer vos formations à distance

Centre national d'enseignement à distance
Conservatoire national des arts et métiers
Fédération Interuniversitaire de l'Enseignement à Distance