Appuyer sur Entrée pour chercher ou la touche ESC pour fermer

NFA010 | Graphes et optimisation

schedule

51

Total d'heures d'enseignement
school

6

Crédits ECTS
date_range

Date non définie

Début des cours prévu

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

Inscription 1er semestre et annuel :

  • Modalité présentiel/hybride : de juillet à mi-octobre
  • Modalité FOAD (100% à distance) : de juillet à mi-novembre

Inscription 2ème semestre :

  • Modalité présentiel/hybride : de juillet à mi-février
  • Modalité FOAD (100% à distance) : de juillet à mi-mars

Planning

Légende:
Cours en présentiel
Cours 100% à distance
Mixte: cours en présentiel et à distance

Certaines unités d'enseignement nécessitent des prérequis. Cliquez sur le titre de l'UE ci-dessus pour en savoir plus.

Centre de formation 2022/2023 Prochaine session* Modalité Tarif
individuel
100% à distance Semestre 2 Date non définie De 0 à 1.020 € shopping_cart Ajouter au panier
*Selon les UEs, il est possible de s'inscrire après le début des cours. Votre demande sera étudiée pour finaliser votre inscription.

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

Mon employeur finance Pôle Emploi finance Je finance avec le co-financement Région
1.020 € 510 € Salarié : 156 € Demandeur d'emploi : 124,80 €

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

Si vous êtes demandeur d'emploi et que vous cotisez à AG2R La Mondiale, vous pouvez bénéficier d'un financement : 4 UE gratuites par an.

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 indiqué ci-dessus et est à destination des salariés ou demandeurs d’emploi.

Pour plus de renseignements, nous vous invitons à consulter notre guide du financement et à contacter 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

Besoin d'aide dans vos démarches ?

L'équipe du Cnam Nouvelle-Aquitaine est là pour vous aider