Nature UE
Crédits ECTS 3
Volume horaire total 20
Volume horaire CM 20

Pré-requis

UE Complexité

Objectifs

Algorithmique des graphes ; notion de complexité paramétrée; résolution de problèmes par la programmation dynamique ; théorie structurelle des graphes par la largeur arborescente.

PT招财进宝

Ce cours présente les graphes et quelques paramètres classiques sur les graphes. Il présente aussi quelques familles de graphes et des algorithmes polynomiaux pour ces familles, pour des problèmes réputés difficiles.

Une deuxième partie introduira la mesure de complexité largeur arborescente et quelques techniques de programmation dynamique, avec mesure de la complexité en temps et espace dépendant de la largeur arborescente. On introduira à cet effet la complexité paramétrée ainsi que la notion de mineurs.

Une dernière partie présentera l’utilisation des graphes pour représenter des données.

Appartient à

Informations complémentaires

Algorithmique des graphes ; notion de complexité paramétrée; résolution de problèmes par la programmation dynamique ; théorie structurelle des graphes par la largeur arborescente.