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.
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) .
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
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.
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).
Cette UE apparaît dans les diplômes et certificats suivants :
Date de début de cours : |
---|
Les dates fournies sont d'ordre général à toutes les formations. Les cours pour cette formation peuvent potentiellement commencer un peu plus tard dans le semestre. |
Tarif : |
Seul le financement à titre individuel est proposé à l'inscription en ligne. Si vous souhaitez financer votre formation par votre entreprise, vous devez demander un devis auprès de nos centres Tarifs en vigueur depuis le 17 juin 2020. |
Annuel : |
Il s'étend de fin septembre / début octobre à début juillet (dates indicatives, renseignez-vous auprès de votre centre). |
Semestre 1 : |
Il s'étend de fin septembre / début octobre à fin janvier / début février (dates indicatives, renseignez-vous auprès de votre centre). |
Semestre 2 : |
Il s'étend de fin février / début mars à début juillet (dates indicatives, renseignez-vous auprès de votre centre). |
Cours du soir : | |
---|---|
Les cours commencent le plus souvent à 18h30 dans les centres. |
|
Cours en journée : | |
Se renseigner auprès du centre pour connaître les horaires. |
|
Cours en ligne : | |
Les cours sont diffusés sous forme de séances numériques via une plateforme d'e-learning animées et tutorées par un enseignant. Des regroupements peuvent être proposés dont certains sont obligatoires. |
|
Classe virtuelle : | |
L'enseignant à distance intervient en direct et en visioconférence sur la plateforme d'e-learning. Il complète son intervention par des activités interactives (exercices échanges…) |
|
Cours en ligne hybride : | |
Cette modalité propose une majorité de cours en ligne tuteurés et des regroupements en présentiel obligatoires. |
|
Cours hybrides : | |
Cette modalité mixe des cours en présentiel (en cours du soir ou en journée) et des cours en ligne. |
|
Cours en ligne organisés par un autre centre CNAM Régional : |
|
Les cours sont diffusés sous forme de séances numériques via une plateforme d'e-learning animées et tutorées par un enseignant. |