IT3004

Graphes et Algorithmes

Date mise à jour : 11/02/2013

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 h

Horaire 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