University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Amarchi,Nour el-houda |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Simulation d'algorithmesauto- stabilsants dans les réseaux complexces Type de document : texte imprimé Auteurs : Amarchi,Nour el-houda, Auteur ; Benreguia,Baadreddine, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (41 f .) Format : 29 cm Langues : Français (fre) Langues originales : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Informatique: réseaux complexces Résumé : Résumé
Notre objectif a été d’intégrer et d’implémenter le modèle Scale Free, et offrir une nouvelle vision à la communauté scientifique pour pouvoir tester des algorithmes auto-stabilisants sur des réseaux complexes proches de la réalité.
1. Les algorithmes auto-stabilisants fournissent une tolérance naturelle aux pannes transi-toires, et ce quelle que soit leur distribution. Le coût d'une telle propriété est l'existence d'une phase de stabilisation pendant laquelle les pannes peuvent influencer le système, se propager et produire un comportement incorrect. L'étude du comportement des algorithmes auto-stabilisants pendant cette phase de convergence, et la contrainte de ce comportement est donc un sujet particulièrement important de l'algorithmique auto-stabilisante.
2. Nous avons défini l’ensemble des modèles de graphes qui existent dans la littérature comme (Random, Small World et Scale Free networks), ainsi que la distribution de degré qui représente la probabilité qu’un noeud sélectionné aléatoirement possède k arêtes. La distribution de degré d’un graphe aléatoire suit la loi de poisson par contre les larges réseaux complexes suivent une loi de puissance.
3. À la fin, nous avons implémenté et simulé le modèle Scale Free, afin de le comparer vis-à -vis le modèle Random) par des tests benchmark sur trois algorithmes auto-stabilisants : Grundy Coloration, MIS et MDS. Nous avons déduit que le temps de convergence des algorithmes Grundy Coloration et MDS pour le modèle Scale Free est mieux que celui du modèle Random. De plus en matiére de cardinalité selon l’algorithme MIS Scale Free est bien meilleur.
Perspectives
L’auto-stabilisation dans les réseaux complexes est un domaine très prometteur pour l’avenir. Dans les futurs travaux, nous souhaiterions faire une étude détaillée sur les résultats obtenus après la simulation, et tester d’autres algorithmes auto-stabilisants sur des graphes proches de la réalité afin de les comparer.
40Note de contenu : Sommaire
Remerciement .............................................................................................................................. I
Dédicace ..................................................................................................................................... II
Table des matières ................................................................................................................... III
Introduction générale ................................................................................................................... 1
Chapitre 1: L'auto stabilisation
1.1. Introduction .................................................................................................................... 3
1.2. Qu’est-ce qu’un système distribué ? ............................................................................. 3
1.2.1. Propriété d’un système distribué : ......................................................................... 4
1.2.2. Avantages et inconvénients des systèmes distribués ............................................ 5
1.2.2.1. Avantages : ....................................................................................................... 5
1.2.2.2. Inconvénients .................................................................................................... 5
1.2.3. Comment modéliser un système distribué ? .......... Error! Bookmark not defined.
1.2.4. Problèmes classiques en algorithmes distribués :................................................. 6
1.2.4.1. Problèmes statiques ............................................................................................... 6
1.2.4.2. Problème dynamique ............................................................................................ 7
1.2.5. Modèles de communications : ................................................................................ 7
1.2.6. Tolérance aux pannes : ........................................................................................... 7
1.3. L’auto stabilisation : ....................................................................................................... 9
1.3.1. Avantages et limites de l’auto-stabilisation : ...................................................... 10
1.3.1.1. Avantages : ..................................................................................................... 10
1.3.1.2. Limites : .......................................................................................................... 10
1.3.2. Domaine d’application de l’auto-stabilisation :.................................................. 11
1.3.2.1. Ensemble dominant ....................................................................................... 11
1.3.2.2. Ensemble indépendant .................................................................................. 11
1.3.2.3. Coloration des sommets : .............................................................................. 12
1.3.3. Définitions formelles ............................................................................................. 13
1.3.3.1. Les Démons ........................................................................................................ 14
1.3.3.2. Distribution : .................................................................................................. 14
1.3.3.3. Équité : ............................................................................................................ 14
1.3.4. Mesures de complexité .......................................................................................... 15
1.4. Conclusion ..................................................................................................................... 15
Chapitre 2: Les modèles de graphes et la proposition d’un algorithme pour un générateur Scale Free
2.1. Introduction .................................................................................................................. 16
2.2. Coefficient de clustering : ............................................................................................ 16
2.3. Distribution de degré : ................................................................................................. 17
2.3.1. C’est quoi la loi de puissance ? ............................................................................. 17
2.3.2. C’est quoi la loi de poisson ? ................................................................................ 17
2.4. Les modèles de graphes théoriques « classiques » ..................................................... 18
2.4.1. Random network : ................................................................................................. 18
2.4.2. Small World network : ......................................................................................... 19
2.4.2.1. Le modèle Stenely Milgram: ......................................................................... 19
2.4.2.2. Le modèle Watts et Strogatz : ....................................................................... 20
2.4.3. Scale Free network : .............................................................................................. 22
2.4.3.1. Historique de Scale Free networks : ............................................................ 24
2.4.3.2. Comment crée un graphe Scale Free avec 11 noeuds et un degré attachement 2? 25
2.4.3.3. Pseudo code pour crée un graphe de modèle Scale free: ............................ 26
2.5. Conclusion : ................................................................................................................... 26
Chapitre 3: Simulation et résultats
3.1. Introduction .................................................................................................................. 27
3.2. Explication de l’algorithme : ....................................................................................... 27
3.2.1. La classe Graph : ................................................................................................... 27
3.2.1.1. Génération de graph du modèle Scale Free : .............................................. 27
3.2.1.2. La méthode : calculMDS() ............................................................................ 29
3.2.1.3. La méthode : calculMIS() .............................................................................. 29
3.2.2. La classe ColoringVertex : ................................................................................... 30
3.2.3. La classe DemonDialog ......................................................................................... 30
3.3. Étude comparative entre les graphes Random et Scale Free: .................................. 31
3.3.1. Simulation : ............................................................................................................ 31
3.3.2. Détail de la simulation : ........................................................................................ 31
3.3.3. Étude de performance : ........................................................................................
3.3.3.1. Grundy coloration algorithme : .................................................................... 32
3.3.3.2. MIS Algorithme : ........................................................................................... 34
3.3.3.3. MDS Algorithme : .......................................................................................... 36
3.3.4. Résultat de l’étude comparative : ........................................................................ 38
3.4. Conclusion : ................................................................................................................... 38
Conclusion générale .................................................................................................................. 39
Bibliographies ............................................................................................................................ 40
Webographie………………………………………………………………………………………………………………………………42
Côte titre : MAI/0268 En ligne : https://drive.google.com/file/d/1XRsieiHeRXnq_pe3rdYmeJ752g9blIt4/view?usp=shari [...] Format de la ressource électronique : Simulation d'algorithmesauto- stabilsants dans les réseaux complexces [texte imprimé] / Amarchi,Nour el-houda, Auteur ; Benreguia,Baadreddine, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (41 f .) ; 29 cm.
Langues : Français (fre) Langues originales : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Informatique: réseaux complexces Résumé : Résumé
Notre objectif a été d’intégrer et d’implémenter le modèle Scale Free, et offrir une nouvelle vision à la communauté scientifique pour pouvoir tester des algorithmes auto-stabilisants sur des réseaux complexes proches de la réalité.
1. Les algorithmes auto-stabilisants fournissent une tolérance naturelle aux pannes transi-toires, et ce quelle que soit leur distribution. Le coût d'une telle propriété est l'existence d'une phase de stabilisation pendant laquelle les pannes peuvent influencer le système, se propager et produire un comportement incorrect. L'étude du comportement des algorithmes auto-stabilisants pendant cette phase de convergence, et la contrainte de ce comportement est donc un sujet particulièrement important de l'algorithmique auto-stabilisante.
2. Nous avons défini l’ensemble des modèles de graphes qui existent dans la littérature comme (Random, Small World et Scale Free networks), ainsi que la distribution de degré qui représente la probabilité qu’un noeud sélectionné aléatoirement possède k arêtes. La distribution de degré d’un graphe aléatoire suit la loi de poisson par contre les larges réseaux complexes suivent une loi de puissance.
3. À la fin, nous avons implémenté et simulé le modèle Scale Free, afin de le comparer vis-à -vis le modèle Random) par des tests benchmark sur trois algorithmes auto-stabilisants : Grundy Coloration, MIS et MDS. Nous avons déduit que le temps de convergence des algorithmes Grundy Coloration et MDS pour le modèle Scale Free est mieux que celui du modèle Random. De plus en matiére de cardinalité selon l’algorithme MIS Scale Free est bien meilleur.
Perspectives
L’auto-stabilisation dans les réseaux complexes est un domaine très prometteur pour l’avenir. Dans les futurs travaux, nous souhaiterions faire une étude détaillée sur les résultats obtenus après la simulation, et tester d’autres algorithmes auto-stabilisants sur des graphes proches de la réalité afin de les comparer.
40Note de contenu : Sommaire
Remerciement .............................................................................................................................. I
Dédicace ..................................................................................................................................... II
Table des matières ................................................................................................................... III
Introduction générale ................................................................................................................... 1
Chapitre 1: L'auto stabilisation
1.1. Introduction .................................................................................................................... 3
1.2. Qu’est-ce qu’un système distribué ? ............................................................................. 3
1.2.1. Propriété d’un système distribué : ......................................................................... 4
1.2.2. Avantages et inconvénients des systèmes distribués ............................................ 5
1.2.2.1. Avantages : ....................................................................................................... 5
1.2.2.2. Inconvénients .................................................................................................... 5
1.2.3. Comment modéliser un système distribué ? .......... Error! Bookmark not defined.
1.2.4. Problèmes classiques en algorithmes distribués :................................................. 6
1.2.4.1. Problèmes statiques ............................................................................................... 6
1.2.4.2. Problème dynamique ............................................................................................ 7
1.2.5. Modèles de communications : ................................................................................ 7
1.2.6. Tolérance aux pannes : ........................................................................................... 7
1.3. L’auto stabilisation : ....................................................................................................... 9
1.3.1. Avantages et limites de l’auto-stabilisation : ...................................................... 10
1.3.1.1. Avantages : ..................................................................................................... 10
1.3.1.2. Limites : .......................................................................................................... 10
1.3.2. Domaine d’application de l’auto-stabilisation :.................................................. 11
1.3.2.1. Ensemble dominant ....................................................................................... 11
1.3.2.2. Ensemble indépendant .................................................................................. 11
1.3.2.3. Coloration des sommets : .............................................................................. 12
1.3.3. Définitions formelles ............................................................................................. 13
1.3.3.1. Les Démons ........................................................................................................ 14
1.3.3.2. Distribution : .................................................................................................. 14
1.3.3.3. Équité : ............................................................................................................ 14
1.3.4. Mesures de complexité .......................................................................................... 15
1.4. Conclusion ..................................................................................................................... 15
Chapitre 2: Les modèles de graphes et la proposition d’un algorithme pour un générateur Scale Free
2.1. Introduction .................................................................................................................. 16
2.2. Coefficient de clustering : ............................................................................................ 16
2.3. Distribution de degré : ................................................................................................. 17
2.3.1. C’est quoi la loi de puissance ? ............................................................................. 17
2.3.2. C’est quoi la loi de poisson ? ................................................................................ 17
2.4. Les modèles de graphes théoriques « classiques » ..................................................... 18
2.4.1. Random network : ................................................................................................. 18
2.4.2. Small World network : ......................................................................................... 19
2.4.2.1. Le modèle Stenely Milgram: ......................................................................... 19
2.4.2.2. Le modèle Watts et Strogatz : ....................................................................... 20
2.4.3. Scale Free network : .............................................................................................. 22
2.4.3.1. Historique de Scale Free networks : ............................................................ 24
2.4.3.2. Comment crée un graphe Scale Free avec 11 noeuds et un degré attachement 2? 25
2.4.3.3. Pseudo code pour crée un graphe de modèle Scale free: ............................ 26
2.5. Conclusion : ................................................................................................................... 26
Chapitre 3: Simulation et résultats
3.1. Introduction .................................................................................................................. 27
3.2. Explication de l’algorithme : ....................................................................................... 27
3.2.1. La classe Graph : ................................................................................................... 27
3.2.1.1. Génération de graph du modèle Scale Free : .............................................. 27
3.2.1.2. La méthode : calculMDS() ............................................................................ 29
3.2.1.3. La méthode : calculMIS() .............................................................................. 29
3.2.2. La classe ColoringVertex : ................................................................................... 30
3.2.3. La classe DemonDialog ......................................................................................... 30
3.3. Étude comparative entre les graphes Random et Scale Free: .................................. 31
3.3.1. Simulation : ............................................................................................................ 31
3.3.2. Détail de la simulation : ........................................................................................ 31
3.3.3. Étude de performance : ........................................................................................
3.3.3.1. Grundy coloration algorithme : .................................................................... 32
3.3.3.2. MIS Algorithme : ........................................................................................... 34
3.3.3.3. MDS Algorithme : .......................................................................................... 36
3.3.4. Résultat de l’étude comparative : ........................................................................ 38
3.4. Conclusion : ................................................................................................................... 38
Conclusion générale .................................................................................................................. 39
Bibliographies ............................................................................................................................ 40
Webographie………………………………………………………………………………………………………………………………42
Côte titre : MAI/0268 En ligne : https://drive.google.com/file/d/1XRsieiHeRXnq_pe3rdYmeJ752g9blIt4/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0268 MAI/0268 Mémoire Bibliothéque des sciences Français Disponible
Disponible