Aller au menu Aller au contenu
Diversité scientifique et technologique
L'école d'ingénieurs de physique, électronique, matériaux
Diversité scientifique et technologique

> Formation

Graphes et applications - mise à niveau - 4PMIGAP1

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In
  • Volumes horaires

    • CM : 0
    • TD : 18.0
    • TP : 0
    • Projet : 0
    • Stage : 0
    • DS : -
    Crédits ECTS : 1.5
  • Responsables : Wojciech BIENIA

Objectifs

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

Contenu

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ôles 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 (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) :
Documents interdits (ex : livres, tous documents) :
Matériel (ex : calculatrices):

  • matériel autorisé, préciser :
  • matériel interdit, préciser :
  • Commentaires :

SESSION DE RATTRAPAGE :
Type d'examen (écrit, oral, examen sur machine) :
Salle spécifique :
Durée :
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) :
Documents interdits (ex : livres, tous documents) :
Matériel (ex : calculatrices):

  • matériel autorisé, préciser :
  • matériel interdit, préciser :
  • Commentaires :


    • MCC en présentiel **
      N1=E1 (examen écrit)
      N2=E2 (examen écrit)

MCC en distanciel
N1 = DM
N2 = DM

Calendrier

Le cours est programmé dans ces filières :

  • Cursus ingénieur - Filière SEOC - Semestre 7
cf. l'emploi du temps 2020/2021

Informations complémentaires

Cursus ingénieur->Filières->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

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In

mise à jour le 30 juin 2020

Université Grenoble Alpes