Graphes Et Applications Mise Agrave Niveau 4mmgamn 388397

7/25/2019 Graphes Et Applications Mise Agrave Niveau 4mmgamn 388397

1/3

Graphes et applications - Mise niveau -

4MMGAMN

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 problmes dans les rseaux, et qui apparatront dans

d'autres cours. L'accent sera mis sur la modlisation et sur l'existence de rsultats gnraux et de diverses

mthodes de rsolution.

2 apprendre comment modliser certains problmes susceptibles d'tre rsolus par des mthodes

d'Optimisation Combinatoire et de proposer une introduction aux concepts de base de la Recherche

Oprationnelle.

Wojciech BIENIAContact

Contenu

1- Exploration, composantes connexes, arbres, arbre couvrant (rseaux LAN, ou algorithmes de configuration

de rseau dynamique)

2 - Chemins, flots, et connectivit, flot maximum et coupe minimum (acheminement), connexit (rsistanceaux pannes des rseaux), problmes de chemins arcs disjoints (affectation de trafic).

3 - Compatibilit, conflits, domination : couplage et affectation (affectation de clients a des ressources),

coloration (routage dans les rseaux optiques), absorbant (positionnement de concentrateurs dans un

rseau)

4 - Autres problmes divers : cycle eulrien, cycle hamiltonien; diffusion (broadcasting et gossiping),

localisation et implantation, capacit de Shannon d'un graphe.

5 - Introduction aux ordonnancements.

Prrequis

Aucun, mais a priori, un lve doit pouvoir suivre le raisonnement formel avec un certain niveau d'abstraction.

L'COLE FORMATION RECHERCHE INTERNATIONALENTREPRISESVIE

TUDIANTE

Volumes horaires

CM : 9.0

TD : 9.0

: 1.5Crdits ECTS

Page 1
http://ensimag.grenoble-inp.fr/l-ecole/?RH=ENSIMAG-01_Presenthttp://ensimag.grenoble-inp.fr/formation/?RH=ENSIMAG-02_Formationhttp://ensimag.grenoble-inp.fr/recherche/?RH=ENSIMAG-03_Recherchehttp://ensimag.grenoble-inp.fr/international/?RH=ENSIMAG-04_Internatihttp://ensimag.grenoble-inp.fr/entreprises/?RH=ENSIMAG-05_Entreprishttp://ensimag.grenoble-inp.fr/vie-etudiante/?RH=ENSIMAG-06_Vieetudiahttp://ensimag.grenoble-inp.fr/vie-etudiante/?RH=ENSIMAG-06_Vieetudiahttp://ensimag.grenoble-inp.fr/vie-etudiante/?RH=ENSIMAG-06_Vieetudiahttp://ensimag.grenoble-inp.fr/entreprises/?RH=ENSIMAG-05_Entreprishttp://ensimag.grenoble-inp.fr/international/?RH=ENSIMAG-04_Internatihttp://ensimag.grenoble-inp.fr/recherche/?RH=ENSIMAG-03_Recherchehttp://ensimag.grenoble-inp.fr/formation/?RH=ENSIMAG-02_Formationhttp://ensimag.grenoble-inp.fr/l-ecole/?RH=ENSIMAG-01_Present


2/3

Contrles des connaissances

CONTRLE CONTINU :

Type d'valuation (ex : TP, assiduit, participation) :

SESSION NORMALE :Type d'examen (crit, oral, examen sur machine) : examen crit

Salle spcifique :

Dure : 2h

Documents autoriss (ex : aucun, rsum feuille A4 manuscrite, dictionnaires, tous documents) :

Documents interdits (ex : livres, tous documents) :

Matriel (ex : calculatrices):

matriel autoris, prciser :

matriel interdit, prciser :Commentaires :

SESSION DE RATTRAPAGE :

Type d'examen (crit, oral, examen sur machine) :

Salle spcifique :

Dure :

Documents autoriss (ex : aucun, rsum feuille A4 manuscrite, dictionnaires, tous documents) :

Documents interdits (ex : livres, tous documents) :

Matriel (ex : calculatrices):

matriel autoris, prciser :

matriel interdit, prciser :

Commentaires :

N1=E1

N2=E2

Informations complmentairesListe des cours

