Algorithmique des graphes

Informations

Langue d'enseignement : Français
Crédits ECTS: 6

Programme

  • Heures d'enseignement dispensées à l'étudiant : 48 heures
  • Temps de travail personnel : 102 heures

Objectifs et compétences

Objectifs :
L'objectif principal portera sur la représentation de graphes et la résolution de problèmes sur cette structure de données.

L'étudiant devra mettre en oeuvre des compétences d'abstraction, de calcul et de preuve de complexité et de mise en oeuvre d'algorithmes adaptés.

Cet enseignement abordera les notions générales relatives à la définition des graphes (e.g., sommet, arête, arc, chaîne, chemin, cycle, circuit, connexité, connectivité, orientation, ...), à leur représentations en machine (i.e., sous formes de listes ou matrices). Les complexités des fonctions élémentaires sur les graphes en fonction de la représentation choisie seront présentées. L'enseignement comprendra également les parcours dans les graphes (i.e., parcours en profondeur et en largeur) et leurs applications (composantes connexes, fortement connexes, tri topologique, graphes bipartis, ...), les algorithmes résolvant le problème du plus-courts chemins (i.e., algorithmes de Bellman, Ford, Dijkstra, Floyd-Warshall), les problématiques de caractérisations, reconnaissance, et détection d'arbre couvrant de poids minimum ainsi que celles relatives aux flots (i.e., calculs de flot maximum, coupe minimum).

Organisation pédagogique

le mode de fonctionnement de l'UE est présenté au début des enseignements

Contrôle des connaissances

La première session est constituée

> d'une note de contrôle continu (coef. 0.5)

> d'une note d'examen écrit terminal (1h30) (coef. 0.5)

pour l'obtention d'une note = 0.5*Examen écrit terminal + 0.5*Contrôle continu

La seconde session est constituée

> du report de la note de session 1 de contrôle continu

> d'une note d'examen écrit terminal (1h30)

pour l'obtention d'une note finale = 0.5*Examen écrit terminal + 0.5*max(Contrôle continu, Examen écrit terminal)

En seconde session, si l'effectif est faible un oral pourra être proposé.

Lectures recommandées

l'ensemble des références bibliographiques est communiqué au début des enseignements

Responsable de l'unité d'enseignement

- Non défini -

Enseignants

la composition de l'ensemble de l'équipe pédagogique est communiquée au début des enseignements