Stage LIESSE


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 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

Programme sur deux jours : Plus courts et plus longs chemins dans les graphes orientés


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)
  

dernière modification 17-juin-2014