|
| Titre : |
Algorithme auto-stabilisant pour le calcule d’un ensemble fortement dominant (Strong Dominating Set) |
| Type de document : |
document électronique |
| Auteurs : |
Lamis Flifla, Auteur ; Anouar Ala Errahmane Herizi, Auteur ; Guellati, Nabil, Directeur de thèse |
| Editeur : |
Sétif:UFA1 |
| Année de publication : |
2024 |
| Importance : |
1 vol (52 f .) |
| Format : |
29 cm |
| Langues : |
Français (fre) |
| Catégories : |
Thèses & Mémoires:Informatique
|
| Mots-clés : |
Informatique |
| Index. décimale : |
004 Informatique |
| Résumé : |
L'auto-stabilisation est un concept important dans les systèmes distribués qui permet de
garantir la sécurité et la fiabilité du système, même en cas de pannes transitoires.
Alors , L’objectif de notre travail est de faire un algorithme auto-stabilisant pour le calcul
d’un ensemble fortement dominant , pour garantir que le système revienne à un état
correct et cohérent, même après avoir subi des perturbations ou des pannes. En d'autres
termes, ces algorithmes sont capables de se rétablir automatiquement et de maintenir leur
bon fonctionnement dans des conditions changeantes ou instables.
Notre travail a été réalisé en trois étapes : tout d’abord, nous avons présenté l’historique
de ce domaine, comme on a défini ses principaux concepts , en mentionnant la biographie
du son père ‘’Edsger Wybe Dijkstra’’ . Ensuite , on a fait une description des ensemble
dominants et leurs types . Enfin , parmi les types des ensembles dominants on a choisi
l’ensemble fortement dominant minimale , pour développer un nouvel algorithme pour ce
paramètre puis nous avons implémenté notre algorithme en utilisant le langage JAVA afin
de le comparer avec des algorithmes de la littérature. |
| Note de contenu : |
Sommaire
Résumé………………………………………..………………………………………..………………………………..……. 6
Introduction générale ………………………………………………………………………..………………………… 8
Chapitre 1……………………………………………………………………………………………………….…………. 9
1.Introduction ……………….………………………………………………………………………………….............. 9
2.Systèmes répartis ……………………………………………………………………………………………………. 9
2.1.Modèles de communication dans les systèmes répartis et concept de
synchronisation………………..……………………………………………………………………………. 10
2.2.Propriètes des systèmes repartis …………………………………………………………….……… 11
2.3. Modélisations des systèmes réparties ……………………………………………………….…… 11
2.4.Les avantages des systèmes repartis ……………………………………………………….……… 12
2.5. La différence entre les systèmes repartis et les systèmes centralisés…………….…. 12
3.Les algorithmes répartis ………………………………………………………………………….……………... 12
3.1.Son fonctionnement ………………………………………………………………………….……….…. 13
3.2.Type d’algorithmes……………………………………………………………………………………… 14
4.L’auto-stabilisation ………………………………………………………………………………………………… 14
4.1.Définition de panne…………………………………………………………………………………….... 14
4.2.Définition de la tolérance des pannes ………………………………………………………… …15
4.3.Temps de stabilisation …………………………………………………………………………………. 15
4.4.Les avantages et les inconvénients d’auto-stabilisation…………………………………… 15
5.Algorithme de Dijkstra …………………………………………………………………………………………… 16
5.1.Découverte scientifique ………………………………………………………………………………… 17
5.2.Le token ring de dijkstra …………………..………………………………………………………….... 17
5.3.Exemple……………………..……………………………………………………………………………… ….18
6.Conclusion ………………………..……………………………………………………………………………..…… 19
Chapitre 2……………………………………………………………………………………………………………..… 20
1.Introduction ………………………………………………………………………………………..………………… 20
2.L’ensemble dominant ……………………………………………………………………………………………... 20
2.1.Un ensemble dominant indépendant …………………………………………………………...….. 20
2.2.Ensemble fortement dominant ……………………………………………………………………….. 21
2.3.Un ensemble dominant connecté ………………………………………………………………….… 21
3.Introduction pour les réseaux sans fil ………………………………………………………………… … 21
4.Le clustering …………………………………………………………………………………………………………. 22
4.1. La structure de clustering ……………………………………………………………………...……... 22
4.2.La procédure de clustering ……………………………………………………………………...…….. 23
5.Les algorithme bases sur les ensembles dominants …………………………………………..……. 23
5.1. L'algorithme LEACH (Low Energy Adaptive Clustering Hierarchy) …………..……..…… 24
5.2. Le concept d'ensemble dominant connecté a été introduit pour la première fois par
Guha et Kuller …………………………………………………………………………………..…………………..…. 24
5.3. L'algorithme de clustering pondéré (WCA)……………………………………………...…… 24
6. L’état de l’art…………………………………………………………………………………………………..….… 24
6.1.L'algorithme de Xu et al (Ensemble dominant minimal)…………………………....…… 24
6. 2. L’algorithme de D.P. Jacobs: (Dominating Bipartitions)…………………..……………..……… 25
6.3.L’algorithme de P.K. Srimani………………………………………………………………..………... 26
6.4. L’algorithme de Volker Turau (Ensembles dominants minimaux )……..………..… 27
6.5.Algorithme de Neggazi ……………………..…………………………………………………….…….. 27
7.Autre références ………………………………………………………………………………….……………… 29
8.Conclusion ……………………………………………………...………………………………………………..… 30 |
| Côte titre : |
MAI/0945 |
Algorithme auto-stabilisant pour le calcule d’un ensemble fortement dominant (Strong Dominating Set) [document électronique] / Lamis Flifla, Auteur ; Anouar Ala Errahmane Herizi, Auteur ; Guellati, Nabil, Directeur de thèse . - [S.l.] : Sétif:UFA1, 2024 . - 1 vol (52 f .) ; 29 cm. Langues : Français ( fre)
| Catégories : |
Thèses & Mémoires:Informatique
|
| Mots-clés : |
Informatique |
| Index. décimale : |
004 Informatique |
| Résumé : |
L'auto-stabilisation est un concept important dans les systèmes distribués qui permet de
garantir la sécurité et la fiabilité du système, même en cas de pannes transitoires.
Alors , L’objectif de notre travail est de faire un algorithme auto-stabilisant pour le calcul
d’un ensemble fortement dominant , pour garantir que le système revienne à un état
correct et cohérent, même après avoir subi des perturbations ou des pannes. En d'autres
termes, ces algorithmes sont capables de se rétablir automatiquement et de maintenir leur
bon fonctionnement dans des conditions changeantes ou instables.
Notre travail a été réalisé en trois étapes : tout d’abord, nous avons présenté l’historique
de ce domaine, comme on a défini ses principaux concepts , en mentionnant la biographie
du son père ‘’Edsger Wybe Dijkstra’’ . Ensuite , on a fait une description des ensemble
dominants et leurs types . Enfin , parmi les types des ensembles dominants on a choisi
l’ensemble fortement dominant minimale , pour développer un nouvel algorithme pour ce
paramètre puis nous avons implémenté notre algorithme en utilisant le langage JAVA afin
de le comparer avec des algorithmes de la littérature. |
| Note de contenu : |
Sommaire
Résumé………………………………………..………………………………………..………………………………..……. 6
Introduction générale ………………………………………………………………………..………………………… 8
Chapitre 1……………………………………………………………………………………………………….…………. 9
1.Introduction ……………….………………………………………………………………………………….............. 9
2.Systèmes répartis ……………………………………………………………………………………………………. 9
2.1.Modèles de communication dans les systèmes répartis et concept de
synchronisation………………..……………………………………………………………………………. 10
2.2.Propriètes des systèmes repartis …………………………………………………………….……… 11
2.3. Modélisations des systèmes réparties ……………………………………………………….…… 11
2.4.Les avantages des systèmes repartis ……………………………………………………….……… 12
2.5. La différence entre les systèmes repartis et les systèmes centralisés…………….…. 12
3.Les algorithmes répartis ………………………………………………………………………….……………... 12
3.1.Son fonctionnement ………………………………………………………………………….……….…. 13
3.2.Type d’algorithmes……………………………………………………………………………………… 14
4.L’auto-stabilisation ………………………………………………………………………………………………… 14
4.1.Définition de panne…………………………………………………………………………………….... 14
4.2.Définition de la tolérance des pannes ………………………………………………………… …15
4.3.Temps de stabilisation …………………………………………………………………………………. 15
4.4.Les avantages et les inconvénients d’auto-stabilisation…………………………………… 15
5.Algorithme de Dijkstra …………………………………………………………………………………………… 16
5.1.Découverte scientifique ………………………………………………………………………………… 17
5.2.Le token ring de dijkstra …………………..………………………………………………………….... 17
5.3.Exemple……………………..……………………………………………………………………………… ….18
6.Conclusion ………………………..……………………………………………………………………………..…… 19
Chapitre 2……………………………………………………………………………………………………………..… 20
1.Introduction ………………………………………………………………………………………..………………… 20
2.L’ensemble dominant ……………………………………………………………………………………………... 20
2.1.Un ensemble dominant indépendant …………………………………………………………...….. 20
2.2.Ensemble fortement dominant ……………………………………………………………………….. 21
2.3.Un ensemble dominant connecté ………………………………………………………………….… 21
3.Introduction pour les réseaux sans fil ………………………………………………………………… … 21
4.Le clustering …………………………………………………………………………………………………………. 22
4.1. La structure de clustering ……………………………………………………………………...……... 22
4.2.La procédure de clustering ……………………………………………………………………...…….. 23
5.Les algorithme bases sur les ensembles dominants …………………………………………..……. 23
5.1. L'algorithme LEACH (Low Energy Adaptive Clustering Hierarchy) …………..……..…… 24
5.2. Le concept d'ensemble dominant connecté a été introduit pour la première fois par
Guha et Kuller …………………………………………………………………………………..…………………..…. 24
5.3. L'algorithme de clustering pondéré (WCA)……………………………………………...…… 24
6. L’état de l’art…………………………………………………………………………………………………..….… 24
6.1.L'algorithme de Xu et al (Ensemble dominant minimal)…………………………....…… 24
6. 2. L’algorithme de D.P. Jacobs: (Dominating Bipartitions)…………………..……………..……… 25
6.3.L’algorithme de P.K. Srimani………………………………………………………………..………... 26
6.4. L’algorithme de Volker Turau (Ensembles dominants minimaux )……..………..… 27
6.5.Algorithme de Neggazi ……………………..…………………………………………………….…….. 27
7.Autre références ………………………………………………………………………………….……………… 29
8.Conclusion ……………………………………………………...………………………………………………..… 30 |
| Côte titre : |
MAI/0945 |
|
Ajouter le résultat dans votre panier Affiner la rechercheAlgorithme auto-stabilisant pour le calcule d’un ensemble fortement dominant (Strong Dominating Set) / Lamis Flifla
