Vous êtes ici :

Discipline(s) : Informatique, Mathématiques, Sciences et technologies

UE1 - S5 : Algorithmique des Graphes | P.Sciences de l'Informatique

Semestre Semestre 5
Type Obligatoire
Nature UE
Volume horaire total 40h
Volume horaire CM 20h
Volume horaire TD 20h

Domaine(s) LMD

Informatique, Mathématiques - Informatique

Langue(s) d'enseignement

Français

Responsables

Objectifs

  • Modélisation de différentes situations complexes sous forme de graphes
  • Conception et Adaptation des algorithmes répondant aux problèmes exposés

Contenu

  1. Généralités sur les Graphes: notions, représentations, structures de données... 
  2. Composantes fortement connexes. 
  3. Le problème du plus court chemin.
  4. Algorithmes gourmands: algorithme de Prim et algorithme de Kruskal. 
  5. Le problème du flot maximum. 

Appartient à

Bibliographie

Graphes et algorithmes, Michel Gondran et Michel Minoux, Eyrolles, 1995

Contrôles des connaissances

Contrôle de connaissance en Continu/Projets.