Accueil UnitésGraphes et optimisation
NFA010

U.E Graphes et optimisation

nombre d’heures
51
Modalités 100% à distance
Crédits ects
6

Où se
former?

1 Centre d’enseignement en Nouvelle-Aquitaine

Quand se former ?

Rentrée
Permanente !
voir toutes les dates

Votre projet professionnel commence ici !

Formez-vous avec

Dites-nous tout sur votre projet !

Choisissez une session de formation

Centres de formation :
Modalités d’enseignement : 100% à distance Mixte : à distance + cours en salle Présentiel
Centres de formation Prochaines sessions Modalités Informations
Session 2021/2022
Centres de formation Prochaines sessions Modalités Informations
Nouvelle-Aquitaine Octobre 2021
Février 2022

1er semestre
NFA010-2021-1-FN-NA

Pas d'information disponible

Nouvelle-Aquitaine Février 2022
Juin 2022

2nd semestre
NFA010-2021-2-FN-NA

Pas d'information disponible

Session 2022/2023
Centres de formation Prochaines sessions Modalités Informations
Nouvelle-Aquitaine Octobre 2022
Février 2023

1er semestre
NFA010-2022-1-FN-NA

Pas d'information disponible

Nouvelle-Aquitaine Février 2023
Juin 2023

2nd semestre
NFA010-2022-2-FN-NA

Pas d'information disponible

Voir ma liste de formation
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 d'optimisation.

Connaissance d'algorithmes fondamentaux sur les graphes.

Utilisation de structures de données fondamentales : tableau, file et pile

Nous contacter

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

Nous contacter

Agenda

Choisissez une session de formation

Centres de formation
Modalités d’enseignement : 100% à distance Mixte : à distance + cours en salle Présentiel
  • Session 2020/2021

    Pas d'Unité d'Enseignement pour cette session

  • Session 2021/2022

  • Session 2022/2023

Présentation

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 d'optimisation.

Connaissance d'algorithmes fondamentaux sur les graphes.

Utilisation de structures de données fondamentales : tableau, file et pile

Nous contacter

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

Nous contacter
Tarif indicatif
1 020

Mobilisez les financements auxquels vous avez droit !

Votre entreprise

finance

1 020

Vous payez

0

Pôle Emploi



finance

510

Vous payez

0

Votre CPF

Compte Personnel de Formation

finance

1 020

Vous payez

0

Le Conseil Régional

finance

Vous payez

156 (1)

AG2R (2)
La Mondiale

finance
700

/module (4 modules maximum/an)

Vous payez

0
(1) -20% pour les demandeurs d'emploi (2) Dispositif réservé aux adhérents demandeurs d'emploi

Besoin de plus d’information sur les dispositifs de financement ?

Demandez l’aide
d’un conseiller
Cnam Nouvelle-Aquitaine

Valorisez votre formation avec un diplôme !

CPN9000A-1
Titre RNCP Niveau 5 (ex niveau III) Technicien développeur
CPN9000A-2
Titre RNCP Niveau 5 (ex niveau III) Technicien développeur
CPN9000A-3
Titre RNCP Niveau 5 (ex niveau III) Technicien développeur
Appuyer sur Entrée pour chercher ou la touche ESC pour fermer
    top