University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Battaa, Mohamed Sofiane |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la rechercheUn nouvel algorithme auto- stabilisant pour le calcul d'un ensemble dominant à ditance k / Battaa, Mohamed Sofiane
Titre : Un nouvel algorithme auto- stabilisant pour le calcul d'un ensemble dominant à ditance k Type de document : texte imprimé Auteurs : Battaa, Mohamed Sofiane, Auteur ; Guellati,Nabil, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (55 f .) Format : 29 cm Langues : Français (fre) Langues originales : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Auto-stabilisation
Systèmes distribués
Algorithmes distribuésIndex. décimale : 004 Informatique Résumé : Résumé
L’auto stabilisation est une technique qui permet la tolérance aux pannes transi- toires. Elle a été introduite par E. W. Dijkstra en 1974. Un système ou un algo- rithme distribué est dit auto stabilisant si à partir de n’importe quel état initial, il est capable de retrouver automatiquement un état correct au bout d’un temps fini. De nombreux problèmes étudiés dans les réseaux et les systèmes repartis peuvent être modélises par des graphes. Plusieurs recherches ont été menées dans ce do- maine et plusieurs algorithmes repartis de graphe ont été développés. Nous étudions dans ce travail, les algorithmes distribués auto stabilisants qui permettent le calcul d’ensembles dominants et indépendants dans un graphe. Nous présentons un nouvel algorithme distribué auto stabilisant qui permet le calcul d’un ensemble dominant à distance k (DKDS : distance-k dominating set ) dans un graphe arbitraire. Nous allons évaluer ses performances par simulation de son comportement dans un en- vironnement à grand échèle. Ensuite, nous allons effectuer une comparaison entre notre algorithme et d’autres algorithmes similaires dans la littérature et discuter les résultats obtenues. Notre algorithme peut être utilisé pour l’organisation des res- sources dans un système distribué et il est utile pour faire du clustering dans les réseaux (organisation des noeuds d’un réseau en groupes).
Note de contenu : Table des matières
Introduction générale 1
1 L’auto-stabilisation dans les Systèmes distribués 2
Introduction 2
Système distribué 2
Algorithme distribué 3
Les Types de pannes 5
La tolérance aux pannes 6
L’auto-stabilisation 6
Définition 6
Premier algorithme auto stabilisant 7
Les avantages et les inconvenants de l’auto stabilisation 10
Définitions formelles 10
Preuve d’auto stabilisation 11
Preuve de correction 11
Preuve de convergence 11
Complexité 12
Complexité en espace 12
Complexité en temps 12
Démons 13
Conclusion 13
2 Les algorithmes distribués auto stabilisants d’ensembles dominants
et indépendants 15
Introduction 15
Usage des ensembles dominants et indépendants dans le clustering 15
Avantages du clustering 16
Définitions 17
État de l’art sur les algorithmes distribués auto-stabilisants d’en- sembles dominants et indépendants 19
Les algorithmes de Hedetniemi 20
Les algorithmes de Turau (MIS et MDS) 22
L’algorithme de Chiu (MDS) 25
L’algorithme de Goddard (MIS) 27
L’algorithme de Goddard (MDS) 28
L’algorithme de Neggazi (ISDS) 30
L’algorithme de Srimani (MTDS) 31
L’algorithme de Huang (MKDS /K=2) 33
L’algorithme de Lin (MKDS /K=2) 34
2.5 Récapitulation 36
2.6 conclusion 37
3.Un vouvel algorithme distribué auto-stabilisant (DKDS) 38
3.1 Introduction 38
3.2 Défintion 38
3.3 Usage des ensemble DKDS 40
3.4 Hipothèse de notre algorithme 41
3.5 Désctiption de l'algorithme 41
3.6 La preuve de l'algorithme 45
3.6.1 preuve de convergence 45
3.7 Analyse de complexité 47
3.8 Simulation 49
3.9 Interface de l'application 51
3.10 Conclusion 52
Conclusion générale 53
Bibliographie 54Côte titre : MAI/0213 En ligne : https://drive.google.com/file/d/1tP5i4_CZLN-Uh8SLdSmb0oQffEw0vZkJ/view?usp=shari [...] Format de la ressource électronique : Un nouvel algorithme auto- stabilisant pour le calcul d'un ensemble dominant à ditance k [texte imprimé] / Battaa, Mohamed Sofiane, Auteur ; Guellati,Nabil, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (55 f .) ; 29 cm.
Langues : Français (fre) Langues originales : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Auto-stabilisation
Systèmes distribués
Algorithmes distribuésIndex. décimale : 004 Informatique Résumé : Résumé
L’auto stabilisation est une technique qui permet la tolérance aux pannes transi- toires. Elle a été introduite par E. W. Dijkstra en 1974. Un système ou un algo- rithme distribué est dit auto stabilisant si à partir de n’importe quel état initial, il est capable de retrouver automatiquement un état correct au bout d’un temps fini. De nombreux problèmes étudiés dans les réseaux et les systèmes repartis peuvent être modélises par des graphes. Plusieurs recherches ont été menées dans ce do- maine et plusieurs algorithmes repartis de graphe ont été développés. Nous étudions dans ce travail, les algorithmes distribués auto stabilisants qui permettent le calcul d’ensembles dominants et indépendants dans un graphe. Nous présentons un nouvel algorithme distribué auto stabilisant qui permet le calcul d’un ensemble dominant à distance k (DKDS : distance-k dominating set ) dans un graphe arbitraire. Nous allons évaluer ses performances par simulation de son comportement dans un en- vironnement à grand échèle. Ensuite, nous allons effectuer une comparaison entre notre algorithme et d’autres algorithmes similaires dans la littérature et discuter les résultats obtenues. Notre algorithme peut être utilisé pour l’organisation des res- sources dans un système distribué et il est utile pour faire du clustering dans les réseaux (organisation des noeuds d’un réseau en groupes).
Note de contenu : Table des matières
Introduction générale 1
1 L’auto-stabilisation dans les Systèmes distribués 2
Introduction 2
Système distribué 2
Algorithme distribué 3
Les Types de pannes 5
La tolérance aux pannes 6
L’auto-stabilisation 6
Définition 6
Premier algorithme auto stabilisant 7
Les avantages et les inconvenants de l’auto stabilisation 10
Définitions formelles 10
Preuve d’auto stabilisation 11
Preuve de correction 11
Preuve de convergence 11
Complexité 12
Complexité en espace 12
Complexité en temps 12
Démons 13
Conclusion 13
2 Les algorithmes distribués auto stabilisants d’ensembles dominants
et indépendants 15
Introduction 15
Usage des ensembles dominants et indépendants dans le clustering 15
Avantages du clustering 16
Définitions 17
État de l’art sur les algorithmes distribués auto-stabilisants d’en- sembles dominants et indépendants 19
Les algorithmes de Hedetniemi 20
Les algorithmes de Turau (MIS et MDS) 22
L’algorithme de Chiu (MDS) 25
L’algorithme de Goddard (MIS) 27
L’algorithme de Goddard (MDS) 28
L’algorithme de Neggazi (ISDS) 30
L’algorithme de Srimani (MTDS) 31
L’algorithme de Huang (MKDS /K=2) 33
L’algorithme de Lin (MKDS /K=2) 34
2.5 Récapitulation 36
2.6 conclusion 37
3.Un vouvel algorithme distribué auto-stabilisant (DKDS) 38
3.1 Introduction 38
3.2 Défintion 38
3.3 Usage des ensemble DKDS 40
3.4 Hipothèse de notre algorithme 41
3.5 Désctiption de l'algorithme 41
3.6 La preuve de l'algorithme 45
3.6.1 preuve de convergence 45
3.7 Analyse de complexité 47
3.8 Simulation 49
3.9 Interface de l'application 51
3.10 Conclusion 52
Conclusion générale 53
Bibliographie 54Côte titre : MAI/0213 En ligne : https://drive.google.com/file/d/1tP5i4_CZLN-Uh8SLdSmb0oQffEw0vZkJ/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0213 MAI/0213 Mémoire Bibliothéque des sciences Français Disponible
Disponible
