Vous êtes ici

  1. Accueil
  2. Algorithmique des graphes

Algorithmique des graphes

Algorithmique des graphes

En pratique :

Volume horaire de cours : 24
Volume horaire global de TD : 12
Volume horaire global de TP : 12
Langue principale : français

Description du contenu de l'enseignement

Ce module présente les principaux algorithmes sur les graphes. Il commence par une présentation des multiples domaines d'application, des modèles de graphes et des différentes notions et terminologies sur les graphes. On étudie ensuite des algorithmes de parcours, de calcul de la fermeture transitive, de composantes fortement connexes, de plus courts chemins, les problèmes d'ordonnancement et de flots des réseaux de transport. Une part importante est accordée à l'analyse de la complexité des algorithmes. Un mini-projet permet de modéliser un problème réel sous la forme d'un graphe et d'apporter des solutions en utilisant des algorithmes étudiés.


Compétences à acquérir

A l'issue de ce module, les étudiants devraient être en mesure d’analyser des problèmes combinatoires réels, de déterminer si ces problèmes peuvent être modélisés par des graphes et d’identifier les algorithmes de graphes (en prenant en compte leurs complexités) - ou à défaut, de proposer des adaptations de ces algorithmes ou de concevoir de nouveaux algorithmes - qui permettent d’apporter des solutions à ces problèmes.concevoir de nouveaux algorithmes - qui permettent d’apporter des solutions à ces problèmes.


Bibliographie, lectures recommandées

  • Graphe et algorithmes, M. Goudran, M. Minoux, Ed. Lavoisier
  • Introduction à l’algorithme, T. Cormen, C. Leiserson, R. Rivest, C. Stein, Ed. Dunod
  • Exercices et problèmes résolus de recherche opérationnelle, Vol1.: Graphes : leurs usages, leurs algorithmes, Roseaux (Nom collectif), Ed. Dunod
  • Algorithmique des graphes, J.M Hélary, polycopié 66, Istic/Université de Rennes 1 Algorithmique des graphes, J.M Hélary, polycopié 66, Istic/Université de Rennes 1