University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Nabil Guellati |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la rechercheImplémentation d’un algorithme auto-stabilisant pour le calcul d’un ensemble indépendant(Algorithme Srimani) / Rebiha Rahma Bouima
Titre : Implémentation d’un algorithme auto-stabilisant pour le calcul d’un ensemble indépendant(Algorithme Srimani) Type de document : texte imprimé Auteurs : Rebiha Rahma Bouima, Auteur ; Keltoum Serradj ; Nabil Guellati, Directeur de thèse Editeur : Sétif:UFS Année de publication : 2023 Importance : 1 vol (48 f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Système répartie
Tolérance aux pannes
Auto-stabilisation
Clustering
Ensemble indépendant
Ensemble indépendant maximalIndex. décimale : 004 - Informatique Résumé : Un système distribué est constitué d’unités de calcul autonomes qui collaborent
pour atteindre un objectif commun. Il est important de prendre en compte la probabilité de panne de ces systèmes, et l’auto-stabilisation joue un rôle essentiel dans la
gestion de ces pannes. De plus, le clustering offre une solution pour réduire les coûts de
communication. Notre recherche se focalise sur l’implimentation d’un algorithme autostabilisant permettant de calculer un ensemble indépendant maximal dans un graphe
arbitraire =
A distributed system consists of autonomous computing units that collaborate to
achieve a common goal. It is important to consider the probability of failure in these systems, and self-stabilization plays a crucial role in managing such failures. Additionally,
clustering provides a solution to reduce communication costs. Our research focuses on
implementing a self-stabilizing algorithm to calculate a maximum independent set in
an arbitrary graph.Côte titre : MAI/0794
En ligne : https://drive.google.com/file/d/1cfCIVu_-9VflOCFcsS2noYnFM8YUUVZS/view?usp=drive [...] Format de la ressource électronique : Implémentation d’un algorithme auto-stabilisant pour le calcul d’un ensemble indépendant(Algorithme Srimani) [texte imprimé] / Rebiha Rahma Bouima, Auteur ; Keltoum Serradj ; Nabil Guellati, Directeur de thèse . - [S.l.] : Sétif:UFS, 2023 . - 1 vol (48 f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Système répartie
Tolérance aux pannes
Auto-stabilisation
Clustering
Ensemble indépendant
Ensemble indépendant maximalIndex. décimale : 004 - Informatique Résumé : Un système distribué est constitué d’unités de calcul autonomes qui collaborent
pour atteindre un objectif commun. Il est important de prendre en compte la probabilité de panne de ces systèmes, et l’auto-stabilisation joue un rôle essentiel dans la
gestion de ces pannes. De plus, le clustering offre une solution pour réduire les coûts de
communication. Notre recherche se focalise sur l’implimentation d’un algorithme autostabilisant permettant de calculer un ensemble indépendant maximal dans un graphe
arbitraire =
A distributed system consists of autonomous computing units that collaborate to
achieve a common goal. It is important to consider the probability of failure in these systems, and self-stabilization plays a crucial role in managing such failures. Additionally,
clustering provides a solution to reduce communication costs. Our research focuses on
implementing a self-stabilizing algorithm to calculate a maximum independent set in
an arbitrary graph.Côte titre : MAI/0794
En ligne : https://drive.google.com/file/d/1cfCIVu_-9VflOCFcsS2noYnFM8YUUVZS/view?usp=drive [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0794 MAI/0794 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Un nouvel algorithme auto-stabilisant pour le calcul d’un ensemble 1-isolé Type de document : document électronique Auteurs : Yousra Touahra, Auteur ; Imane Derradj, Auteur ; Nabil Guellati, Directeur de thèse Editeur : Sétif:UFA1 Année de publication : 2024 Importance : 1 vol (46 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Auto-stabilisation
Systèmes distribués
Algorithmes distribués
Ensembles indépendants
Ensembles 1-isolésIndex. décimale : 004 Informatique Résumé :
L’auto-stabilisation est une méthode permettant de gérer les pannes transitoires,
introduite par Dijkstra. Un système distribué est considéré comme auto-stabilisant s’il
est capable de revenir à un état correct après une période de temps fini, quel que soit
son état initial. Plusieurs problématiques observées dans les réseaux et les systèmes
distribués peuvent être modélisés à l’aide de graphes. Notre étude se concentre sur les
algorithmes distribués auto-stabilisants qui facilitent le calcul des ensembles indépendants
et dominants dans un graphe. Nous présentons un nouvel algorithme distribué
auto-stabilisant permettant de calculer un ensemble 1-isolé (TKD-1IS : 1-insulated set)
dans un graphe quelconque. Nous évaluons ses performances en simulant son comportement
dans un environnement à grande échelle. En outre, nous comparons notre
algorithme à d’autres algorithmes similaires de la littérature et discutons des résultats
obtenus, aussi nous présentons deux nouvelles versions de notre algorithme. Ce dernier
peut être utilisé pour organiser les ressources dans un système distribué et s’avère utile
pour regrouper des noeuds dans des réseaux (clustering).Note de contenu :
Sommaire
Introduction générale 1
1 Les systèmes distribués et l’auto-stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Les systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Exemples de systèmes distribués célèbres . . . . . . . . . . . . . 3
1.2.2 Les avantages des systemes distribués . . . . . . . . . . . . . . . 4
1.2.3 Les algorithmes distribués . . . . . . . . . . . . . . . . . . . . . 4
1.3 Les graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.2 Types de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Les pannes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 Les types de pannes . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.2 La tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . 6
1.5 L’auto-stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5.1 Définition : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5.2 Exemple d’algorithme auto-stabilisant . . . . . . . . . . . . . . 8
1.5.3 Les avantages de l’auto-stabilisation . . . . . . . . . . . . . . . 10
1.5.4 Les inconvénients de l’auto-stabilisation . . . . . . . . . . . . . 10
1.5.5 Les démons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5.6 Preuve d’auto-stabilisation . . . . . . . . . . . . . . . . . . . . 11
1.5.6.1 Preuve de Correction . . . . . . . . . . . . . . . . . . . 11
1.5.6.2 Preuve de Convergence . . . . . . . . . . . . . . . . . 11
1.5.7 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.7.1 Complexité en espace : . . . . . . . . . . . . . . . . . . 11
1.5.7.2 Complexité en temps . . . . . . . . . . . . . . . . . . 11
1.6 Définitions formelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Algorithmes d’ensembles indépendants 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Les ensembles dominants . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2 Les ensembles indépendants . . . . . . . . . . . . . . . . . . . . 14
2.2.3 Les ensembles k-isolés . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.4 Les ensembles 1-isolés . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.2 Les avantages du clustering . . . . . . . . . . . . . . . . . . . . 16
2.3.3 Usage des ensembles indépendants dans le clustering . . . . . . 17
2.4 L’état de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.1 Algorithme de Hedetniemi . . . . . . . . . . . . . . . . . . . . . 18
2.4.2 Algorithme de Turau . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.3 Algorithme de Shukla . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4.4 Algorithme de Srimani . . . . . . . . . . . . . . . . . . . . . . . 22
2.4.5 Algorithme de Naggazi . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.6 Algorithme de Michiyo . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.7 Récapitulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5 Autres références . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Un nouvel algorithme auto-stabilisant pour le calcul d’un ensemble
1-isolé (1-insulated set) 30
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 Hypothèses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Les règles de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Preuve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.6.1 Preuve de correction . . . . . . . . . . . . . . . . . . . . . . . . 33
3.6.2 Preuve de convergence . . . . . . . . . . . . . . . . . . . . . . . 33
3.7 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.8 Interface de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.9 Description du code de l’application de Kuszner (avec nos modifications) 37
3.10 Description de la première transformation (TKD_1IS_V2) . . . . . . . 41
3.11 Les règles de TKD_1IS_V2 . . . . . . . . . . . . . . . . . . . . . . . . 42
3.12 Description de la deuxième transformation (TKD_1IS_V3) . . . . . . . 43
3.13 Les règles de TKD_1IS_V3 . . . . . . . . . . . . . . . . . . . . . . . . 43
3.14 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Conclusion générale 44Côte titre : MAI/0943 Un nouvel algorithme auto-stabilisant pour le calcul d’un ensemble 1-isolé [document électronique] / Yousra Touahra, Auteur ; Imane Derradj, Auteur ; Nabil Guellati, Directeur de thèse . - [S.l.] : Sétif:UFA1, 2024 . - 1 vol (46 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Auto-stabilisation
Systèmes distribués
Algorithmes distribués
Ensembles indépendants
Ensembles 1-isolésIndex. décimale : 004 Informatique Résumé :
L’auto-stabilisation est une méthode permettant de gérer les pannes transitoires,
introduite par Dijkstra. Un système distribué est considéré comme auto-stabilisant s’il
est capable de revenir à un état correct après une période de temps fini, quel que soit
son état initial. Plusieurs problématiques observées dans les réseaux et les systèmes
distribués peuvent être modélisés à l’aide de graphes. Notre étude se concentre sur les
algorithmes distribués auto-stabilisants qui facilitent le calcul des ensembles indépendants
et dominants dans un graphe. Nous présentons un nouvel algorithme distribué
auto-stabilisant permettant de calculer un ensemble 1-isolé (TKD-1IS : 1-insulated set)
dans un graphe quelconque. Nous évaluons ses performances en simulant son comportement
dans un environnement à grande échelle. En outre, nous comparons notre
algorithme à d’autres algorithmes similaires de la littérature et discutons des résultats
obtenus, aussi nous présentons deux nouvelles versions de notre algorithme. Ce dernier
peut être utilisé pour organiser les ressources dans un système distribué et s’avère utile
pour regrouper des noeuds dans des réseaux (clustering).Note de contenu :
Sommaire
Introduction générale 1
1 Les systèmes distribués et l’auto-stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Les systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Exemples de systèmes distribués célèbres . . . . . . . . . . . . . 3
1.2.2 Les avantages des systemes distribués . . . . . . . . . . . . . . . 4
1.2.3 Les algorithmes distribués . . . . . . . . . . . . . . . . . . . . . 4
1.3 Les graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.2 Types de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Les pannes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 Les types de pannes . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.2 La tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . 6
1.5 L’auto-stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5.1 Définition : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5.2 Exemple d’algorithme auto-stabilisant . . . . . . . . . . . . . . 8
1.5.3 Les avantages de l’auto-stabilisation . . . . . . . . . . . . . . . 10
1.5.4 Les inconvénients de l’auto-stabilisation . . . . . . . . . . . . . 10
1.5.5 Les démons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5.6 Preuve d’auto-stabilisation . . . . . . . . . . . . . . . . . . . . 11
1.5.6.1 Preuve de Correction . . . . . . . . . . . . . . . . . . . 11
1.5.6.2 Preuve de Convergence . . . . . . . . . . . . . . . . . 11
1.5.7 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.7.1 Complexité en espace : . . . . . . . . . . . . . . . . . . 11
1.5.7.2 Complexité en temps . . . . . . . . . . . . . . . . . . 11
1.6 Définitions formelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Algorithmes d’ensembles indépendants 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Les ensembles dominants . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2 Les ensembles indépendants . . . . . . . . . . . . . . . . . . . . 14
2.2.3 Les ensembles k-isolés . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.4 Les ensembles 1-isolés . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.2 Les avantages du clustering . . . . . . . . . . . . . . . . . . . . 16
2.3.3 Usage des ensembles indépendants dans le clustering . . . . . . 17
2.4 L’état de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.1 Algorithme de Hedetniemi . . . . . . . . . . . . . . . . . . . . . 18
2.4.2 Algorithme de Turau . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.3 Algorithme de Shukla . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4.4 Algorithme de Srimani . . . . . . . . . . . . . . . . . . . . . . . 22
2.4.5 Algorithme de Naggazi . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.6 Algorithme de Michiyo . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.7 Récapitulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5 Autres références . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Un nouvel algorithme auto-stabilisant pour le calcul d’un ensemble
1-isolé (1-insulated set) 30
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 Hypothèses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Les règles de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Preuve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.6.1 Preuve de correction . . . . . . . . . . . . . . . . . . . . . . . . 33
3.6.2 Preuve de convergence . . . . . . . . . . . . . . . . . . . . . . . 33
3.7 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.8 Interface de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.9 Description du code de l’application de Kuszner (avec nos modifications) 37
3.10 Description de la première transformation (TKD_1IS_V2) . . . . . . . 41
3.11 Les règles de TKD_1IS_V2 . . . . . . . . . . . . . . . . . . . . . . . . 42
3.12 Description de la deuxième transformation (TKD_1IS_V3) . . . . . . . 43
3.13 Les règles de TKD_1IS_V3 . . . . . . . . . . . . . . . . . . . . . . . . 43
3.14 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Conclusion générale 44Côte titre : MAI/0943 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0943 MAI/0943 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Un nouvel algorithme auto-stabilisant pour le calcul d'un ensemble dominant fort (Strong Dominating Set) Type de document : texte imprimé Auteurs : Fatima Zahra Zergoune, Auteur ; Manel Chouar, Auteur ; Nabil Guellati, Directeur de thèse Année de publication : 2022 Importance : 1 vol (52 f .) Format : 29cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Système répartie
Tolérance aux pannesIndex. décimale : 004 Informatique Résumé :
est un système constitué d'un ensemble d'unités de calcul autonomes ayant la capacit
é de communiquer. Ces unités travaillent ensemble pour mener à bien une
mission globale.La probabilité de panne d'un élément du système n'est pas né-
gligeable, car en réalité il n'y a pas de système parfait.Ces pannes peuvent être
classées selon leurs durées, leurs étendues et leurs natures. Plusieurs mécanismes
de tolérance aux pannes sont décrits dans la littérature. Dans notre travail, nous
nous intéressons à l'auto-stabilisation en tant que mécanisme tolérant aux pannes.
Ces systèmes sont aussi vulnérables au cout de communication qui peut être
pallié par l'utilisation de clustering. Le clustering consiste au regroupement des
n÷uds selon un ou plusieurs paramètres comme le degré du n÷ud. Dans notre
travail nous présentons un algorithme auto-stabilisant qui calcule un ensemble
fortement dominant. Cet algorithme fonctionne dans les graphes arbitraire.Côte titre : MAI/0642 En ligne : https://drive.google.com/file/d/1NF6CVeFol1YIvKcZdJPy4xLMtsLQE2kh/view?usp=share [...] Format de la ressource électronique : Un nouvel algorithme auto-stabilisant pour le calcul d'un ensemble dominant fort (Strong Dominating Set) [texte imprimé] / Fatima Zahra Zergoune, Auteur ; Manel Chouar, Auteur ; Nabil Guellati, Directeur de thèse . - 2022 . - 1 vol (52 f .) ; 29cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Système répartie
Tolérance aux pannesIndex. décimale : 004 Informatique Résumé :
est un système constitué d'un ensemble d'unités de calcul autonomes ayant la capacit
é de communiquer. Ces unités travaillent ensemble pour mener à bien une
mission globale.La probabilité de panne d'un élément du système n'est pas né-
gligeable, car en réalité il n'y a pas de système parfait.Ces pannes peuvent être
classées selon leurs durées, leurs étendues et leurs natures. Plusieurs mécanismes
de tolérance aux pannes sont décrits dans la littérature. Dans notre travail, nous
nous intéressons à l'auto-stabilisation en tant que mécanisme tolérant aux pannes.
Ces systèmes sont aussi vulnérables au cout de communication qui peut être
pallié par l'utilisation de clustering. Le clustering consiste au regroupement des
n÷uds selon un ou plusieurs paramètres comme le degré du n÷ud. Dans notre
travail nous présentons un algorithme auto-stabilisant qui calcule un ensemble
fortement dominant. Cet algorithme fonctionne dans les graphes arbitraire.Côte titre : MAI/0642 En ligne : https://drive.google.com/file/d/1NF6CVeFol1YIvKcZdJPy4xLMtsLQE2kh/view?usp=share [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0642 MAI/0642 Mémoire Bibliothéque des sciences Français Disponible
Disponible
