Ressource pédagogique : Cours d´algorithmique des graphes du MPRI

Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

Dans de nombreux domaines tels que la chimie, la biologie, les réseaux de télécommunications ou encore les réseaux sociaux des modèles à base de graphes sont utilisés quotidiennement en recherche. De même les graphes constituent des outils importants et très utilisés de modélisation en informatique. Pour s'en convaincre il sufit de considérer la place faite aux algorithmes sur les graphes dans les ouvrages classiques d'algorithmique. En effet malgré la simplicité apparente de leur définition, les graphes capturent une large part de la complexité algorithmique. Il est donc très important de bien comprendre la structure des graphes afin d'utiliser des modélisations pertinentes à base de graphes. Ce module a deux objectifs principaux : le premier concerne la compréhension de la complexité structurelle des graphes via des décompositions de graphes et les invariants de graphes associés, tandis que le deuxième est centré sur la conception d'algorithmes "efficaces" sur les graphes et l'étude des outils algorithmiques nécessaires.

• Granularité : cours
• Structure : linéaire

"Domaine(s)" et indice(s) Dewey

• Algorithms (518.1)
• Graph theory (511.5 )

Thème(s)

Informations pédagogiques

• Activité induite : apprendre
• Commentaires pédagogiques : Ces notes ont été prises à l'occasion des cours d'algorithmique des graphes du Master Parisien de Recherche en Informatique en 2006/2007, donnés par Michel Habib (8 séances de 90 minutes)