Ingénieur Polytech LilleCycle préparatoire (PeiP)Cycle IngénieurMécanique Génie Informatique et Statistique GéoTechnique Génie Civil Génie Biologique et Alimentaire Ingénieur d’Exploitation des Systèmes de Production Informatique Microélectronique Automatique Ingénierie et Commercialisation des systèMes de Mesure Matériaux

---

Mastère spécialisé en Génie de l'EauProfessionnels intervenantsEtudes bibliographiquesStages en entrepriseDébouchés

---

Formations hébergées à l'école

Admissions

   

Semestre 6
  UE 6-2 - Fondements Informatiques 2 (112920)
    Graphes et combinatoire (112310)

Enseignant(s) : Clarisse DHAENENS

ECTS : 1.25

Objectifs à atteindre

En Cours /TD :
_Savoir modéliser un problème de la vie courante à l’aide de graphes et reconnaître le problème à résoudre_
Maîtriser les principaux algorithmes de résolution pour les problèmes classiques
Acquérir des notions de complexité
Introduction des aspects de dualité
En TP (sur machine) savoir :
_Transposer un problème en un problème de graphe_
Le représenter de façon informatique pour pouvoir le traiter
Le résoudre à l’aide d’algorithmes vus en cours

Programme détaillé

Ordonnancement simple, PERT
Problème du flot maximal (Algo de Bellman-Ford, Th de la coupe min)
En TP :
Mise en œuvre d’algorithmes classiques de graphes (algorithmes de parcours, plus court chemin, ordonnancement PERT, algorithme de flot, …)

Pré-requis

Cours de base d’algorithmique et de structures de données
Cours de graphes et combinatoire du S1

Volume horaire

Total :	20h
Cours :	8h
TD :	8h
TP :	4h
Tutorat :	0h
DS :	1h

Bibliographie

M. Sakarovitch, « Optimisation combinatoire, vol 2, programmation discrète », Edition Hermann, ISBN 2 7056 5976 5, 1984.

---