Vous êtes ici :

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

UE1 - S5 : Algorithmique des Graphes | P.MIAGE

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 d'une situation sous forme de graphe
  • Identification d'un algorithme répondant à un problème posé.
  • Conception/Adaptation d'un algorithme selon les besoins. 
  • Manipulation de la structure de données graphes. 

Contenu

  1. Généralités sur les graphes: notions de bases, exemples, représentations. 
  2. Analyse des algorithmes: notions de complexité, du meilleur au pire cas. 
  3. Composantes fortement connexes.
  4. Problème du flot maximum.

Appartient à

Bibliographie

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

Contrôles des connaissances

Contrôle de connaissances Terminal.