Volumes horaires
- CM 0
- Projet 0
- TD 18.0
- Stage 0
- TP 0
- DS -
Crédits ECTS
Crédits ECTS 1.5
Objectif(s)
1° permettre aux étudiants de se familiariser avec les graphes, qui sont un outil essentiel de l’optimisation combinatoire avec de nombreuses applications à divers problèmes dans les réseaux, et qui apparaîtront dans d’autres cours. L’accent sera mis sur la modélisation et sur l’existence de résultats généraux et de diverses méthodes de résolution.
2° apprendre comment modéliser certains problèmes susceptibles d'être résolus par des méthodes d’Optimisation Combinatoire et de proposer une introduction aux concepts de base de la Recherche Opérationnelle.
Contact Moritz MUHLENTHALER Responsable(s)
Wojciech BIENIA
Contenu(s)
1- Exploration, composantes connexes, arbres, arbre couvrant (réseaux LAN, ou algorithmes de configuration de réseau dynamique)
2 - Chemins, flots, et connectivité, flot maximum et coupe minimum (acheminement), connexité (résistance aux pannes des réseaux), problèmes de chemins arcs disjoints (affectation de trafic).
3 - Compatibilité, conflits, domination : couplage et affectation (affectation de clients a des ressources), coloration (routage dans les réseaux optiques), absorbant (positionnement de concentrateurs dans un réseau)
4 - Autres problèmes divers : cycle eulérien, cycle hamiltonien; diffusion (broadcasting et gossiping), localisation et implantation, capacité de Shannon d’un graphe.
5 - Introduction aux ordonnancements.
Prérequis
Aucun, mais a priori, un élève doit pouvoir suivre le raisonnement formel avec un certain niveau d’abstraction.
Contrôle des connaissances
CONTRÔLE CONTINU :
Type d'évaluation (ex : TP, assiduité, participation) :
SESSION NORMALE :
Type d'examen (écrit, oral, examen sur machine) : examen écrit
Salle spécifique :
Durée : 2h
Documents autorisés : résumé feuille A4 manuscrite (recto-verso)
Documents interdits :
Matériel (ex : calculatrices):
- matériel autorisé, préciser :
- matériel interdit, préciser : calculatrices, ordinateurs, portables, tablettes
- Commentaires :
SESSION DE RATTRAPAGE :
Type d'examen (écrit, oral, examen sur machine) :
Salle spécifique :
Durée :
Documents autorisés : résumé feuille A4 manuscrite (recto-verso)
Documents interdits :
Matériel (ex : calculatrices):
- matériel autorisé, préciser :
- matériel interdit, préciser : calculatrices, ordinateurs, portables, tablettes
- Commentaires :
- MCC en présentiel **
N1=E1 (examen écrit)
N2=E2 (examen écrit)
- MCC en présentiel **
MCC en distanciel
N1 = DM
N2 = DM
Calendrier
Le cours est programmé dans ces filières :
- Cursus ingénieur - Filière SEOC - Semestre 7
Bibliographie
W. BIENIA : "Introduction à la recherche opérationnelle et optimisation combinatoire", polycopié 2007
V. CHVATAL : "Linear programming", W.H. Freeman Company, 1983
G. FINKE at al : “Recherche Opérationnelle et réseaux” traité IGAT, HERMES, 2002
M. SAKAROVITCH : "Optimisation combinatoire vol.I et II", Hermann, 1984
N.H. XUONG : "Mathématiques discrètes et informatique", Masson, 1992.
I. Charon, A. Germa, O. Hudry, Méthodes d’Optimisation Combinatoire, Collection Pédagogique de Télécommunication, Masson, Paris, 1996
M. Gondran, M. Minoux, Graphes et Algorithmes (2ème ed. revue et augmentée). Eyrolles, Paris, 1985.
J.A. Bondy, U.S.R. Murty, Graph Theory with Applications. North-Holland, 1981.
A. Gibbons, Algorithmic Graph Theory.Cambridge University Press, 1988