Télécom ParisTech Chemin dans les graphes le Jeudi 03 avril 2014

Synopsis

Ce cours présente des algorithmes permettant de déterminer des plus courts chemins dans les graphes orientés. Il est composé des parties suivantes :

1. Introduction à l'algorithmique et à la complexité des problèmes.

2. Introduction aux graphes orientés.

3. Codages des graphes : matrice d'adjacence, matrice des poids, listes d'adjacence.

4. Algorithme de Dijkstra pour des graphes pondérés positivement : principe, complexité, preuve, variations.

Dans la session approfondie, on abordera également les liens entre plus courts chemins et plus longs chemins; l'algorithme de Bellman (programmation dynamique) pour des graphes sans circuit, et l'algorithme matriciel dans le cas général. Au-delà de la spécification de ces algorithmes, on indiquera comment on peut étendre ces algorithmes pour résoudre des problèmes proches (par exemple prise en compte de deux valuations). On verra aussi comment le choix approprié d'une structure de données permet de réduire la complexité algorithmique dans certains cas.

Informations générales

Thème : Plus courts chemins dans les graphes orientés

Dates des sessions :

''* Session d'une journée : jeudi 3 avril 2014'' - cette session peut être combinée à celle sur les algorithmes de tris du mercredi 2 avril (s'inscrire aux deux sessions)

''* Session (plus approfondie) de deux jours : lundi 19 et mardi 20 mai 2014''

Type de stage : Cours

Auditoire attendu : les professeurs de CPGE 1ère et 2ème années, en mathématiques, physique, chimie, informatique et sciences de l'ingénieur.

Pré-requis : rudiments de programmation (variables, boucles).

Sont également invités, plus généralement, les enseignants ou enseignants-chercheurs intéressés de l'enseignement secondaire ou supérieur (inscription libre mais obligatoire, voir ci-dessous).

Lieu : Télécom ParisTech, 46, rue Barrault, 75013 Paris

Les exposés et pauses sont en amphithéâtre. Le déjeuner a lieu au restaurant administratif de Télécom ParisTech. Le cocktail de clôture est en salle des conseils.

Responsable pédagogique : Olivier Hudry

Contact : liesse@telecom-paristech.fr

Intervenants : Olivier Hudry, enseignant-chercheur au département InfRes de Télécom ParisTech.

Page Web de présentation : ici

Seuil d'ouverture / Numerus clausus : 5 / 50

Inscription (libre mais obligatoire) : Inscription de préférence en ligne

Pour le 3 avril : ici

Pour les 19 et 20 mai : ici

ou par mél à liesse@telecom-paristech.fr

Programme sur une journée : Plus courts chemins dans les graphes orientés pondérés positivement

Jeudi 3 avril

9h30 - 9h45 : Accueil (Hall Barrault)

9h45 - 10h00 : Présentation du stage

10h00 - 12h30 : Introduction à l'algorithmique et à la complexité des problèmes. Introduction aux graphes orientés.

12h30 Déjeuner

13h30 - 16h30 : Codages des graphes : matrice d'adjacence, matrice des poids, listes d'adjacence. Algorithme de Dijkstra : principe, complexité, preuve, variations.

16h30 : Cocktail de clôture

Programme sur deux jours : Plus courts et plus longs chemins dans les graphes orientés

Lundi 19 mai

9h30 - 9h45 : Accueil (Hall Barrault)

9h45 - 10h : Présentation du stage

10h - 12h30 : Introduction à l'algorithmique et à la complexité des problèmes.

12h30 Déjeuner

13h30 - 17h : Introduction aux graphes orientés.

Mardi 20 mai

9h30 - 12h30 : Codages des graphes : matrice d'adjacence, matrice des poids, listes d'adjacence. Liens entre plus courts chemins et plus longs chemins.

12h30 : Déjeuner

13h30 - 16h30 : Algorithme de Dijkstra pour des graphes pondérés positivement, algorithme de Bellman (programmation dynamique) pour des graphes sans circuit, algorithme matriciel dans le cas général.

16h30 : Cocktail de clôture