Application à l’organisation des examens

Table des matières

Introduction générale
Chapitre 1 : Théorie de graphe et optimisation combinatoire
1.1 -Introduction
1.2 Généralités sur les graphes
1.2.1 Définitions et terminologie
1.2.2 Représentation d’un graphe
La seconde idée permettant une représentation matricielle d’un graphe exploite la relation d’incidence entre arêtes et sommets
1.3 L’optimisation combinatoire
1.3.1 Préliminaire
C’est l’ensemble des problèmes pour lesquels il existe un algorithme de résolution en un temps polynomiale
b)-La classe NP
1.3.2 Méthodes de résolution
Chapitre 2 : Problème de gestion des examens
6 2.1 Introduction
2.2 Problème d’emploi du temps des examens
2.3 Etat de l’art
Problèmes de l’université de Toronto
2.4 Problématique
2.5 Représentation des solutions
2.5.1 Représentation graphique
2.5.2 Représentation matricielle
Chapitre 3 : Coloration des graphes
3.1 Introduction
3.2 Coloration d’un graphe
3.2.1 Ensemble indépendant
3.2.2 Graphe complet
3.2.3 Nombre chromatique
3.3 Problème d’ensemble indépendant maximal
3.3.1 Relaxation
3.3.2 Relaxation Surrogate
3.3.3 Problème d’ensemble indépendant maximal
3.3.4 Formulation du problème d’ensemble indépendant maximal
3.3.5 Formulation Mathématique
3.3.6 Amélioration de la solution de la contrainte surrogate
3.3.7 Amélioration par une méthode basée sur le multiplicateur w de la contrainte surrogate
Chapitre 4 : Application à l’Organisation des examens d’un semestre à la FST de Fès
4.1 Introduction
4.2 Résolution du problème d’organisation des examens
4.2.1 Organisation des examens d’un semestre à la FST de Fès
4.2.2 Représentation matricielle
Conclusion générale
Bibliographie