Soutenance mémoire
Problème de gestion des examens
Application à l’Organisation des examens
Depuis quelques années le problème de la gestion des examens dans les universités est devenu un problème pour les organisateurs, Vu l’augmentation de nombre de modules à la FST de Fès et vu les réformes pédagogiques qui permettent aux étudiants de s’inscrire dans des modules suivant leurs choix, et vu la capacité des locaux de la FST qui est limité.Le problème de la gestion des examens est devenu un problème pour les organisateurs,Dans ce chapitre nous proposons une méthode d’organisation des examens en utilisant la coloration des graphes plus précisément nous proposons une modélisation du problème sous forme d’un graphe non orienté dans les sommets sont les examens, deux sommets i, j sont adjacents dans le graphe si les examens i et j ont des étudiants en commun. Nous assignons une couleur à chaque sommet de tel sorte que deux sommets adjaçants n’aient pas la même couleur. L’objectif est de minimiser le nombre de jours d’organisation des examens qui correspond à minimiser le nombre de couleur du graphe.
Représentation matricielle
Pour résoudre le problème d’organisation des examens en utilisant la coloration des graphes, nous proposons une modélisation sous forme d’une matrice carré symétrique contient 0 et 1, 1 si i et j sont deux modules de même spécialité où s’ils ont au moins un étudiant réserve en commun et 0 sinon avec i,j = {1,……………,32}
Étapes de résolution
Pour colorier un graphe nous proposons une présentation sous forme d’une matrice symétrique qui contient 0 et 1, à partir de cette matrice nous proposons un programme qui permet de colorier tous les sommets du graphe en déterminant à chaque fois un ensemble indépendant qui nous donne une couleur.
Les étapes de l’exécution :
étape1 : Initialisation de l’ensemble indépendant par le sommet M1
étape2 : Chercher le premier sommet j non adjacent avec le sommet de l’ensemble puis l’ajouter a notre ensemble
étape3 : Chercher un sommet j qui n’est adjacent avec aucun sommet de l’ensemble indépendant, si tous les sommets restant sont adjacents avec au mois un sommet de l’ensemble indépendant, on passe à l’étape d, sinon on répète cette dernière
étape4 : donner une couleur à cet ensemble puis barrer en ligne et en colonne tous les sommets sélectionnés dans l’ensemble
étape5 : Revenir à l’étape1 jusqu’à ce que tous les sommets des graphes soient coloriés
On note par L notre ensemble indépendant, qui est jusqu’à maintenant L={1} .Puis on cherche le premier sommet non adjacent avec le sommet « 1 », c’est-à-dire on cherche le premier 0 dans la ligne qui correspond au sommet « 1 », dans ce cas c’est le sommet « 3 », donc L devient L= {1,3}.
Puis on cherche un autre sommet, qui ne doit être adjacent avec aucun sommet de L, dans ce cas il n’existe pas, donc on va donner à cet ensemble la couleur 1.
|
Guide du mémoire de fin d’études avec la catégorie Théorie de graphe et optimisation combinatoire |
|
Étudiant en université, dans une école supérieur ou d’ingénieur, et que vous cherchez des ressources pédagogiques entièrement gratuites, il est jamais trop tard pour commencer à apprendre et consulter une liste des projets proposées cette année, vous trouverez ici des centaines de rapports pfe spécialement conçu pour vous aider à rédiger votre rapport de stage, vous prouvez les télécharger librement en divers formats (DOC, RAR, PDF).. Tout ce que vous devez faire est de télécharger le pfe et ouvrir le fichier PDF ou DOC. Ce rapport complet, pour aider les autres étudiants dans leurs propres travaux, est classé dans la catégorie Coloration des graphes où vous pouvez trouver aussi quelques autres mémoires de fin d’études similaires.
|
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
Télécharger le rapport complet
