Aller au menu Aller au contenu
Une voie, plusieurs choix
Informatique et Mathématiques appliquées
Une voie, plusieurs choix

> Formation > Cursus ingénieur

Graphes et applications - mise à niveau - 4MMGAMN

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

    • CM : 9.0
    • TD : 9.0
    Crédits ECTS : 1.5

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 Wojciech BIENIA

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 :


N1=E1
N2=E2

Informations complémentaires

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

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

mise à jour le 15 janvier 2017

Grenoble INP Institut d'ingénierie Univ. Grenoble Alpes