JDN > Formations professionnelles > Conception et Développement > Langages > Formation Graphes et optimisation (NFA010)




Formation Graphes et optimisation (NFA010)Informations pratiquesCentre de formation CNAM CERGY-PONTOISE

 Formation Graphes et optimisation (NFA010)


 CNAM CERGY-PONTOISE, Cergy-Pontoise
 Formation à distance


Objectif Objectifs pédagogiques :
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.

Contenu Contenu de la formation
Les problèmes combinatoires : généralités, difficultés.
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).

Coût 160 euros (Les tarifs Ile de France sont subventionnés par le Conseil régional d'Ile de France.)
Durée de la formation 4 mois

 

Mise à jour le 08 Novembre 2006 
Mettre à jour | Envoyer cette fiche 


Rechercher
> Recherche avancée
> Toutes les formations
> Top des recherches
0-9|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z


Les informations contenues dans l'Annuaire des formations sont communiquées par les établissements concernés. Elles n'engagent en rien la responsabilité de l'éditeur du Journal du Net. © Benchmark Group


Rechercher une formation
Recherche avancée | Toutes les formations
Top des recherches


ENST Telecom Paris formation continue et professionnelle – Cegos
CNFCE ORSYS
Journal du Net Voir un exemple
Management Voir un exemple
Emploi Voir un exemple
Toutes nos newsletters

Annonces Google