NFA010

Graphes et optimisation


6 crédits Agnès PLATEAU-ALFANDARI EPN05 - Informatique Unité d'enseignement de type cours

Publié Du 01-09-2007 au 31-08-9999

Prérequis

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) .

Objectifs pédagogiques

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.

Compétences

Aptitude à formuler et modéliser un problème.

Connaissance d'algorithmes fondamentaux sur les graphes.

 

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, 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, de DIJKSTRA. Application : ordonnancements de projets (méthodes MPM).

Flots maximaux dans un réseau de transport : l'algorithme de FORD-FULKERSON.

Arbres couvrants de poids extrémal : algorithmes de KRUSKAL, de PRIM.
 

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.

(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).
 

Modalités de validation

  • Examen final

Description des modalités de validation

Le professeur, responsable national pour cette U.E., procède à la vérification et à la validation des sujets d'examen proposés par les CRA.

Bibliographie

TitreAuteur(s)
Précis de recherche opérationnelle (Dunod).5ème édition.R. FAURE, B. LEMAIRE, C. PICOULEAU
Programmation linéaire, algorithme du simplexe, Polycopié CNAM (en ligne).B. LEMAIRE
Exercices et problèmes résolus de R.O., T1 : Graphes, T3 : Programmation Linéaire (Masson).Groupe ROSEAUX
Polycopié de sujets de travaux dirigés (TD) : (en ligne)B. LEMAIRE

Thésaurus du Cnam :

  • Programmation linéaire
  • Structure de données
  • Recherche opérationnelle
  • Optimisation dans les graphes

Thésaurus Formacode :

  • Aucune indexation

Secrétariat

Libellé
EPN05 - Informatique
Nom du contact
Swathi Rajaselvam
Adresses email
swathi.ranganadin@cnam.fr
Numéros de téléphone
01 40 27 22 58
Adresse postale
2 rue Conté
Paris 75003

Personnes impliquées nationalement

  • Cédric BENTZ