JDN > Formations professionnelles > Administration, support et système > Informatique Industrielle > Formation Graphes et optimisation




Formation Graphes et optimisationInformations pratiquesCentre de formation ARCNAM

 Formation Graphes et optimisation


 ARCNAM, PARIS
 Formation à distance


Objectif Se familiariser avec des modeles classiques de problemes d'optimisation. 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.
Contenu 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 (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é des algorithmes dans le cas polynômial par l'évaluation du nombre d'opérations élémentaires. 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. Programmes de transport solution de base et arbre associé ; heuristiques d'obtention de solutions de base, notion de "regret" et heuristique de BALAS-HAMMER ; optimisation : algorithme du "stepping-stone". Recherches arborescentes : en profondeur d'abord (Pb des reines sur l'échiquier) ; Branch and Bound : résolution du problème du knap-sack (sac-à-dos) en variables binaires. Programmation linéaire : Définition, historique ; panorama des applications industrielles, performances et rentabilité. Approche géométrique de l'optimum (sommet) ; 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. E. de niveau au moins égal à BAC+3)
Niveau requis Cours de premier cycle. Il est conseillé d'avoir suivi ( ou de suivre en parallèle) les 2 UE de "Mathematiques pour l'informatique" (MVA 003 et MVA 004) .
Coût 60 euros (Coût par UE)
Durée de la formation 4 mois

 

Mise à jour le 06 Septembre 2007 
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