ST-3001B Graphes et Algorithmes Date mise à jour : 7/11/2018
ESIEE  3e année   2ème semestre ESIEE  3e année S   2ème semestre ESIEE  3e année T   2ème semestre
Horaires : Horaire Cours : 20 hHoraire TD : 10 h
Crédits ECTS : 3
Langue(s) de l'unite enseignee : FRANCAIS
Responsable(s) : COUPRIE Michel (michel.couprie@esiee.fr)
Objectif(s) :
Cette introduction aux algorithmes les plus classiques de la théorie des graphes doit permettre de maîtriser les notions indispensables à la Reconnaissance des Formes, l'Intelligence Artificielle, l'Optimisation Combinatoire et la Résolution de Problèmes.
L'objectif est :
- d'être capable de formuler un problème en termes de graphe
- de savoir détecter si la résolution de ce problème se ramène à un algorithme connu
- si ce n'est pas le cas, d'être capable de proposer un nouvel algorithme en sachant évaluer sa complexité de calcul.
Pré-requis :
Programmation en langage évolué, algorithmique.

Themes Cours T.D
Notions de base. Rappel complexité de calcul 2h00
Chemins - composantes connexes - parcours Eulérien 2h00 2h00
Arbres. Arbres de poids maximum 4h00 2h00
Plus courts chemins 4h00 2h00
Graphes sans circuits 3h00 2h00
Réseau de transport - flot maximum 3h00 2h00

Nature de l'épreuve Commentaires Durée Coeff
Examen final 2 1

Bibliographie :

Documents de références
[1] T. Cormen, C. Leiserson, R. Rivest, Introduction à l'algorithme, Dunod ed., 1994
[2] M. Sakarovitch, Optimisation Combinatoire T1 : Programmation discrète (Chap 3), Hermann ed,
[3] M. Sakarovitch, Optimisation Combinatoire T2 : Graphes et Programmation linéaire (Chap. 2.3.4), Hermann ed,
[4] M. Gondran, M. Minoux, Graphes et Algorithmes, Eyrolles