University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Lyna Semcheddine |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Un nouvel algorithme auto-stabilisant pour une Coloration `a distance-2 Type de document : document électronique Auteurs : Rayane Lababsa, Auteur ; Lyna Semcheddine, Auteur ; Guellati,Nabil, Directeur de thèse Editeur : Sétif:UFA1 Année de publication : 2024 Importance : 1 vol (43 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Auto-stabilisation
Coloration des graphes
Coloration `a distance-2
Vitesse de convergence
Nombre de couleursIndex. décimale : 004 Informatique Résumé :
Un syst`eme r´eparti est une architecture informatique qui permet `a plusieurs ordinateurs
autonomes de travailler ensemble pour r´esoudre un probl`eme complexe en communiquant
entre eux via un r´eseau de communication. L’auto-stabilisation permet `a ces
syst`emes de r´ecup´erer automatiquement un ´etat correct, mˆeme si un ou plusieurs de
ses composants tombent en panne ou sont perturb´es sans d´ependre d’une intervention
ext´erieure.
La coloration des graphes est une m´ethode qui vise `a attribuer des couleurs distinctes
aux sommets d’un graphe, en respectant des crit`eres pr´ecis, tels que la non-adjacence
de sommets de mˆeme couleur. Il en existe deux types : la coloration `a distance-1, et `a
distance-2 .La coloration `a distance-2 est notre sujet principal, qui vise `a attribuer des
couleurs diff´erentes aux voisins directes et indirectes d’un sommet diff´erentes aux voisins
directes et indirectes d’un sommet.
Dans ce m´emoire nous avons r´ealis´e un algorithme auto-stabilisant pour une coloration `a
distance-2, nous l’avons compar´e avec deux autres algorithmes : ” l’Algorithme de Tixeuil
” et ” l’algorithme de coloration ´evidente ” . En conclusion , notre algorithme est meilleur
que l’algorithme de coloration ´evidente en termes de nombre minimale de couleur, tandis
que l’algorithme de Tixeuil est l´eg`erement meilleur en termes de vitesse de convergence.Note de contenu : Sommaire
Liste des acronymes 1
List des Figures i
Introduction G´en´erale 1
1 G´en´eralit´es 4
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Les syst`emes r´epartis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Taxonomie des pannes dans les syst`emes repartis . . . . . . . . . . . . . . 6
1.3.1 Les pannes d’´etats . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2 Les pannes de code . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Les graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 L’Auto stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 L’algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.1 Exemple d’ex´ecution . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 ´Etat de l’art 15
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 La coloration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 D´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2 D´efis et complexit´e . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.3 Approches de la coloration des graphes . . . . . . . . . . . . . . . 16
2.2.4 Programmation enti`ere z´ero-un . . . . . . . . . . . . . . . . . . . 16
2.2.5 Applications concr`etes de la coloration de graphes . . . . . . . . . 17
2.3 Coloration `a distance-1 et `a distance-2 . . . . . . . . . . . . . . . . . . . . 18
2.4 Nombre chromatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 La coloration propre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6 La sous-couche MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7 Gestion des collisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.8 Algorithmes r´epartis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8.1 D´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.9 Travaux li´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Contribution 25
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Rappel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.1 D´efinition de la coloration `a distance-2 . . . . . . . . . . . . . . . . 25
3.3 Hypoth`eses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.1 D´emon centralis´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.2 La communication par m´emoire partag´ee . . . . . . . . . . . . . . 25
3.4 Description du fonctionnement de l’algorithme . . . . . . . . . . . . . . . 26
3.4.1 L’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.5 Biographie de LUKASZ KUSZNER . . . . . . . . . . . . . . . . . . . . . 28
3.6 L’application KUSZNER . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.7 Pr´esentation des fonctions du code source . . . . . . . . . . . . . . . . . . 29
3.8 Les interfaces de l’application . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.9 R´esultats de la simulation des algorithmes . . . . . . . . . . . . . . . . . . 37
3.9.1 En termes de vitesse de convergence . . . . . . . . . . . . . . . . . 37
3.9.2 En termes de nombres de couleurs . . . . . . . . . . . . . . . . . . 37Côte titre : MAI/0933 Un nouvel algorithme auto-stabilisant pour une Coloration `a distance-2 [document électronique] / Rayane Lababsa, Auteur ; Lyna Semcheddine, Auteur ; Guellati,Nabil, Directeur de thèse . - [S.l.] : Sétif:UFA1, 2024 . - 1 vol (43 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Auto-stabilisation
Coloration des graphes
Coloration `a distance-2
Vitesse de convergence
Nombre de couleursIndex. décimale : 004 Informatique Résumé :
Un syst`eme r´eparti est une architecture informatique qui permet `a plusieurs ordinateurs
autonomes de travailler ensemble pour r´esoudre un probl`eme complexe en communiquant
entre eux via un r´eseau de communication. L’auto-stabilisation permet `a ces
syst`emes de r´ecup´erer automatiquement un ´etat correct, mˆeme si un ou plusieurs de
ses composants tombent en panne ou sont perturb´es sans d´ependre d’une intervention
ext´erieure.
La coloration des graphes est une m´ethode qui vise `a attribuer des couleurs distinctes
aux sommets d’un graphe, en respectant des crit`eres pr´ecis, tels que la non-adjacence
de sommets de mˆeme couleur. Il en existe deux types : la coloration `a distance-1, et `a
distance-2 .La coloration `a distance-2 est notre sujet principal, qui vise `a attribuer des
couleurs diff´erentes aux voisins directes et indirectes d’un sommet diff´erentes aux voisins
directes et indirectes d’un sommet.
Dans ce m´emoire nous avons r´ealis´e un algorithme auto-stabilisant pour une coloration `a
distance-2, nous l’avons compar´e avec deux autres algorithmes : ” l’Algorithme de Tixeuil
” et ” l’algorithme de coloration ´evidente ” . En conclusion , notre algorithme est meilleur
que l’algorithme de coloration ´evidente en termes de nombre minimale de couleur, tandis
que l’algorithme de Tixeuil est l´eg`erement meilleur en termes de vitesse de convergence.Note de contenu : Sommaire
Liste des acronymes 1
List des Figures i
Introduction G´en´erale 1
1 G´en´eralit´es 4
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Les syst`emes r´epartis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Taxonomie des pannes dans les syst`emes repartis . . . . . . . . . . . . . . 6
1.3.1 Les pannes d’´etats . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2 Les pannes de code . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Les graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 L’Auto stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 L’algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.1 Exemple d’ex´ecution . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 ´Etat de l’art 15
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 La coloration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 D´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2 D´efis et complexit´e . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.3 Approches de la coloration des graphes . . . . . . . . . . . . . . . 16
2.2.4 Programmation enti`ere z´ero-un . . . . . . . . . . . . . . . . . . . 16
2.2.5 Applications concr`etes de la coloration de graphes . . . . . . . . . 17
2.3 Coloration `a distance-1 et `a distance-2 . . . . . . . . . . . . . . . . . . . . 18
2.4 Nombre chromatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 La coloration propre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6 La sous-couche MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7 Gestion des collisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.8 Algorithmes r´epartis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8.1 D´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.9 Travaux li´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Contribution 25
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Rappel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.1 D´efinition de la coloration `a distance-2 . . . . . . . . . . . . . . . . 25
3.3 Hypoth`eses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.1 D´emon centralis´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.2 La communication par m´emoire partag´ee . . . . . . . . . . . . . . 25
3.4 Description du fonctionnement de l’algorithme . . . . . . . . . . . . . . . 26
3.4.1 L’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.5 Biographie de LUKASZ KUSZNER . . . . . . . . . . . . . . . . . . . . . 28
3.6 L’application KUSZNER . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.7 Pr´esentation des fonctions du code source . . . . . . . . . . . . . . . . . . 29
3.8 Les interfaces de l’application . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.9 R´esultats de la simulation des algorithmes . . . . . . . . . . . . . . . . . . 37
3.9.1 En termes de vitesse de convergence . . . . . . . . . . . . . . . . . 37
3.9.2 En termes de nombres de couleurs . . . . . . . . . . . . . . . . . . 37Côte titre : MAI/0933 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0933 MAI/0933 Mémoire Bibliothéque des sciences Français Disponible
Disponible
