Formation indisponible à l'heure actuelle
Graphes et Optimisation
Formation
A distance
Avez-vous besoin d'un coach de formation?
Il vous aidera à comparer différents cours et à trouver la solution la plus abordable.
Description
-
Typologie
Formation
-
Méthodologie
A distance
-
Heures de classe
60h
-
Envoi de matériel d'apprentissage
Oui
Objectifs: Apprendre comment modéliser des problèmes notamment d'optimisation, issus de l'informatique et de la recherche opérationnelle, comment les résoudre à l'aide d'un algorithme et d'une structure de données appropriés.
À propos de cette formation
Cours de début de premier cycle.
Les Avis
Le programme
Théorie des graphes et algorithmes de base
Introduction: vocabulaire et concepts de base (connexité, forte connexité, mise en ordre). Nombre cyclomatique, arbres et arborescences.
Représentations des graphes: matricielles (adjacence, incidence). listes (successeurs, prédécesseurs).
Les graphes en tant qu'outil de modélisation. exemples en informatique et en R. O.
Parcours des graphes: en largeur. en profondeur. applications. détermination des composantes connexes, etc.
Fermeture transitive. détermination, méthode matricielle: algorithme de ROY-WARSHALL. parcours en profondeur (cas d'un graphe sans circuit).
initiation à la complexité dans le cas polynômial. évaluation du nombre d'opérations.
Algorithmes d'optimisation dans les graphes valués
Chemins optimaux dans un graphe valué: algorithmes de FORD, de DIJKSTRA. Application: ordonnancements de projets (méthodes MPM et PERT).
Flots maximaux dans un réseau de transport: l'algorithme de FORD-FULKERSON (exemple. preuve. complexité).
Arbres couvrants de poids extrémal: algorithmes de KRUSKAL, de PRIM et de SOLLIN.
Programmes de transport (heuristiques et notion de "regret". algorithme du stepping-stone).
Problèmes d'affectation: la méthode hongroise (lien avec les flots maximaux).
Recherches arborescentes: en profondeur d'abord (Pb des reines sur l'échiquier). Branch and Bound: résolution du problème du voyageur de commerce (TSP) par l'algorithme de LITTLE et al.
Programmation linéaire
Définition, historique. panorama des applications industrielles, performances et rentabilité. Approche géométrique. caractérisation géométrique du cheminement vers le sommet optimum. Caractérisation algébrique d'un sommet. Méthode algébrique du simplexe. méthode des tableaux (en se limitant au cas où le sommet 0 est admissible).
(Un approfondissement de ces concepts de base et des algorithmes associés fait l'objet d' U. V. des cycles probatoire puis d'approfondissement).
Avez-vous besoin d'un coach de formation?
Il vous aidera à comparer différents cours et à trouver la solution la plus abordable.
Graphes et Optimisation