Stage LIESSE
|
|
Algorithmes de tri et chemins dans les graphes
|
N.B.: Ces
descriptif et programme sont
donnés à
titre indicatif et peuvent évoluer.
Table des
matières
Nouveautés
- 11/05/15 : 21 inscrits. Les inscriptions sont closes, merci de votre compréhension.
- 03/04/15 : 14 inscrits.
- 03/03/15 : 10 inscrits.
- 29/01/15 : 5 inscrits.
- 03/12/14 : création de cette fiche.
Informations
générales
- Thème
: Algorithmes de tri et plus courts chemins dans les graphes orientés
- Dates de la session : Lundi 18 et mardi 19 mai 2015
- Type de stage : Cours (pas de séance de travaux pratiques prévue pour cette formation).
- 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).
Inscription libre
mais obligatoire, voir ci-dessous.
- Lieu
: Télécom ParisTech, 46, rue Barrault, 75013 Paris (comment
venir?).
- 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 ici ou
par
mél à liesse@telecom-paristech.fr
Synopsis
Ce cours
présente plusieurs algorithmes de tri ainsi que 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. Quelques structures de données classiques.
3. Résultats théoriques sur la complexité des algorithmes de tri.
4. Algorithmes de tri.
5. Introduction aux graphes orientés.
6. Codages des graphes : matrice d'adjacence, matrice des poids, listes d'adjacence.
7. Algorithme de Dijkstra pour des graphes pondérés positivement : principe, complexité, preuve, variations.
Au-delà de la spécification de ces algorithmes, on mettra l'accent sur
les différences de complexité (au sens de la complexité algorithmique)
existant entre ces algorithmes. On verra comment on peut parfois (tri
rapide) améliorer la complexité d'un algorithme. Si le temps le permet, on pourra aborder é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.
NB: il n'y a pas de séance de travaux pratiques prévue pour cette formation.
Programme :
- J1 Matin
- 9h30 - 9h45 : Accueil (Hall Barrault)
- 9h45 - 10h00 : Présentation du stage
- 10h00 - 12h30 : Introduction à l'algorithmique et à la complexité des
problèmes. Quelques structures de données classiques.
- 12h30 Déjeuner
- J1 Après-midi
- 13h30
- 17h00 : Résultats théoriques sur la complexité des algorithmes
de tri. Algorithmes de tri classiques : tri par sélection, tri par
insertion, tri rapide, tri par fusion.
- J2 Matin
- 9h30
- 12h30 : Introduction aux graphes orientés.
- 12h30 : Déjeuner
- J2 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
Documents
dernière
modification 12-mai-2015