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 couleurs
Index. 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 . . . . . . . . . . . . . . . . . . 37
Cô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 couleurs
Index. 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 . . . . . . . . . . . . . . . . . . 37
Côte titre :	MAI/0933