]
]
]
]
Cours 2012
IHDC B321 - Théorie des graphes et réseaux de Pétri
Enseignant(s)
X.
Encadrement des TP/Exercices
Objectifs
Développer l'aptitude mathématique dans le cadre de l'algorithmique liée à la théorie des graphes et dans la modélisation du comportement dynamique de systèmes discrets (Réseaux de Pétri).
Ce cours introduit à l'analyse de la complexité théorique des algorithmes et à quelques modèles de la Recherche Opérationnelle.
L'intérêt du cours réside dans l'énorme potentiel de modélisation constitué par les graphes.
Contenu
I. Théorie des graphes :
Définitions, Représentations et concepts de base
Cheminements, Accessibilité, Parcours, Connexité
Décomposition en niveaux
Chemins extrémaux
Problèmes de l'ordonnancement (PERT et MPM )
Procédure de séparation et d'évaluation progressive (Branch and Bound)
Arbre maximal
II. Réseaux de Pétri :
Exemples d'application
Formalisation
Analyse des réseaux et de leurs propriétés
Donné en
Année(s) d'études |
Quadrimestre |
Théorie (h) |
Exercices (h) |
Crédits |
|
|---|---|---|---|---|---|
|
3e année de bachelier en sciences informatiques (horaire décalé) |
1er |
45 |
15 |
8 |
|
|
Année préparatoire au 2e cycle en sciences informatiques à horaire décalé |
1er |
45 |
15 |
8 |
|
Table des matières
I. Théorie des graphes :
- Introduction : Définitions, Représentations et concepts de base,Concepts dérivés et généralisation ;
- Représentation informatique, Complexité;
- Chemins, Accessibilité, Parcours, Connexité forte et simple;
- Graphes sans circuit : décomposition en niveaux, Applications pratiques
- Chemins extrémaux des graphes pondérés, Typologie des problèmes, principaux algorithmes, problèmes dérivés
- Applications des chemins extrémaux, problèmes de l'ordonnancement (PERT et MPM )
- Procédure de séparation et d'évaluation progressive (Branch and Bound), recherche du circuit hamiltonien de poids minimum et problèmes dérivés, résultats théoriques sur les cheminements d'Euler de de Hamilton
- Arbre maximal
II. Réseaux de Pétri :
- Exemples d'application
- Formalisation
- Analyse des réseaux et de leur propriétés
Méthode d'enseignement
Pédagogie : un syllabus complet est fourni aux étudiants en début d'année.
Des applications pratiques telles la méthode Electre en aide à la décision, le tracé automatiques de graphes, les problèmes d'ordonnancement sont intégrés aux exposés théoriques afin d'illustrer le caractère concret de la matière.
Evaluation
Modalites d'interrogation aux examens :
- en 1ère session, l'examen est écrit, il comporte des questions de théorie et des exercices. Il est vivement conseillé de passer cet examen en janvier.
- en 2ème session, l'examen est identique à celui de la 1ère.
Evaluation de la charge de travail pendant l'année académique :
- une heure de cours devrait correspondre, en moyenne, à deux heures de travail personnel au total (c'est à dire en ce compris le travail en blocus).
Prérequis
L'étudiant qui aborde ce cours devrait avoir des notions élémentaires de calcul matriciel : les opérations sur les matrices, les notations indicées.
Le cours IHDC B121 est une référence utile de mise à niveau.
Lectures recommandées
Se référer au syllabus