-> ->Semestre 3Cursus ingnieur Filire ISSC

-> ->Semestre 3Cursus ingnieur Filire SLE

->Equipe Algorithmique-Mathmatiques discrtes

Bibliographie

W. BIENIA : "Introduction la recherche oprationnelle et optimisation combinatoire", polycopi 2007

V. CHVATAL : "Linear programming", W.H. Freeman Company, 1983

G. FINKE at al : "Recherche Oprationnelle et rseaux" trait IGAT, HERMES, 2002

Page 2
http://ensimag.grenoble-inp.fr/cursus-ingenieur/liste-des-cours-version-francaise-385937.kjsp?RH=IMA_Enseignementshttp://ensimag.grenoble-inp.fr/http://ensimag.grenoble-inp.fr/cursus-ingenieur/cursus-ingenieur-ensimag-142047.kjsp?RH=IMA_Enseignementshttp://ensimag.grenoble-inp.fr/cursus-ingenieur/systemes-et-logiciels-embarques-124724.kjsp?RH=IMA_Enseignementshttp://ensimag.grenoble-inp.fr/cursus-ingenieur/equipes-p-eacute-dagogiques-version-fran-ccedil-aise-386498.kjsp?RH=IMA_Enseignementshttp://ensimag.grenoble-inp.fr/cursus-ingenieur/algorithmique-mathematiques-discretes-386488.kjsp?RH=IMA_Enseignementshttp://ensimag.grenoble-inp.fr/cursus-ingenieur/algorithmique-mathematiques-discretes-386488.kjsp?RH=IMA_Enseignementshttp://ensimag.grenoble-inp.fr/cursus-ingenieur/equipes-p-eacute-dagogiques-version-fran-ccedil-aise-386498.kjsp?RH=IMA_Enseignementshttp://ensimag.grenoble-inp.fr/cursus-ingenieur/systemes-et-logiciels-embarques-124724.kjsp?RH=IMA_Enseignementshttp://ensimag.grenoble-inp.fr/cursus-ingenieur/cursus-ingenieur-ensimag-142047.kjsp?RH=IMA_Enseignementshttp://ensimag.grenoble-inp.fr/http://ensimag.grenoble-inp.fr/http://ensimag.grenoble-inp.fr/cursus-ingenieur/liste-des-cours-version-francaise-385937.kjsp?RH=IMA_Enseignements


3/3

M. SAKAROVITCH : "Optimisation combinatoire vol.I et II", Hermann, 1984

N.H. XUONG : "Mathmatiques discrtes et informatique", Masson, 1992.

I. Charon, A. Germa, O. Hudry, Mthodes d'Optimisation Combinatoire, Collection Pdagogique de

Tlcommunication, Masson, Paris, 1996

M. Gondran, M. Minoux, Graphes et Algorithmes (2me ed. revue et augmente). 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

ENGLISH VERSION

See english version for this page

cole nationale suprieure d'informatique et de mathmatiques appliques

681, rue de la passerelle - Domaine universitaire - BP 72

38402 SAINT MARTIN D'HERES

www.grenoble-inp.fr/suivez-nous

Afin d'amliorer la qualit de ce site et le service rendu l'utilisateur, nous utilisons des cookies de mesure

d'audience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies cette fin. Pour

en savoir plus

Page 3
http://ensimag.grenoble-inp.fr/cursus-ingenieur/graphs-and-applications-upgrade-4mmgamn-388398.kjsp?RH=IMA_Enseignementshttp://www.grenoble-inp.fr/suivez-noushttp://ensimag.grenoble-inp.fr/infos-legales/?RH=ENSIMAG_INFOSLEGALEShttp://ensimag.grenoble-inp.fr/infos-legales/?RH=ENSIMAG_INFOSLEGALEShttp://ensimag.grenoble-inp.fr/infos-legales/?RH=ENSIMAG_INFOSLEGALEShttp://ensimag.grenoble-inp.fr/infos-legales/?RH=ENSIMAG_INFOSLEGALEShttp://www.grenoble-inp.fr/suivez-noushttp://ensimag.grenoble-inp.fr/cursus-ingenieur/graphs-and-applications-upgrade-4mmgamn-388398.kjsp?RH=IMA_Enseignements