Graphes et optimisation (NFA010)


Les inscriptions pour l'année 2011-2012 sont closes.

Tarif formation

72 € l'unité d'enseignement.
* Hors frais de dossier annuel.



Code UE
NFA010 		Graphes et optimisation Crédits
6 		Enseignant:
Coordonnées du
centre de


Public concerné et conditions d’accès

Cours de début de premier cycle.

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.

Capacité et compétences acquises

Aptitude à formuler et modéliser un problème
Connaissance d'algorithmes fondamentaux sur les graphes.

Contenu de la formation

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)

Moyens et supports pédagogiques spécifiques
Support utilisé : Plateforme CNAM (via Plei@d)
Inscriptions
Modalités administratives d'inscription FOD Auditeurs Franciliens Cliquez ici
Auditeurs hors Ile de France Contactez votre centre régional
Modalités d'évaluation
Consultez http://formation-paris.cnam.fr
Planning de la formation
Début de la formation
Fin de la formation
Regroupements : Consultez http://formation-paris.cnam.fr
Lieux des regroupements : Cnam Paris
1ère session d'examen
2ème session d'examen (rattrapage)
Moyens de communication utilisés
Tutorat : Collectif et individuel
Communication avec le tuteur Asynchrone( messagerie, fax, courrier, forums) et synchrone(chat, visioconférence)
Outils nécessaires et configuration:
- Ordinateur (type) et Logiciels
Ordinateur type PC Windows / MacOS + haut-parleurs + connexion à  internet (ADSL) + Firefox, Internet explorer 7, 8

Consultez le programme national ici