Graphes
Parcours : DU Cursus master ingénierie (CMI) - Informatique, image, réalité virtuelle, interactions et jeux

  • Cours (CM) 20h
  • Cours intégrés (CI) -
  • Travaux dirigés (TD) 14h
  • Travaux pratiques (TP) -
  • Travail étudiant (TE) -

Langue de l'enseignement : Français

Niveau de l'enseignement : B2-Avancé - Utilisateur indépendant

Description du contenu de l'enseignement

Cette UE présente les propriétés mathématiques fondamentales des graphes, et analyse les principaux algorithmes sur ceux-ci. Programme :
Graphes orientés et non-orientés : adjacence, degrés, voisinages ; chaînes, chemins, cycles et circuits ; composantes (fortement) connexes ; graphes eulériens ; arbres et arborescences. Algorithmes sur les graphes : parcours en largeur et en profondeur, tri topologique, composantes fortement connexes ; arbres couvrants minimum ; recherche de plus courts chemins ; réseaux de transports et recherche de flots maximaux. Couplages dans les graphes bipartis, applications.

Compétences à acquérir

À l'issue de cette UE une étudiante devrait savoir :
- les propriétés fondamentales des graphes et des arbres ;
- exprimer des problèmes dans le langage des graphes ;
- pratiquer les algorithmes sur les graphes.

Bibliographie, lectures recommandées

Références :
C. Berge : Graphes, 2e édition, Dunod, 1973.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein : Introduction to Algorithms, PHI Learning, 2010. Traduction française : Algorithmique. Dunod, 2010.

Pré-requis obligatoires

À l'entrée de cette UE, une étudiante devrait :
- connaître les rudiments de mathématiques discrètes (cf. PSC en S4) ;
- pratiquer la programmation impérative, choisir les structures de données appropriées et connaître l'algorithmique de base (cf. SDA1 en S3 et SDA2 en S4).

Contact

UFR de Mathématique et Informatique

7 RUE RENE DESCARTES
67084 STRASBOURG
0368850123

Responsable

Christian Ronse


Parcours : DU Cursus master ingénierie (CMI) - Informatique, image, réalité virtuelle, interactions et jeux