NFA010 | Graphes et optimisation

Programme

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

Objectifs : aptitudes et compétences

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 :

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

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

Délais d'accès

Le délai d'accès à la formation correspond à la durée entre votre inscription et la date du premier cours de votre formation.

• UE du 1er semestre et UE annuelle : inscription entre mai et octobre
• UE du 2e semestre : inscription de mai jusqu'à mi-mars

Exemple : Je m'inscris le 21 juin à FPG003 (Projet personnel et professionnel : auto-orientation pédagogique). Le premier cours a lieu le 21 octobre. Le délai d'accès est donc de 4 mois.

Planning

Modalités

Modalités pédagogiques :

Pédagogie qui combine apports académiques, études de cas basées sur des pratiques professionnelles et expérience des élèves. Équipe pédagogique constituée pour partie de professionnels. Un espace numérique de formation (ENF) est utilisé tout au long du cursus.

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.

Tarif

Plusieurs dispositifs de financement sont possibles en fonction de votre statut et peuvent financer jusqu'à 100% de votre formation.

Salarié : Faites financer votre formation par votre employeur

Demandeur d’emploi : Faites financer votre formation par Pôle emploi

Votre formation est éligible au CPF ? Financez-la avec votre CPF

Si aucun dispositif de financement ne peut être mobilisé, nous proposons à l’élève une prise en charge partielle de la Région Nouvelle-Aquitaine avec un reste à charge. Ce reste à charge correspond au tarif réduit et est à destination des salariés ou demandeurs d’emploi.

Pour plus de renseignements, consultez la page Financer mon projet formationopen_in_new ou contactez nos conseillers pour vous accompagner pas à pas dans vos démarches.

Cette unité d'enseignement n'est valorisable que dans cette certification.

Avis des auditeurs

Les dernières réponses à l'enquête d'appréciation de cet enseignement :

Fiche synthétique au format PDF

Taux de réussite

Les dernières informations concernant le taux de réussite des unités d’enseignement composant les diplômes

Taux de réussite