Prepas.org

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

Télécom ParisTech Algorithmes de tri et chemins dans les graphes (cours) du Lundi 18 mai 2015 au Mardi 19 mai 2015

Lundi 18 et mardi 19 mai 2015 Inscription en ligne : http://www.telecom-paristech.fr/liesse/inscri-algorithmes/
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).
Lieu : Télécom ParisTech, 46, rue Barrault, 75013 Paris.
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