Stage LIESSE
|
|
Chemins dans les graphes
|
N.B.: Ces
descriptif et programme sont
donnés à
titre indicatif et peuvent évoluer.
Table des
matières
Nouveautés
- 17/06/13 : vos avis nous intéressent : le bilan complet du stage disponible en ligne ici. MERCI à tous !
- 12/05/14 : 26+22=48 inscrits au total; les inscriptions sont closes.
- 14/04/14 : 39 inscrits au total
- 07/04/14 : 22 inscrits pour la session approfondie. Nous vous attendons plus nombreux!
- 27/03/14 : 17 inscrits pour la session d'une journée, les inscriptions sont closes.
- 03/03/14 : 9 + 14 inscrits. Nous vous attendons plus nombreux!
- 24/01/14 : ouverture des inscriptions.
- 20/01/14 : création de cette fiche.
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 mathématiques supérieures et
spéciales, 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 (comment
venir?).
Les
exposés et
pauses sont en amphithéâtre Saphir. Le
déjeuner a lieu au restaurant administratif de Télécom ParisTech.
Le cocktail de clôture est en salle des conseils.
- Volume
horaire et programmation
: voir ci-dessous
- 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 : maintenue
par Télécom ParisTech
- Seuil
d'ouverture / Numerus clausus : 5 / 50
- Inscription
(libre mais obligatoire) : Inscription de préférence en ligne : session d'un jour - session de deux jours ; ou
par
mél à liesse@telecom-paristech.fr
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.
Programme sur
une journée : Plus courts chemins dans les graphes orientés pondérés positivement
- Matin
- 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
- Après-midi
- 13h30
- 16h30 : Codages des graphes : matrice d'adjacence, matrice des
poids, listes d'adjacence. Algorithme de Dijkstra : principe,
complexité, preuve, variations.
- 16h30 : Clôture
Programme sur deux jours : Plus courts et plus longs chemins dans les graphes orientés
- J1 Matin
- 9h30 - 9h45 : Accueil (Hall Barrault)
- 9h45 - 10h00 : Présentation du stage
- 10h00 - 12h30 : Introduction à l'algorithmique et à la complexité des problèmes.
- 12h30 Déjeuner
- J1 Après-midi
- 13h30
- 17h00 : Introduction aux graphes orientés.
- J2 Matin
- 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
- J2 Après-midi
- 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 : Clôture
Documents
Bilan
d'évaluation
Voici la synthèse des avis
recueillis à
la fin du stage (note sur 20 dans chaque catégorie), avec quelques
commentaires écrits par les stagiaires.
(33 fiches)
- Contenu de la formation (18,7/20) :
excellent stage, contenu fort apprécié, tout m'a semblé important,
contenu cohérent, objectifs atteints, programme largement réalisé,
présentation de l'algorithme de Dykstra a été le point essentiel,
approche intéressante de la complexité.
- Pédagogie du
cours (19,2/20) : tout
était très bien, qualité et implication de l'intervenant remarquables,
MERCI, très bonne expertise et pédagogie de l'intervenant, présence
d'un polycopié appréciée, exposés vivants et passionnants, un peu lent
la première 1/2 journée.
- Qualité des
échanges (19,4/20) : excellente,
très fructueux et font tout l'intérêt de ce stage, disponibilité
permanente et patiente de l'intervenant vis-à-vis des remarques.
- Organisation
et logistique (17,2/20) : très
bien, support en ligne apprécié, bon accueil pour certains, moins bon
pour d'autres, manque d'aide auprès de l'intervenant à l'accueil.
- Utilité du
stage par rapport à vos attentes (18,5/20) : compréhension
approfondie des techniques mises en oeuvre, préparer le programme de
l'informatique pour tous de 2ème année de CPGE, enseignement dans le
cadre de l'option informatique en MP et peut-être des TIPE de
mathématiques, beaucoup d'idées pédagogiques.
dernière
modification 17-juin-2014