Prepas.org

Le site de l'UPS pour les Classes Préparatoires aux Grandes Écoles

Télécom ParisTech Chemin dans les graphes du Lundi 19 mai 2014 au Mardi 20 mai 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(lien externe)
Seuil d'ouverture / Numerus clausus : 5 / 50
Inscription (libre mais obligatoire) : Inscription de préférence en ligne


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