University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'indexation
Ouvrages de la bibliothèque en indexation 004
Ajouter le résultat dans votre panier Affiner la recherche
Implémentation d'un algorithme auto-stabilisant pour le calcul d'un arbre couvrant / Bensedira,meriem
Titre : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un arbre couvrant Type de document : texte imprimé Auteurs : Bensedira,meriem ; GUELLATI, N, Directeur de thèse Editeur : Setif:UFA Année de publication : 2016 Importance : 1 vol (55f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
Systèmes répartis
tolérance aux pannes
auto-stabilisation
arbres couvrantsIndex. décimale : 004 Informatique Résumé : Résumé
Les systèmes distribués sont particulièrement sujets à des pannes, lorsqu’on augmente le nombre de processeurs de tels systèmes, la possibilité que ces composants tombent en panne va être également élevée, l’auto-stabilisation est l’une des techniques de tolérance aux pannes
particulièrement les pannes transitoires.
En 1973, E.W. Dijkstra a définit l’auto-stabilisation comme la propriété pour un système de se retrouver lui-même dans un comportement correct en un nombre fini d’étapes, et ce, quel que soit son état initial. L’auto-stabilisation constitue donc un moyen efficace pour tolérer les pannes transitoires.
Notre étude a pour objectif alors de transformer et implémenter un algorithme autostabilisant permettant à un ensemble de nœuds d’un réseau, en démarrant d’une configuration
quelconque, d’arriver à une configuration correct, dite légitime, après un temps fini en
utilisant le modèle de communication par échange de messages.Note de contenu : Table des matières
INTRODUCTION GENERALE .......................................................................... 1
Chapitre 1: Systèmes distribués et auto-stabilisation
1.1 INTRODUCTION............................................................................................. 4
1.2 SYSTEMES DISTRIBUES ............................................................................................. 4
1.2.1 OBJECTIFS DES SYSTEMES DISTRIBUES ............................................................................. 5
1.2.2 LES MODES DE COMMUNICATIONS................................................................................ 5
1.2.3 ALGORITHMES DISTRIBUES ........................................................................................... 7
1.2.3.1 Problèmes classiques en algorithmique distribuée ....................................................................... 8
1.2.3.1.1 Les problèmes statiques............................................................................... 8
1.2.3.1.2 Les problèmes dynamiques ....................................................................... 8
1.2.3.2 Topologies classiques .................................................................................. 9
1.2.4 TOLERANCE AUX PANNES................................................................................. 9
1.2.4.1 Classification des pannes............................................................................. 10
1.2.4.2 Tolérance classique aux pannes ................................................................... 10
1.2.4.3 L’auto-stabilisation : ............................................................................. 11
1.2.4.3.1 Token-ring de Dijkstra...................................................................... 12
1.2.4.3.2 Définitions formelles........................................................................ 15
1.2.4.4 Atomicité :..................................................................................... 17
1.2.4.5 Démon :...................................................................................... 17
1.2.4.6 Complexité ............................................................................ 18
1.3. CONCLUSION .................................................19
Chapitre 2: Etat de l'art sur les algorithmes auto-stabilisants de calcul d'arbres couvrants
2.1 INTRODUCTION..................................................................................... 21
2.2 DEFINITIONS .......................................................................................... 21
2.3 ARBRES COUVRANTS ET PLUS COURT CHEMIN DANS LES SYSTEMES DISTRIBUES . 22
2.4 ALGORITHMES UTILISANT UN MODELE DE COMMUNICATION PAR MEMOIRE PARTAGEE ............................................ 23
2.4.1 ALGORITHMES UTILISANT UN DEMON CENTRALISE .............................................................................. 23
2.4.1.1 Algorithme de Huang et Chen.................................................................................... 23
2.4.1.2 Algorithme de Dolev, Israeli et Moran ......................................................................... 23
2.4.1.3 Algorithme de Dolev ......................................................................................... 24
2.4.1.4 Algorithme de Afek............................................................................................. 26
2.4.1.5 Algorithme de T.C.Huang ....................................................................................... 26
2.4.1.6 Algorithme de Lélia Blin...................................................................................... 28
2.4.1.7 Algorithme de Lélia Blin.................................................................................. 29
2.4.2 ALGORITHMES UTILISANT UN DEMON DISTRIBUE .................................................................. 31
2.4.2.1 Algorithme de Lavallé............................................................................... 31
2.4.2.2 Algorithme de T.C. Huang ................................................................................ 32
2.4.2.3 Algorithme de Lélia Blin.................................................................................. 34
2.5 ALGORITHMES UTILISANT UN MODELE DE COMMUNICATION PAR ECHANGE DE MESSAGES............................................. 35
2.5.1 ALGORITHME DE GUPTA ET SRIMANI .............................................................................. 35
6. CONCLUSION.............................................................................................. 36
Chapitre 3: conception et implémentation
3.1 INTRODUCTION....................................................................................... 38
3.2 TRANSFORMATION DE L’ALGORITHME AUTO-STABILISANT........................................... 38
3.2.1 LANGAGE DE PROGRAMMATION ET ENVIRONNEMENT..................................................................... 40
3.2.2 PRESENTATION DE L’ALGORITHME :............................................................................... 41
3.3 CONCEPTION ..................................................................................................... 43
3.3.1 SPECIFICATION INFORMELLE DES BESOINS ...................................................................... 43
3.3.2 MODELISATION ................................................................................................. 44
3.3.2.1 Modélisation des interactions..................................................................................... 44
3.3.2.2 Modélisation de la sémantique .............................................................................. 49
3.3.2.3 Modélisation de la structure ................................................................................... 49
3.4 SIMULATION D’UNE PANNE TRANSITOIRE .............................................................................. 50
3.5 CONCLUSION ......................................................................................................... 53
CONCLUSION GENERALE ................................................................................................ 54Côte titre : MAI/0135 En ligne : https://drive.google.com/file/d/1WDqzdpT3X98n5_y74vwIY9_Yq80iLFbX/view?usp=shari [...] Format de la ressource électronique : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un arbre couvrant [texte imprimé] / Bensedira,meriem ; GUELLATI, N, Directeur de thèse . - [S.l.] : Setif:UFA, 2016 . - 1 vol (55f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
Systèmes répartis
tolérance aux pannes
auto-stabilisation
arbres couvrantsIndex. décimale : 004 Informatique Résumé : Résumé
Les systèmes distribués sont particulièrement sujets à des pannes, lorsqu’on augmente le nombre de processeurs de tels systèmes, la possibilité que ces composants tombent en panne va être également élevée, l’auto-stabilisation est l’une des techniques de tolérance aux pannes
particulièrement les pannes transitoires.
En 1973, E.W. Dijkstra a définit l’auto-stabilisation comme la propriété pour un système de se retrouver lui-même dans un comportement correct en un nombre fini d’étapes, et ce, quel que soit son état initial. L’auto-stabilisation constitue donc un moyen efficace pour tolérer les pannes transitoires.
Notre étude a pour objectif alors de transformer et implémenter un algorithme autostabilisant permettant à un ensemble de nœuds d’un réseau, en démarrant d’une configuration
quelconque, d’arriver à une configuration correct, dite légitime, après un temps fini en
utilisant le modèle de communication par échange de messages.Note de contenu : Table des matières
INTRODUCTION GENERALE .......................................................................... 1
Chapitre 1: Systèmes distribués et auto-stabilisation
1.1 INTRODUCTION............................................................................................. 4
1.2 SYSTEMES DISTRIBUES ............................................................................................. 4
1.2.1 OBJECTIFS DES SYSTEMES DISTRIBUES ............................................................................. 5
1.2.2 LES MODES DE COMMUNICATIONS................................................................................ 5
1.2.3 ALGORITHMES DISTRIBUES ........................................................................................... 7
1.2.3.1 Problèmes classiques en algorithmique distribuée ....................................................................... 8
1.2.3.1.1 Les problèmes statiques............................................................................... 8
1.2.3.1.2 Les problèmes dynamiques ....................................................................... 8
1.2.3.2 Topologies classiques .................................................................................. 9
1.2.4 TOLERANCE AUX PANNES................................................................................. 9
1.2.4.1 Classification des pannes............................................................................. 10
1.2.4.2 Tolérance classique aux pannes ................................................................... 10
1.2.4.3 L’auto-stabilisation : ............................................................................. 11
1.2.4.3.1 Token-ring de Dijkstra...................................................................... 12
1.2.4.3.2 Définitions formelles........................................................................ 15
1.2.4.4 Atomicité :..................................................................................... 17
1.2.4.5 Démon :...................................................................................... 17
1.2.4.6 Complexité ............................................................................ 18
1.3. CONCLUSION .................................................19
Chapitre 2: Etat de l'art sur les algorithmes auto-stabilisants de calcul d'arbres couvrants
2.1 INTRODUCTION..................................................................................... 21
2.2 DEFINITIONS .......................................................................................... 21
2.3 ARBRES COUVRANTS ET PLUS COURT CHEMIN DANS LES SYSTEMES DISTRIBUES . 22
2.4 ALGORITHMES UTILISANT UN MODELE DE COMMUNICATION PAR MEMOIRE PARTAGEE ............................................ 23
2.4.1 ALGORITHMES UTILISANT UN DEMON CENTRALISE .............................................................................. 23
2.4.1.1 Algorithme de Huang et Chen.................................................................................... 23
2.4.1.2 Algorithme de Dolev, Israeli et Moran ......................................................................... 23
2.4.1.3 Algorithme de Dolev ......................................................................................... 24
2.4.1.4 Algorithme de Afek............................................................................................. 26
2.4.1.5 Algorithme de T.C.Huang ....................................................................................... 26
2.4.1.6 Algorithme de Lélia Blin...................................................................................... 28
2.4.1.7 Algorithme de Lélia Blin.................................................................................. 29
2.4.2 ALGORITHMES UTILISANT UN DEMON DISTRIBUE .................................................................. 31
2.4.2.1 Algorithme de Lavallé............................................................................... 31
2.4.2.2 Algorithme de T.C. Huang ................................................................................ 32
2.4.2.3 Algorithme de Lélia Blin.................................................................................. 34
2.5 ALGORITHMES UTILISANT UN MODELE DE COMMUNICATION PAR ECHANGE DE MESSAGES............................................. 35
2.5.1 ALGORITHME DE GUPTA ET SRIMANI .............................................................................. 35
6. CONCLUSION.............................................................................................. 36
Chapitre 3: conception et implémentation
3.1 INTRODUCTION....................................................................................... 38
3.2 TRANSFORMATION DE L’ALGORITHME AUTO-STABILISANT........................................... 38
3.2.1 LANGAGE DE PROGRAMMATION ET ENVIRONNEMENT..................................................................... 40
3.2.2 PRESENTATION DE L’ALGORITHME :............................................................................... 41
3.3 CONCEPTION ..................................................................................................... 43
3.3.1 SPECIFICATION INFORMELLE DES BESOINS ...................................................................... 43
3.3.2 MODELISATION ................................................................................................. 44
3.3.2.1 Modélisation des interactions..................................................................................... 44
3.3.2.2 Modélisation de la sémantique .............................................................................. 49
3.3.2.3 Modélisation de la structure ................................................................................... 49
3.4 SIMULATION D’UNE PANNE TRANSITOIRE .............................................................................. 50
3.5 CONCLUSION ......................................................................................................... 53
CONCLUSION GENERALE ................................................................................................ 54Côte titre : MAI/0135 En ligne : https://drive.google.com/file/d/1WDqzdpT3X98n5_y74vwIY9_Yq80iLFbX/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0135 MAI/0135 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un arbre couvrant Type de document : texte imprimé Auteurs : Daikh, issam ; GUELLATI, N, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (43f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
auto-stabilisation
arbre couvrant
système distribué
panneIndex. décimale : 004 Informatique Résumé : Résumé
Dans le contexte des réseaux a grande échelle, la prise en compte des pannes est une
nécessité évidente. Ce document s’intéresse a l’approche auto-stabilisante qui vise a
concevoir des algorithmes se réparant d’eux-même en cas de pannes transitoires. Dans
la littérature de l’auto-stabilisation, La structure de communication la plus utilisée est
souvent un arbre couvrant. La construction d’arbres couvrants participe a la résolution
de nombreux problèmes fondamentaux de l’algorithmique distribué. ce mémoire porte
plus particulièrement sur l’auto-stabilisation d’algorithmes distribués construisant des
structures couvrantes d’un système distribué.
Un grand nombre d’algorithmes auto-stabilisants pour la construction d’arbres couvrants
ont été proposés dans la littérature. Dans notre travail nous avons choisi un algorithme
et transformé du modèle théorique (hypothèses fortes) vers un modèle implémentable
(hypothèses réalistes), l’algorithme est implémenté sous JAVA en utilisant les sockets.Note de contenu : Table des matières
Introduction générale 1
1 Systèmes distribués et Auto-Stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Objectifs des systèmes distribués . . . . . . . . . . . . . . . . . . 4
1.2.2 Algorithmes distribués . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Modèle de communication . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Auto stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Token ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.2 Avantages de l’auto-stabilisation . . . . . . . . . . . . . . . . . . 11
1.3.3 Limites de l’auto-stabilisation . . . . . . . . . . . . . . . . . . . . 11
1.3.4 Démons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Algorithmes auto-stabilisants et arbres couvrants 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Arbres couvrants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Arbres couvrants de poids minimum (MST) . . . . . . . . . . . . 14
2.2.2 Arbre de Steiner . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Arbre couvrant de plus court chemin . . . . . . . . . . . . . . . . 16
2.3 Algorithmes auto-stabilisants . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1 Algorithme de NS Chen et Shing-Tsaan Huang . . . . . . . . . . 18
2.3.2 Algorithme de Sumit Sur et Pradip K Srimani . . . . . . . . . . . 19
2.3.3 Algorithme de Gheorghe Antonoiu et Pradip K Srimani . . . . . 21
2.3.4 Algorithme de S.Dolev, A.Israeli, S.Moran . . . . . . . . . . . . . 22
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Construction d’arbre couvrant auto-stabilisante 25
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Architecture Générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.1 Diagramme de classe . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.2 Diagrammes des séquences . . . . . . . . . . . . . . . . . . . . . 29
3.4.3 Diagramme états-transitions . . . . . . . . . . . . . . . . . . . . . 32
3.5 Environnement de développement . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Choix du langage de programmation . . . . . . . . . . . . . . . . . . . . 32
3.7 Explication de la partie programmation de l’algorithme . . . . . . . . . . 32
3.8 Aperçu de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Conclusion générale 41
Bibliography 43
Résumé 44Côte titre : MAI/0153 En ligne : https://drive.google.com/file/d/14nh0-KxaeKVP-YGGRLuOhkjQwhKR1WwG/view?usp=shari [...] Format de la ressource électronique : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un arbre couvrant [texte imprimé] / Daikh, issam ; GUELLATI, N, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (43f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
auto-stabilisation
arbre couvrant
système distribué
panneIndex. décimale : 004 Informatique Résumé : Résumé
Dans le contexte des réseaux a grande échelle, la prise en compte des pannes est une
nécessité évidente. Ce document s’intéresse a l’approche auto-stabilisante qui vise a
concevoir des algorithmes se réparant d’eux-même en cas de pannes transitoires. Dans
la littérature de l’auto-stabilisation, La structure de communication la plus utilisée est
souvent un arbre couvrant. La construction d’arbres couvrants participe a la résolution
de nombreux problèmes fondamentaux de l’algorithmique distribué. ce mémoire porte
plus particulièrement sur l’auto-stabilisation d’algorithmes distribués construisant des
structures couvrantes d’un système distribué.
Un grand nombre d’algorithmes auto-stabilisants pour la construction d’arbres couvrants
ont été proposés dans la littérature. Dans notre travail nous avons choisi un algorithme
et transformé du modèle théorique (hypothèses fortes) vers un modèle implémentable
(hypothèses réalistes), l’algorithme est implémenté sous JAVA en utilisant les sockets.Note de contenu : Table des matières
Introduction générale 1
1 Systèmes distribués et Auto-Stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Objectifs des systèmes distribués . . . . . . . . . . . . . . . . . . 4
1.2.2 Algorithmes distribués . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Modèle de communication . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Auto stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Token ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.2 Avantages de l’auto-stabilisation . . . . . . . . . . . . . . . . . . 11
1.3.3 Limites de l’auto-stabilisation . . . . . . . . . . . . . . . . . . . . 11
1.3.4 Démons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Algorithmes auto-stabilisants et arbres couvrants 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Arbres couvrants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Arbres couvrants de poids minimum (MST) . . . . . . . . . . . . 14
2.2.2 Arbre de Steiner . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Arbre couvrant de plus court chemin . . . . . . . . . . . . . . . . 16
2.3 Algorithmes auto-stabilisants . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1 Algorithme de NS Chen et Shing-Tsaan Huang . . . . . . . . . . 18
2.3.2 Algorithme de Sumit Sur et Pradip K Srimani . . . . . . . . . . . 19
2.3.3 Algorithme de Gheorghe Antonoiu et Pradip K Srimani . . . . . 21
2.3.4 Algorithme de S.Dolev, A.Israeli, S.Moran . . . . . . . . . . . . . 22
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Construction d’arbre couvrant auto-stabilisante 25
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Architecture Générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.1 Diagramme de classe . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.2 Diagrammes des séquences . . . . . . . . . . . . . . . . . . . . . 29
3.4.3 Diagramme états-transitions . . . . . . . . . . . . . . . . . . . . . 32
3.5 Environnement de développement . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Choix du langage de programmation . . . . . . . . . . . . . . . . . . . . 32
3.7 Explication de la partie programmation de l’algorithme . . . . . . . . . . 32
3.8 Aperçu de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Conclusion générale 41
Bibliography 43
Résumé 44Côte titre : MAI/0153 En ligne : https://drive.google.com/file/d/14nh0-KxaeKVP-YGGRLuOhkjQwhKR1WwG/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0153 MAI/0153 Mémoire Bibliothéque des sciences Français Disponible
DisponibleImplémentation d'un algorithme auto-stabilisant pour le calcul d'un ensemble indépendant en utilisant la communication par messages / Bessou, mouhamed
Titre : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un ensemble indépendant en utilisant la communication par messages Type de document : texte imprimé Auteurs : Bessou, mouhamed ; GUELLATI, N, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (50f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
systèmes distribués
toléranceauxpannes
auto-stabilisation
clustering
ensemble indépendant maximalIndex. décimale : 004 Informatique Résumé : Résumé
Les progrès remarquables des équipements informatiques et de télécommunications durant ces dernières années ont permis une forte évolution de l'environnement distribué qui
les utilise. On est ainsi passé de réseaux locaux de stations de travail à des réseaux Ã
grande échelle. Cette avancée des équipements a permis de répondre plus ecacement aux
besoins des diérents domaines. La tolérance aux pannes dans les systèmes distribués est
un sujet qui a été largement étudié. La tolérance aux pannes fait référence à la capacité
d'un système de continuer à fonctionner lorsqu'une partie de celui-ci tombe en panne. Une
des solutions proposées pour la tolérance aux pannes est l'auto-stabilisation.
Ce mémoire étudie les algorithmes auto-stabilisants dans le cadre des systèmes distribués. Elle s'intéresse plus particulièrement à l'implémentation de ces algorithmes dans les
réseaux réels.
Dans la première partie, nous présentons le domaine des systèmes distribués, nous citons
leurs objectifs et les types des pannes qui les menaces. Nous présentons aussi l'approche
de l'auto-stabilisation en citons quelques-unes de ses avantages et ses limites.
Dans la deuxième partie, nous présentons les réseaux ad hoc, le clustering dans les
réseaux ad hoc et nous présentons aussi les ensembles indépendants en citons leur utilité
dans les réseaux. Nous terminons cette partie par la présentation de quelques algorithmes
auto-stabilisants permettant de calculés les ensembles indépendants maximaux.
Dans la troisième partie, nous essayons de surpasser les hypothèses fortes des algorithmes auto-stabilisants, pour cela nous proposons une solution pour utiliser l'algorithme
auto-stabilisant d'Ikeda dans un réseau réel. Finalement nous l'implémentons en langage
Java en utilisant les sockets.
Note de contenu : Table des matières
Introduction générale 1
1 Systèmes Distribués et Auto-Stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Objectifs des systèmes distribués . . . . . . . . . . . . . . . . 4
1.2.2 Algorithme distribué . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Problème classique en algorithmique distribuée . . . . . . . . 5
1.3 Modèles de communications . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Tolérance au panne . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Auto Stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.1 Token ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . 9
1.5.2 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.3 Inconvénients . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.4 Démon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Le clustering dans les réseaux ad-hoc et les ensembles indépendants 14
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Réseau ad hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1 La communication dans les réseaux ad hoc . . . . . . . . . . 15
2.2.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Formation de clusters . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.4 Élection de cluster-head . . . . . . . . . . . . . . . . . . . . . 17
2.2.5 Maintenance des clusters . . . . . . . . . . . . . . . . . . . . . 17
2.2.6 Quelques approches de Clustering . . . . . . . . . . . . . . . . 17
2.3 Etat de l'art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Les ensembles indépendants . . . . . . . . . . . . . . . . . . . 18
2.3.2 L'utilisation des ensembles indépendants maximaux (MIS) dans
le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.3 Algorithme de Shukla et al . . . . . . . . . . . . . . . . . . . . 19
2.3.4 Algorithme de Shi et al . . . . . . . . . . . . . . . . . . . . . . 20
2.3.5 Algorithme d'Ikeda et al . . . . . . . . . . . . . . . . . . . . . 21
2.3.6 Algorithme de Turau . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.7 Algorithme de Goddard et al . . . . . . . . . . . . . . . . . . 23
2.3.8 Algorithme de Yen et Huang . . . . . . . . . . . . . . . . . . . 23
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 Implémentation de l'algorithme d'Ikeda dans un réseau réel 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Proposition d'une solution pour l'utilisation de l'algorithme d'Ikeda
dans les réseaux réels . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Algorithme d'Ikeda et al . . . . . . . . . . . . . . . . . . . . . 27
3.2.2 Algorithme transformé . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Description de notre travail . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.1 Modélisation avec UML . . . . . . . . . . . . . . . . . . . . . 30
3.4 Description du code Java . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.1 Le language Java . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.2 Socket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.3 La classe ServeurdeNom . . . . . . . . . . . . . . . . . . . . . 36
3.4.4 La classe Résultat . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.5 Classe InfoVoisin . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.6 Classe N÷ud . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Description de l'application . . . . . . . . . . . . . . . . . . . . . . . 41
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Conclusion générale 46Côte titre : MAI/0167 En ligne : https://drive.google.com/file/d/1OksvpU1oZBqDtH_YvMgebD-KIYf8bper/view?usp=shari [...] Format de la ressource électronique : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un ensemble indépendant en utilisant la communication par messages [texte imprimé] / Bessou, mouhamed ; GUELLATI, N, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (50f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
systèmes distribués
toléranceauxpannes
auto-stabilisation
clustering
ensemble indépendant maximalIndex. décimale : 004 Informatique Résumé : Résumé
Les progrès remarquables des équipements informatiques et de télécommunications durant ces dernières années ont permis une forte évolution de l'environnement distribué qui
les utilise. On est ainsi passé de réseaux locaux de stations de travail à des réseaux Ã
grande échelle. Cette avancée des équipements a permis de répondre plus ecacement aux
besoins des diérents domaines. La tolérance aux pannes dans les systèmes distribués est
un sujet qui a été largement étudié. La tolérance aux pannes fait référence à la capacité
d'un système de continuer à fonctionner lorsqu'une partie de celui-ci tombe en panne. Une
des solutions proposées pour la tolérance aux pannes est l'auto-stabilisation.
Ce mémoire étudie les algorithmes auto-stabilisants dans le cadre des systèmes distribués. Elle s'intéresse plus particulièrement à l'implémentation de ces algorithmes dans les
réseaux réels.
Dans la première partie, nous présentons le domaine des systèmes distribués, nous citons
leurs objectifs et les types des pannes qui les menaces. Nous présentons aussi l'approche
de l'auto-stabilisation en citons quelques-unes de ses avantages et ses limites.
Dans la deuxième partie, nous présentons les réseaux ad hoc, le clustering dans les
réseaux ad hoc et nous présentons aussi les ensembles indépendants en citons leur utilité
dans les réseaux. Nous terminons cette partie par la présentation de quelques algorithmes
auto-stabilisants permettant de calculés les ensembles indépendants maximaux.
Dans la troisième partie, nous essayons de surpasser les hypothèses fortes des algorithmes auto-stabilisants, pour cela nous proposons une solution pour utiliser l'algorithme
auto-stabilisant d'Ikeda dans un réseau réel. Finalement nous l'implémentons en langage
Java en utilisant les sockets.
Note de contenu : Table des matières
Introduction générale 1
1 Systèmes Distribués et Auto-Stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Objectifs des systèmes distribués . . . . . . . . . . . . . . . . 4
1.2.2 Algorithme distribué . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Problème classique en algorithmique distribuée . . . . . . . . 5
1.3 Modèles de communications . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Tolérance au panne . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Auto Stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.1 Token ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . 9
1.5.2 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.3 Inconvénients . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.4 Démon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Le clustering dans les réseaux ad-hoc et les ensembles indépendants 14
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Réseau ad hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1 La communication dans les réseaux ad hoc . . . . . . . . . . 15
2.2.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Formation de clusters . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.4 Élection de cluster-head . . . . . . . . . . . . . . . . . . . . . 17
2.2.5 Maintenance des clusters . . . . . . . . . . . . . . . . . . . . . 17
2.2.6 Quelques approches de Clustering . . . . . . . . . . . . . . . . 17
2.3 Etat de l'art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Les ensembles indépendants . . . . . . . . . . . . . . . . . . . 18
2.3.2 L'utilisation des ensembles indépendants maximaux (MIS) dans
le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.3 Algorithme de Shukla et al . . . . . . . . . . . . . . . . . . . . 19
2.3.4 Algorithme de Shi et al . . . . . . . . . . . . . . . . . . . . . . 20
2.3.5 Algorithme d'Ikeda et al . . . . . . . . . . . . . . . . . . . . . 21
2.3.6 Algorithme de Turau . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.7 Algorithme de Goddard et al . . . . . . . . . . . . . . . . . . 23
2.3.8 Algorithme de Yen et Huang . . . . . . . . . . . . . . . . . . . 23
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 Implémentation de l'algorithme d'Ikeda dans un réseau réel 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Proposition d'une solution pour l'utilisation de l'algorithme d'Ikeda
dans les réseaux réels . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Algorithme d'Ikeda et al . . . . . . . . . . . . . . . . . . . . . 27
3.2.2 Algorithme transformé . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Description de notre travail . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.1 Modélisation avec UML . . . . . . . . . . . . . . . . . . . . . 30
3.4 Description du code Java . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.1 Le language Java . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.2 Socket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.3 La classe ServeurdeNom . . . . . . . . . . . . . . . . . . . . . 36
3.4.4 La classe Résultat . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.5 Classe InfoVoisin . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.6 Classe N÷ud . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Description de l'application . . . . . . . . . . . . . . . . . . . . . . . 41
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Conclusion générale 46Côte titre : MAI/0167 En ligne : https://drive.google.com/file/d/1OksvpU1oZBqDtH_YvMgebD-KIYf8bper/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0167 MAI/0167 Mémoire Bibliothéque des sciences Français Disponible
DisponibleImplémentation d'un algorithme de Data Mining dans le modèle de programmation MapReduce / Bensedira, Ayoub
Titre : Implémentation d'un algorithme de Data Mining dans le modèle de programmation MapReduce Type de document : texte imprimé Auteurs : Bensedira, Ayoub, Auteur ; Nasri,Khaled, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (69 f .) Format : 29 cm Langues : Français (fre) Langues originales : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Big Data
Data Mining
Hadoop
MapReduceIndex. décimale : 004 Informatique Résumé : Résumé
Les données sont devenues aujourd'hui le nouveau champ de bataille concurrentielle
entre les entreprises, notamment avec la prolifération massive des données dans
un contexte Big Data où l'intégration des données en tant qu'une discipline s'impose
de plus en plus comme un dé opérationnel majeur et inédit.
Le datamining est déni comme étant le processus d'extraction de connaissances
à partir de grandes masses de données, il est utilisé dans plusieurs domaines :
médecine, marketing, industrie, recherche opérationnelle entre autres.
Plusieurs entreprises pionnières et chercheurs dans le domaine commencent à faire
face à ce dé de taille par la proposition de nouvelles approches conceptuelles et algorithmiques
an de remédier à cette problématique imposée par un environnement
extérieur émouvant, des approches qui prennent en considération la monté en puissance
et en popularité des réseaux sociaux, Internet Of Things (IoT) et les analyses
Big Data.
Des débats intensifs se sont orientés et concentrés sur la pertinence des anciennes
méthodes traditionnelles et l'introduction de nouvelles méthodes plus exibles
qui s'adaptent à la vélocité, variété et volume des données qui parviennent de
l'environnement. A traves ce projets nous voulons répondre à un certain nombre de
problématiques tel que :
Quels sont les outils et les techniques utilisées dans le domaine de Big Data
pour analyser les données et extraire des connaissances.
Comment introduire la notion de parallélisme pour implémenter un algorithmes
de Data Mining selon le modèle de programmation MapReduce.Note de contenu : Sommaire
Abstract i
Acknowledgement iii
Contents iv
List of Figures vii
Introduction 1
1 Objective: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1 Big Data 3
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Data Evolution: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3 Denitions of Big Data: . . . . . . . . . . . . . . . . . . . . . . . . . 4
4 Sources of Big Data: . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5 Big Data Vs small data: . . . . . . . . . . . . . . . . . . . . . . . . . 7
6 Data structure: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.1 Structured: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.2 Semi-structured: . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.3 Quasi-structured: . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.4 Unstructured: . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
6.5 Combination of the Four Groups: . . . . . . . . . . . . . . . . 9
7 Big Data ecosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
8 Big Data Lifecycle: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
8.1 Data collection phase . . . . . . . . . . . . . . . . . . . . . . . 12
8.2 Data storage phase: . . . . . . . . . . . . . . . . . . . . . . . . 13
8.3 Data analytics phase: . . . . . . . . . . . . . . . . . . . . . . 13
8.4 Knowledge creation phase: . . . . . . . . . . . . . . . . . . . . 13
9 Data scientists: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
10 Big Data and related technologies: . . . . . . . . . . . . . . . . . . . . 15
10.1 Hadoop: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
10.1.1 Hadoop architecture: . . . . . . . . . . . . . . . . . . 16
10.1.1.1 HDFS (Hadoop Distributed File System): . . . . . . 16
10.1.1.2 MapReduce: . . . . . . . . . . . . . . . . . . . . . . . 17
10.2 Cloud Computing: . . . . . . . . . . . . . . . . . . . . . . . . 19
10.3 NoSQL: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
11 Big Data applications: . . . . . . . . . . . . . . . . . . . . . . . . . . 22
12 Challenges of Big Data: . . . . . . . . . . . . . . . . . . . . . . . . . 23
13 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2 Data Mining in Big Data 26
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2 Data Mining overview: . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 Data Mining denition: . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4 Machine learning: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5 Machine Learning techniques: . . . . . . . . . . . . . . . . . . . . . . 29
5.1 Supervised Learning: . . . . . . . . . . . . . . . . . . . . . . . 30
5.2 Unsupervised Learning: . . . . . . . . . . . . . . . . . . . . . . 30
5.3 Reinforcement Learning: . . . . . . . . . . . . . . . . . . . . . 31
6 Machine Learning process: . . . . . . . . . . . . . . . . . . . . . . . . 31
7 Literature review: Data mining in Big Data . . . . . . . . . . . . . . 32
8 Conclusion: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3 Deep Learning for Big Data 35
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2 Deep Learning: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3 Train Deep Learning: . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1 Regularization: . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Weight initialization: . . . . . . . . . . . . . . . . . . . . . . . 37
3.3 Activation function: . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Loss function: . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.5 Backpropagation: . . . . . . . . . . . . . . . . . . . . . . . . . 39
4 Deep Architectures: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.1 Feed forward neural networks: . . . . . . . . . . . . . . . . . . 40
4.2 Convolutional neural networks: . . . . . . . . . . . . . . . . . 40
4.3 Recurrent neural networks: . . . . . . . . . . . . . . . . . . . . 42
5 Deep learning and big data: . . . . . . . . . . . . . . . . . . . . . . . 43
5.1 Challenges: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.2 Some recent work: Deep learning in big data . . . . . . . . . . 45
6 Conclusion: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4 Realized Work 47
1 Introduction: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2 Proposed Architecture: . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3 Implementation Environment: . . . . . . . . . . . . . . . . . . . . . . 48
3.1 Jupyter Notebook: . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 Python 2.7: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3 Keras backend TensorFlow: . . . . . . . . . . . . . . . . . . . 49
3.4 h5py: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5 Hadoop 2.8.4: . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5.1 Hadoop Streaming: . . . . . . . . . . . . . . . . . . . 50
3.5.2 Installation and conguration of Hadoop: . . . . . . 51
4 Dataset: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5 Building the Model: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6 MapReduce test and evaluation: . . . . . . . . . . . . . . . . . . . . . 60
6.1 Prepare data: . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.2 Upload CSV le to HDFS: . . . . . . . . . . . . . . . . . . . . 60
6.3 MapReduce code in python: . . . . . . . . . . . . . . . . . . . 61
6.3.1 Mapper: . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.3.2 Reducer: . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.4 Run the MapReduce job: . . . . . . . . . . . . . . . . . . . . . 63
7 Conclusion: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Conclusion 64
Bibliography 66Côte titre : MAI/0266 En ligne : https://drive.google.com/file/d/1eqC_-rS8sX7jpUH4A3vdgJserTuUGgX4/view?usp=shari [...] Format de la ressource électronique : Implémentation d'un algorithme de Data Mining dans le modèle de programmation MapReduce [texte imprimé] / Bensedira, Ayoub, Auteur ; Nasri,Khaled, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (69 f .) ; 29 cm.
Langues : Français (fre) Langues originales : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Big Data
Data Mining
Hadoop
MapReduceIndex. décimale : 004 Informatique Résumé : Résumé
Les données sont devenues aujourd'hui le nouveau champ de bataille concurrentielle
entre les entreprises, notamment avec la prolifération massive des données dans
un contexte Big Data où l'intégration des données en tant qu'une discipline s'impose
de plus en plus comme un dé opérationnel majeur et inédit.
Le datamining est déni comme étant le processus d'extraction de connaissances
à partir de grandes masses de données, il est utilisé dans plusieurs domaines :
médecine, marketing, industrie, recherche opérationnelle entre autres.
Plusieurs entreprises pionnières et chercheurs dans le domaine commencent à faire
face à ce dé de taille par la proposition de nouvelles approches conceptuelles et algorithmiques
an de remédier à cette problématique imposée par un environnement
extérieur émouvant, des approches qui prennent en considération la monté en puissance
et en popularité des réseaux sociaux, Internet Of Things (IoT) et les analyses
Big Data.
Des débats intensifs se sont orientés et concentrés sur la pertinence des anciennes
méthodes traditionnelles et l'introduction de nouvelles méthodes plus exibles
qui s'adaptent à la vélocité, variété et volume des données qui parviennent de
l'environnement. A traves ce projets nous voulons répondre à un certain nombre de
problématiques tel que :
Quels sont les outils et les techniques utilisées dans le domaine de Big Data
pour analyser les données et extraire des connaissances.
Comment introduire la notion de parallélisme pour implémenter un algorithmes
de Data Mining selon le modèle de programmation MapReduce.Note de contenu : Sommaire
Abstract i
Acknowledgement iii
Contents iv
List of Figures vii
Introduction 1
1 Objective: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1 Big Data 3
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Data Evolution: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3 Denitions of Big Data: . . . . . . . . . . . . . . . . . . . . . . . . . 4
4 Sources of Big Data: . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5 Big Data Vs small data: . . . . . . . . . . . . . . . . . . . . . . . . . 7
6 Data structure: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.1 Structured: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.2 Semi-structured: . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.3 Quasi-structured: . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.4 Unstructured: . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
6.5 Combination of the Four Groups: . . . . . . . . . . . . . . . . 9
7 Big Data ecosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
8 Big Data Lifecycle: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
8.1 Data collection phase . . . . . . . . . . . . . . . . . . . . . . . 12
8.2 Data storage phase: . . . . . . . . . . . . . . . . . . . . . . . . 13
8.3 Data analytics phase: . . . . . . . . . . . . . . . . . . . . . . 13
8.4 Knowledge creation phase: . . . . . . . . . . . . . . . . . . . . 13
9 Data scientists: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
10 Big Data and related technologies: . . . . . . . . . . . . . . . . . . . . 15
10.1 Hadoop: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
10.1.1 Hadoop architecture: . . . . . . . . . . . . . . . . . . 16
10.1.1.1 HDFS (Hadoop Distributed File System): . . . . . . 16
10.1.1.2 MapReduce: . . . . . . . . . . . . . . . . . . . . . . . 17
10.2 Cloud Computing: . . . . . . . . . . . . . . . . . . . . . . . . 19
10.3 NoSQL: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
11 Big Data applications: . . . . . . . . . . . . . . . . . . . . . . . . . . 22
12 Challenges of Big Data: . . . . . . . . . . . . . . . . . . . . . . . . . 23
13 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2 Data Mining in Big Data 26
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2 Data Mining overview: . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 Data Mining denition: . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4 Machine learning: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5 Machine Learning techniques: . . . . . . . . . . . . . . . . . . . . . . 29
5.1 Supervised Learning: . . . . . . . . . . . . . . . . . . . . . . . 30
5.2 Unsupervised Learning: . . . . . . . . . . . . . . . . . . . . . . 30
5.3 Reinforcement Learning: . . . . . . . . . . . . . . . . . . . . . 31
6 Machine Learning process: . . . . . . . . . . . . . . . . . . . . . . . . 31
7 Literature review: Data mining in Big Data . . . . . . . . . . . . . . 32
8 Conclusion: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3 Deep Learning for Big Data 35
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2 Deep Learning: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3 Train Deep Learning: . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1 Regularization: . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Weight initialization: . . . . . . . . . . . . . . . . . . . . . . . 37
3.3 Activation function: . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Loss function: . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.5 Backpropagation: . . . . . . . . . . . . . . . . . . . . . . . . . 39
4 Deep Architectures: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.1 Feed forward neural networks: . . . . . . . . . . . . . . . . . . 40
4.2 Convolutional neural networks: . . . . . . . . . . . . . . . . . 40
4.3 Recurrent neural networks: . . . . . . . . . . . . . . . . . . . . 42
5 Deep learning and big data: . . . . . . . . . . . . . . . . . . . . . . . 43
5.1 Challenges: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.2 Some recent work: Deep learning in big data . . . . . . . . . . 45
6 Conclusion: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4 Realized Work 47
1 Introduction: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2 Proposed Architecture: . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3 Implementation Environment: . . . . . . . . . . . . . . . . . . . . . . 48
3.1 Jupyter Notebook: . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 Python 2.7: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3 Keras backend TensorFlow: . . . . . . . . . . . . . . . . . . . 49
3.4 h5py: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5 Hadoop 2.8.4: . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5.1 Hadoop Streaming: . . . . . . . . . . . . . . . . . . . 50
3.5.2 Installation and conguration of Hadoop: . . . . . . 51
4 Dataset: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5 Building the Model: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6 MapReduce test and evaluation: . . . . . . . . . . . . . . . . . . . . . 60
6.1 Prepare data: . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.2 Upload CSV le to HDFS: . . . . . . . . . . . . . . . . . . . . 60
6.3 MapReduce code in python: . . . . . . . . . . . . . . . . . . . 61
6.3.1 Mapper: . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.3.2 Reducer: . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.4 Run the MapReduce job: . . . . . . . . . . . . . . . . . . . . . 63
7 Conclusion: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Conclusion 64
Bibliography 66Côte titre : MAI/0266 En ligne : https://drive.google.com/file/d/1eqC_-rS8sX7jpUH4A3vdgJserTuUGgX4/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0266 MAI/0266 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Implémentation d'un nouveau schéma de émentation d'un nouveau schéma Type de document : texte imprimé Auteurs : Khaled bennoui, Auteur ; Abdelmounaime zebbache, Auteur ; Kharchi ,Samia, Directeur de thèse Année de publication : 2022 Importance : 1 vol (68 f .) Format : 29cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : AES, boite blanche
s-BoxIndex. décimale : 004 Informatique Résumé :
L’objectif général de la cryptographie est de sécuriser les donnes échangées mais les données pendant l’exécution ne le sont pas, alors la cryptographie en boite blanche est apparue pour assurer cette fonction.
Nous avons proposé une nouvelle fonction de chiffrement basée sur l’AES afin de modifier les donnes pendant l’exécution normale de l’AES. Cette fonction consiste à créer une nouvelle S-Box inconnue pour un intrus et la fonction de permutation dans le résultat intermédiaire. L’implémentation de notre fonction a permis de voir la différence entre les résultats obtenus par AES classique et AES +, à l’aide de fonction Hamming.Côte titre : MAI/0641 En ligne : https://drive.google.com/file/d/1gsMKFh1t6Kag8TtmdbWGyGzj9gLa2XM2/view?usp=share [...] Format de la ressource électronique : Implémentation d'un nouveau schéma de émentation d'un nouveau schéma [texte imprimé] / Khaled bennoui, Auteur ; Abdelmounaime zebbache, Auteur ; Kharchi ,Samia, Directeur de thèse . - 2022 . - 1 vol (68 f .) ; 29cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : AES, boite blanche
s-BoxIndex. décimale : 004 Informatique Résumé :
L’objectif général de la cryptographie est de sécuriser les donnes échangées mais les données pendant l’exécution ne le sont pas, alors la cryptographie en boite blanche est apparue pour assurer cette fonction.
Nous avons proposé une nouvelle fonction de chiffrement basée sur l’AES afin de modifier les donnes pendant l’exécution normale de l’AES. Cette fonction consiste à créer une nouvelle S-Box inconnue pour un intrus et la fonction de permutation dans le résultat intermédiaire. L’implémentation de notre fonction a permis de voir la différence entre les résultats obtenus par AES classique et AES +, à l’aide de fonction Hamming.Côte titre : MAI/0641 En ligne : https://drive.google.com/file/d/1gsMKFh1t6Kag8TtmdbWGyGzj9gLa2XM2/view?usp=share [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0641 MAI/0641 Mémoire Bibliothéque des sciences Français Disponible
DisponibleImplémentation d’une nouvelle primitive cryptographique au service des signatures anonymes / Nassim Krache
PermalinkPermalinkPermalinkImplémentation d'un outil d'aide aux études anthroponymiques et onomastiques / AL-Absi Suhail,Abdulaziz
PermalinkImplémentation d’un Protocole de Routage dans Les Réseaux de Capteurs Sans Fil à Base d'un Système de Coordonnées Virtuelles / Amira Keddari
PermalinkPermalinkImplémentation d’un système de cordonnées virtuelles pour le routage dans les réseaux de capteurs sans fil / chaima Makhlouche
PermalinkPermalinkPermalinkInformatique, / Jean-Philippe Préaux
Permalink