Stage LIESSE


Algorithmes de tri et chemins dans les graphes

Research / Recherche Cours / Teaching Livres / Books CPGE / UPS / LIESSE Divers / More

N.B.: Ces descriptif et programme sont donnés à titre indicatif et peuvent évoluer.

Table des matières


Nouveautés


Informations générales



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 :


Documents



 

dernière modification 12-mai-2015