University Sétif 1 FERHAT ABBAS Faculty of Sciences
Catégories
Ajouter le résultat dans votre panier Affiner la recherche
Contributions à l'étude de la diagnosticabilité et la prédictibilité des systèmes à événements discrets flous / Benmessahel, Bilal
Titre : Contributions à l'étude de la diagnosticabilité et la prédictibilité des systèmes à événements discrets flous Type de document : texte imprimé Auteurs : Benmessahel, Bilal, Auteur ; Touahria, Mohamed, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (121 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Systémes à événement discrets(SED)
Diagnostic
Pronostic
Diagnosticabilité
Prédictibilité
Systémes à événement discrets(SEDF)Index. décimale : 004 - Informatique Résumé : Résumé :
Cette thèse considère et généralise les études de la diagnosticabilité et la prédictibilité dans les SED
et précisément les SED flou (SEDF). La contribution principale de cette thèse est la proposition de
nouvelles approches de vérification de la prédictibilité dans les SED flou. Premièrement nous avons
formalisé la notion de prédictibilité floue pour les SEDF en introduisant des fonctions de
prédictibilité, ces fonctions quantifient le degré de prédictibilité d'un événement de faute et donnent
une mesure précieuse pour affiner la décision sur la prédictibilité des fautes. Nous avons présenté
aussi une comparaison entre la diagnosticabilité floue et la prédictibilité floue. Ensuite nous avons
proposé une approche basée sur le diagnostiqueur flou. L'inconvénient majeur de notre première
approche est sa complexité exponentielle, cela nous a motivé à proposer une deuxième approche de
complexité polynomiale toujours pour la vérification de la prédictibilité des SEDF appelée "approche
vérificateur". Du point de vue de la complexité du calcul, le nombre d'états dans le vérificateur est
polynomial par rapport au nombre d'états dans le système d'entrée. Finalement, nous avons étendu
l'analyse de la prédictibilité du cadre centralisé au cadre décentralisé, pour cela nous avons proposé
une approche décentralisée pour traiter les cas des systèmes de grande taille.
Côte titre : DI/0035 En ligne : https://drive.google.com/file/d/1f_gtXlNSBKpCqai2daTE45n6AM0v4vRK/view?usp=shari [...] Format de la ressource électronique : Contributions à l'étude de la diagnosticabilité et la prédictibilité des systèmes à événements discrets flous [texte imprimé] / Benmessahel, Bilal, Auteur ; Touahria, Mohamed, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (121 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Systémes à événement discrets(SED)
Diagnostic
Pronostic
Diagnosticabilité
Prédictibilité
Systémes à événement discrets(SEDF)Index. décimale : 004 - Informatique Résumé : Résumé :
Cette thèse considère et généralise les études de la diagnosticabilité et la prédictibilité dans les SED
et précisément les SED flou (SEDF). La contribution principale de cette thèse est la proposition de
nouvelles approches de vérification de la prédictibilité dans les SED flou. Premièrement nous avons
formalisé la notion de prédictibilité floue pour les SEDF en introduisant des fonctions de
prédictibilité, ces fonctions quantifient le degré de prédictibilité d'un événement de faute et donnent
une mesure précieuse pour affiner la décision sur la prédictibilité des fautes. Nous avons présenté
aussi une comparaison entre la diagnosticabilité floue et la prédictibilité floue. Ensuite nous avons
proposé une approche basée sur le diagnostiqueur flou. L'inconvénient majeur de notre première
approche est sa complexité exponentielle, cela nous a motivé à proposer une deuxième approche de
complexité polynomiale toujours pour la vérification de la prédictibilité des SEDF appelée "approche
vérificateur". Du point de vue de la complexité du calcul, le nombre d'états dans le vérificateur est
polynomial par rapport au nombre d'états dans le système d'entrée. Finalement, nous avons étendu
l'analyse de la prédictibilité du cadre centralisé au cadre décentralisé, pour cela nous avons proposé
une approche décentralisée pour traiter les cas des systèmes de grande taille.
Côte titre : DI/0035 En ligne : https://drive.google.com/file/d/1f_gtXlNSBKpCqai2daTE45n6AM0v4vRK/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DI/0035 DI/0035 Thèse Bibliothéque des sciences Français Disponible
DisponibleContributions à la Résolution de l'Emergence Inversée en Utilisant les Métaheuristiques Quantiques / Djemame,Sefia
Titre : Contributions à la Résolution de l'Emergence Inversée en Utilisant les Métaheuristiques Quantiques Type de document : texte imprimé Auteurs : Djemame,Sefia, Auteur ; Batouche, Mohamed, Auteur Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (135 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Système complexe
Automate cellulaire
Emergence inversée
Métaheuristiques
Informatique quantique
Particle swarm optimization
Genetic algorithm
Quantum
Quantum GA
Traitement d'imagesIndex. décimale : 004 Informatique Résumé : Résumé
Les systèmes complexes présentent une propriété intéressante : l'émergence.
Cette propriété est présente dans beaucoup de modèles inspirés de la nature.
Parmi ces modèles : les automates cellulaires, les colonies de fourmis, les syst
èmes multi-agents, les essaims de particules, les réseaux de neurones articiels.
La résolution de l'émergence inversée dans ces systèmes consiste à déterminer les
règles de base qui permettent à un collectif d'individus simples de coopérer et de
produire à un niveau global, une fonction émergente. Dans la littérature, ce probl
ème est qualié de "dicile" et induit d'intenses recherches. Dans cette optique,
nous proposons dans cette thèse trois méthodes de résolution. La première mé-
thode s'appuie sur la métaheuristique PSO, qui guide un processus évolutionnaire
d'automate cellulaire. La validation a été faite à travers l'extraction de contours
sur images. La deuxième méthode utilise les principes de l'informatique quantique
hybridée avec le PSO, à travers la métaheuristique Quantum PSO, pour
tirer prot de la diversication de la population, le parallélisme, et la richesse des
opérateurs quantiques. Ce modèle a été utilisé pour résoudre deux problèmes : la
détection de contours et le ltrage d'images. La troisième méthode est une hybridation
entre l'algorithme génétique et l'informatique quantique. L'algorithme
obtenu a montré une bonne capacité de recherche globale. Un nombre réduit de
chromosomes quantiques a su pour étudier le problème.
Les résultats expérimentaux obtenus par les trois méthodes ont démontré la
grande capacité des métaheuristiques utilisées pour apporter une solution satisfaisante
au problème de l'émergence inversée et assurer une excellente convergence
du système et un bon équilibre entre exploitation et explorationNote de contenu : Sommaire
Table des matières
Liste des gures iv
Liste des tableaux vi
Introduction Générale 1
1 Introduction aux Systèmes Complexes 8
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Systèmes Complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Niveaux de Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Historique et Dénitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.2 Dénitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Classication des Systèmes Complexes : types de complexité . . . . . . . . . . 11
1.4.1 Type 1. Complexité statique . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.2 Type 2. Complexité dynamique . . . . . . . . . . . . . . . . . . . . . . 12
1.4.3 Type 3. Complexité évolutive . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.4 Type 4. Complexité auto-organisatrice . . . . . . . . . . . . . . . . . . 12
1.5 Caractéristiques des Systèmes Complexes . . . . . . . . . . . . . . . . . . . . . 13
1.5.1 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5.2 Changement du niveau d'intégration . . . . . . . . . . . . . . . . . . . 14
1.5.3 Boucles de rétroaction et non-linéarité . . . . . . . . . . . . . . . . . . 14
1.5.4 Indéterminisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.5 Irréversibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.6 Emergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.7 Auto-organisation et systèmes auto-organisés . . . . . . . . . . . . . . . 19
1.5.8 Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.8.1 Système adaptatif . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.9 Apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.5.9.1 Types d'apprentissage . . . . . . . . . . . . . . . . . . . . . . 21
1.5.9.2 Diérence entre apprentissage et adaptation . . . . . . . . . . 21
1.6 Domaines d'application des systèmes complexes . . . . . . . . . . . . . . . . . 22
1.6.1 Biologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.6.2 Sciences sociales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.6.3 Psychologie et neuroscience . . . . . . . . . . . . . . . . . . . . . . . . 23
1.6.4 Economie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6.5 Chimie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6.6 Géologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.6.7 Logistique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.7 Exemples de systèmes complexes naturels et articiels . . . . . . . . . . . . . . 25
1.7.1 Systèmes complexes naturels . . . . . . . . . . . . . . . . . . . . . . . . 26
1.7.1.1 Le tas de sable . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.7.1.2 Les colonies d'insectes sociaux . . . . . . . . . . . . . . . . . . 27
1.7.1.3 Autres exemples naturels . . . . . . . . . . . . . . . . . . . . 28
1.7.2 Systèmes complexes articiels . . . . . . . . . . . . . . . . . . . . . . . 28
1.7.2.1 Systèmes multi-agents . . . . . . . . . . . . . . . . . . . . . . 29
1.7.2.2 Boids de Reynolds . . . . . . . . . . . . . . . . . . . . . . . . 31
1.7.2.3 L'intelligence en essaim . . . . . . . . . . . . . . . . . . . . . 33
1.7.2.4 Les réseaux de neurones . . . . . . . . . . . . . . . . . . . . . 33
1.7.2.5 Les algorithmes évolutionnaires . . . . . . . . . . . . . . . . . 35
1.7.2.6 Les automates cellulaires . . . . . . . . . . . . . . . . . . . . . 36
1.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2 Les Automates Cellulaires 39
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2 Dénitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.1 Dénition générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.2 Dénition formelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.2.1 Naissance des Automates Cellulaires . . . . . . . . . . . . . . 41
2.2.3 Exemples d'Automates Cellulaires . . . . . . . . . . . . . . . . . . . . . 42
2.2.3.1 Automate Cellulaire Elémentaire . . . . . . . . . . . . . . . . 42
2.2.3.2 L'automate cellulaire "Jeu de la Vie" . . . . . . . . . . . . . . 43
2.2.3.3 Exploration des possibilités des AC . . . . . . . . . . . . . . . 44
2.2.4 La classication de Wolfram . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3 Domaines d'Application des Automates Cellulaires . . . . . . . . . . . . . . . 45
2.3.1 Modélisation en Physique . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.2 Codage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.3 Mathématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.4 Électronique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.5 Phénomènes Biologiques . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.3.6 Autres applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4 les Automates Cellulaires en Traitement d'images . . . . . . . . . . . . . . . . 48
2.4.1 Intérêt des AC en traitement d'images . . . . . . . . . . . . . . . . . . 48
2.4.2 Etat de l'art des AC en traitement d'images . . . . . . . . . . . . . . . 48
2.5 Problématique et motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.5.1 Formulation du problème . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.5.2 Problèmes Inverses d'Automates Cellulaires . . . . . . . . . . . . . . . 50
2.5.2.1 Dénitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.5.2.2 Quelques Problèmes Inverses d'Automates Cellulaires . . . . . 52
2.5.3 Approches utilisées dans la littérature . . . . . . . . . . . . . . . . . . . 55
2.5.4 Les Algorithmes Evolutionnaires pour Résoudre l'Emergence Inversée . 55
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3 Métaheuristiques d'Optimisation : Etat de l'Art 57
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2 Les Algorithmes d'Optimisation Approchée . . . . . . . . . . . . . . . . . . . . 58
3.2.1 Heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2.2 Métaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2.3 Les métaheuristiques à solution unique . . . . . . . . . . . . . . . . . . 59
3.2.3.1 Le Recuit Simulé . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2.3.2 L'Algorithme de Recherche Tabou . . . . . . . . . . . . . . . 61
3.2.4 Les métaheuristiques à population de solutions . . . . . . . . . . . . . . 62
3.2.4.1 Les algorithmes évolutionnaires . . . . . . . . . . . . . . . . . 62
3.2.4.2 Les Algorithmes des Colonies de Fourmis . . . . . . . . . . . . 64
3.2.4.3 L'algorithme des colonies d'abeilles articielles (ABC) . . . . 66
3.2.4.4 Les systèmes immunitaires articiels (AIS) . . . . . . . . . . . 66
3.2.4.5 Algorithme à évolution diérentielle . . . . . . . . . . . . . . 68
3.2.4.6 Les algorithmes à estimation de distribution . . . . . . . . . . 68
3.3 L'Optimisation par Essaim de Particules . . . . . . . . . . . . . . . . . . . . . 69
3.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.3.2 Comparaison entre l'algorithme génétique et le PSO . . . . . . . . . . . 70
3.3.3 Domaines d'utilisation du PSO . . . . . . . . . . . . . . . . . . . . . . 71
3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4 L'Informatique Quantique 73
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.2 L'Informatique Quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2.1 Bit Quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2.2 Registre quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.2.3 Les cinq principes de l'informatique quantique . . . . . . . . . . . . . . 75
4.2.4 Calcul quantique et algorithmes quantiques . . . . . . . . . . . . . . . . 77
4.2.5 Avantages et limites de l'informatique quantique . . . . . . . . . . . . . 78
4.3 Algorithmes Evolutionnaires Quantiques . . . . . . . . . . . . . . . . . . . . . 79
4.3.1 Individu quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.2 Mesure quantique d'individus . . . . . . . . . . . . . . . . . . . . . . . 80
4.3.3 La porte D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.3.4 Discussion de l'algorithme évolutionnaire quantique . . . . . . . . . . . 82
4.4 Autres Algorithmes Inspirés du Quantique . . . . . . . . . . . . . . . . . . . . 82
4.4.1 Algorithmes génétiques quantiques . . . . . . . . . . . . . . . . . . . . 83
4.4.2 Boids de Reynolds quantiques . . . . . . . . . . . . . . . . . . . . . . . 84
4.4.3 Réseaux de neurones quantiques . . . . . . . . . . . . . . . . . . . . . . 85
4.5 Avantages des Algorithmes Inspirés du Quantique . . . . . . . . . . . . . . . . 85
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5 Utilisation du PSO puis QPSO pour résoudre le problème d'émergence inversée .......87
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.2 Contribution 1 : Application de la Métaheuristique PSO pour la Résolution de l'Emergence Inversée . . . . . . 87
5.2.1 Format des règles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.2.2 Evolution de l'automate Cellulaire par la métaheuristique PSO . . . . . 89
5.2.3 La fonction Fitness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.2.4 L'algorithme CA-PSO pour la détection de contours . . . . . . . . . . . 90
5.2.5 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.2.5.1 Les meilleures règles obtenues . . . . . . . . . . . . . . . . . . 92
5.2.5.2 Résultats sur images de synthèse . . . . . . . . . . . . . . . . 92
5.2.5.3 Résultats sur image à niveaux de gris . . . . . . . . . . . . . . 93
5.2.5.4 Résultats sur image réelle . . . . . . . . . . . . . . . . . . . . 93
5.2.5.5 Résultats sur image médicale . . . . . . . . . . . . . . . . . . 94
5.2.5.6 Temps d'exécution . . . . . . . . . . . . . . . . . . . . . . . . 94
5.2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.3 Contribution 2 : Utilisation du PSO Quantique pour la résolution de problème inverse . . . . . .. . 95
5.3.1 L'Algorithme Quantum-behaved PSO . . . . . . . . . . . . . . . . . . . 96
5.3.2 L'approche proposée . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.3.3 Les règles de transition . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.4 Réglage de paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.5 Les fonctions tness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.6 L'algorithme QPSO pour la détection de contours . . . . . . . . . . . . 99
5.3.7 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.3.7.1 Meilleur paquet de règles . . . . . . . . . . . . . . . . . . . . 100
5.3.7.2 Résultats visuels . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.3.7.3 Comparaison avec des travaux similaires . . . . . . . . . . . . 101
5.3.8 L'algorithme QPSO pour le ltrage d'images . . . . . . . . . . . . . . . 104
5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6 L'Algorithme Génétique Quantique pour la Résolution de l'Emergence Inversée .....107
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.2 Etat de l'art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.3 Généralités sur le Quantum Genetic Computing . . . . . . . . . . . . . . . . . 109
6.3.1 Principes de l'Algorithme Génétique Quantique . . . . . . . . . . . . . 110
6.3.2 Codage des Chromosomes Quantiques . . . . . . . . . . . . . . . . . . 110
6.3.3 La Mesure des Chromosomes . . . . . . . . . . . . . . . . . . . . . . . 111
6.4 L'Approche Proposée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.5 Résultats Expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.6 Comparaison entre Algorithme Génétique Quantique et Algorithme Génétique Classique . . . . . . . 115
6.6.1 Résultats Numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.6.2 Complexité Algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Conclusion et Perspectives 119
Travaux de l'auteur 121
BibliographieCôte titre : DI/0036 En ligne : https://drive.google.com/file/d/1v48n0zBwSM8vrMsZyUqThjE9MEXQlGn2/view?usp=shari [...] Format de la ressource électronique : Contributions à la Résolution de l'Emergence Inversée en Utilisant les Métaheuristiques Quantiques [texte imprimé] / Djemame,Sefia, Auteur ; Batouche, Mohamed, Auteur . - [S.l.] : Setif:UFA, 2018 . - 1 vol (135 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Système complexe
Automate cellulaire
Emergence inversée
Métaheuristiques
Informatique quantique
Particle swarm optimization
Genetic algorithm
Quantum
Quantum GA
Traitement d'imagesIndex. décimale : 004 Informatique Résumé : Résumé
Les systèmes complexes présentent une propriété intéressante : l'émergence.
Cette propriété est présente dans beaucoup de modèles inspirés de la nature.
Parmi ces modèles : les automates cellulaires, les colonies de fourmis, les syst
èmes multi-agents, les essaims de particules, les réseaux de neurones articiels.
La résolution de l'émergence inversée dans ces systèmes consiste à déterminer les
règles de base qui permettent à un collectif d'individus simples de coopérer et de
produire à un niveau global, une fonction émergente. Dans la littérature, ce probl
ème est qualié de "dicile" et induit d'intenses recherches. Dans cette optique,
nous proposons dans cette thèse trois méthodes de résolution. La première mé-
thode s'appuie sur la métaheuristique PSO, qui guide un processus évolutionnaire
d'automate cellulaire. La validation a été faite à travers l'extraction de contours
sur images. La deuxième méthode utilise les principes de l'informatique quantique
hybridée avec le PSO, à travers la métaheuristique Quantum PSO, pour
tirer prot de la diversication de la population, le parallélisme, et la richesse des
opérateurs quantiques. Ce modèle a été utilisé pour résoudre deux problèmes : la
détection de contours et le ltrage d'images. La troisième méthode est une hybridation
entre l'algorithme génétique et l'informatique quantique. L'algorithme
obtenu a montré une bonne capacité de recherche globale. Un nombre réduit de
chromosomes quantiques a su pour étudier le problème.
Les résultats expérimentaux obtenus par les trois méthodes ont démontré la
grande capacité des métaheuristiques utilisées pour apporter une solution satisfaisante
au problème de l'émergence inversée et assurer une excellente convergence
du système et un bon équilibre entre exploitation et explorationNote de contenu : Sommaire
Table des matières
Liste des gures iv
Liste des tableaux vi
Introduction Générale 1
1 Introduction aux Systèmes Complexes 8
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Systèmes Complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Niveaux de Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Historique et Dénitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.2 Dénitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Classication des Systèmes Complexes : types de complexité . . . . . . . . . . 11
1.4.1 Type 1. Complexité statique . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.2 Type 2. Complexité dynamique . . . . . . . . . . . . . . . . . . . . . . 12
1.4.3 Type 3. Complexité évolutive . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.4 Type 4. Complexité auto-organisatrice . . . . . . . . . . . . . . . . . . 12
1.5 Caractéristiques des Systèmes Complexes . . . . . . . . . . . . . . . . . . . . . 13
1.5.1 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5.2 Changement du niveau d'intégration . . . . . . . . . . . . . . . . . . . 14
1.5.3 Boucles de rétroaction et non-linéarité . . . . . . . . . . . . . . . . . . 14
1.5.4 Indéterminisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.5 Irréversibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.6 Emergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.7 Auto-organisation et systèmes auto-organisés . . . . . . . . . . . . . . . 19
1.5.8 Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.8.1 Système adaptatif . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.9 Apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.5.9.1 Types d'apprentissage . . . . . . . . . . . . . . . . . . . . . . 21
1.5.9.2 Diérence entre apprentissage et adaptation . . . . . . . . . . 21
1.6 Domaines d'application des systèmes complexes . . . . . . . . . . . . . . . . . 22
1.6.1 Biologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.6.2 Sciences sociales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.6.3 Psychologie et neuroscience . . . . . . . . . . . . . . . . . . . . . . . . 23
1.6.4 Economie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6.5 Chimie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6.6 Géologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.6.7 Logistique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.7 Exemples de systèmes complexes naturels et articiels . . . . . . . . . . . . . . 25
1.7.1 Systèmes complexes naturels . . . . . . . . . . . . . . . . . . . . . . . . 26
1.7.1.1 Le tas de sable . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.7.1.2 Les colonies d'insectes sociaux . . . . . . . . . . . . . . . . . . 27
1.7.1.3 Autres exemples naturels . . . . . . . . . . . . . . . . . . . . 28
1.7.2 Systèmes complexes articiels . . . . . . . . . . . . . . . . . . . . . . . 28
1.7.2.1 Systèmes multi-agents . . . . . . . . . . . . . . . . . . . . . . 29
1.7.2.2 Boids de Reynolds . . . . . . . . . . . . . . . . . . . . . . . . 31
1.7.2.3 L'intelligence en essaim . . . . . . . . . . . . . . . . . . . . . 33
1.7.2.4 Les réseaux de neurones . . . . . . . . . . . . . . . . . . . . . 33
1.7.2.5 Les algorithmes évolutionnaires . . . . . . . . . . . . . . . . . 35
1.7.2.6 Les automates cellulaires . . . . . . . . . . . . . . . . . . . . . 36
1.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2 Les Automates Cellulaires 39
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2 Dénitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.1 Dénition générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.2 Dénition formelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.2.1 Naissance des Automates Cellulaires . . . . . . . . . . . . . . 41
2.2.3 Exemples d'Automates Cellulaires . . . . . . . . . . . . . . . . . . . . . 42
2.2.3.1 Automate Cellulaire Elémentaire . . . . . . . . . . . . . . . . 42
2.2.3.2 L'automate cellulaire "Jeu de la Vie" . . . . . . . . . . . . . . 43
2.2.3.3 Exploration des possibilités des AC . . . . . . . . . . . . . . . 44
2.2.4 La classication de Wolfram . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3 Domaines d'Application des Automates Cellulaires . . . . . . . . . . . . . . . 45
2.3.1 Modélisation en Physique . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.2 Codage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.3 Mathématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.4 Électronique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.5 Phénomènes Biologiques . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.3.6 Autres applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4 les Automates Cellulaires en Traitement d'images . . . . . . . . . . . . . . . . 48
2.4.1 Intérêt des AC en traitement d'images . . . . . . . . . . . . . . . . . . 48
2.4.2 Etat de l'art des AC en traitement d'images . . . . . . . . . . . . . . . 48
2.5 Problématique et motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.5.1 Formulation du problème . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.5.2 Problèmes Inverses d'Automates Cellulaires . . . . . . . . . . . . . . . 50
2.5.2.1 Dénitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.5.2.2 Quelques Problèmes Inverses d'Automates Cellulaires . . . . . 52
2.5.3 Approches utilisées dans la littérature . . . . . . . . . . . . . . . . . . . 55
2.5.4 Les Algorithmes Evolutionnaires pour Résoudre l'Emergence Inversée . 55
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3 Métaheuristiques d'Optimisation : Etat de l'Art 57
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2 Les Algorithmes d'Optimisation Approchée . . . . . . . . . . . . . . . . . . . . 58
3.2.1 Heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2.2 Métaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2.3 Les métaheuristiques à solution unique . . . . . . . . . . . . . . . . . . 59
3.2.3.1 Le Recuit Simulé . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2.3.2 L'Algorithme de Recherche Tabou . . . . . . . . . . . . . . . 61
3.2.4 Les métaheuristiques à population de solutions . . . . . . . . . . . . . . 62
3.2.4.1 Les algorithmes évolutionnaires . . . . . . . . . . . . . . . . . 62
3.2.4.2 Les Algorithmes des Colonies de Fourmis . . . . . . . . . . . . 64
3.2.4.3 L'algorithme des colonies d'abeilles articielles (ABC) . . . . 66
3.2.4.4 Les systèmes immunitaires articiels (AIS) . . . . . . . . . . . 66
3.2.4.5 Algorithme à évolution diérentielle . . . . . . . . . . . . . . 68
3.2.4.6 Les algorithmes à estimation de distribution . . . . . . . . . . 68
3.3 L'Optimisation par Essaim de Particules . . . . . . . . . . . . . . . . . . . . . 69
3.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.3.2 Comparaison entre l'algorithme génétique et le PSO . . . . . . . . . . . 70
3.3.3 Domaines d'utilisation du PSO . . . . . . . . . . . . . . . . . . . . . . 71
3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4 L'Informatique Quantique 73
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.2 L'Informatique Quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2.1 Bit Quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2.2 Registre quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.2.3 Les cinq principes de l'informatique quantique . . . . . . . . . . . . . . 75
4.2.4 Calcul quantique et algorithmes quantiques . . . . . . . . . . . . . . . . 77
4.2.5 Avantages et limites de l'informatique quantique . . . . . . . . . . . . . 78
4.3 Algorithmes Evolutionnaires Quantiques . . . . . . . . . . . . . . . . . . . . . 79
4.3.1 Individu quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.2 Mesure quantique d'individus . . . . . . . . . . . . . . . . . . . . . . . 80
4.3.3 La porte D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.3.4 Discussion de l'algorithme évolutionnaire quantique . . . . . . . . . . . 82
4.4 Autres Algorithmes Inspirés du Quantique . . . . . . . . . . . . . . . . . . . . 82
4.4.1 Algorithmes génétiques quantiques . . . . . . . . . . . . . . . . . . . . 83
4.4.2 Boids de Reynolds quantiques . . . . . . . . . . . . . . . . . . . . . . . 84
4.4.3 Réseaux de neurones quantiques . . . . . . . . . . . . . . . . . . . . . . 85
4.5 Avantages des Algorithmes Inspirés du Quantique . . . . . . . . . . . . . . . . 85
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5 Utilisation du PSO puis QPSO pour résoudre le problème d'émergence inversée .......87
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.2 Contribution 1 : Application de la Métaheuristique PSO pour la Résolution de l'Emergence Inversée . . . . . . 87
5.2.1 Format des règles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.2.2 Evolution de l'automate Cellulaire par la métaheuristique PSO . . . . . 89
5.2.3 La fonction Fitness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.2.4 L'algorithme CA-PSO pour la détection de contours . . . . . . . . . . . 90
5.2.5 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.2.5.1 Les meilleures règles obtenues . . . . . . . . . . . . . . . . . . 92
5.2.5.2 Résultats sur images de synthèse . . . . . . . . . . . . . . . . 92
5.2.5.3 Résultats sur image à niveaux de gris . . . . . . . . . . . . . . 93
5.2.5.4 Résultats sur image réelle . . . . . . . . . . . . . . . . . . . . 93
5.2.5.5 Résultats sur image médicale . . . . . . . . . . . . . . . . . . 94
5.2.5.6 Temps d'exécution . . . . . . . . . . . . . . . . . . . . . . . . 94
5.2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.3 Contribution 2 : Utilisation du PSO Quantique pour la résolution de problème inverse . . . . . .. . 95
5.3.1 L'Algorithme Quantum-behaved PSO . . . . . . . . . . . . . . . . . . . 96
5.3.2 L'approche proposée . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.3.3 Les règles de transition . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.4 Réglage de paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.5 Les fonctions tness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.6 L'algorithme QPSO pour la détection de contours . . . . . . . . . . . . 99
5.3.7 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.3.7.1 Meilleur paquet de règles . . . . . . . . . . . . . . . . . . . . 100
5.3.7.2 Résultats visuels . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.3.7.3 Comparaison avec des travaux similaires . . . . . . . . . . . . 101
5.3.8 L'algorithme QPSO pour le ltrage d'images . . . . . . . . . . . . . . . 104
5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6 L'Algorithme Génétique Quantique pour la Résolution de l'Emergence Inversée .....107
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.2 Etat de l'art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.3 Généralités sur le Quantum Genetic Computing . . . . . . . . . . . . . . . . . 109
6.3.1 Principes de l'Algorithme Génétique Quantique . . . . . . . . . . . . . 110
6.3.2 Codage des Chromosomes Quantiques . . . . . . . . . . . . . . . . . . 110
6.3.3 La Mesure des Chromosomes . . . . . . . . . . . . . . . . . . . . . . . 111
6.4 L'Approche Proposée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.5 Résultats Expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.6 Comparaison entre Algorithme Génétique Quantique et Algorithme Génétique Classique . . . . . . . 115
6.6.1 Résultats Numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.6.2 Complexité Algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Conclusion et Perspectives 119
Travaux de l'auteur 121
BibliographieCôte titre : DI/0036 En ligne : https://drive.google.com/file/d/1v48n0zBwSM8vrMsZyUqThjE9MEXQlGn2/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DI/0036 DI/0036 Thèse Bibliothéque des sciences Français Disponible
Disponible"Control des mouvements d'avatar en utilisant la technique ""Inverse Kenimatics"" " / Cheraga,k.abdelmoumene
Titre : "Control des mouvements d'avatar en utilisant la technique ""Inverse Kenimatics"" " Type de document : texte imprimé Auteurs : Cheraga,k.abdelmoumene ; LAKHFIF, A, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (55f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Génie Logiciel
animation
avatar
cinématique inverse
humanoides virtuels
control des mouvementsIndex. décimale : 004 Informatique Côte titre : MAI/0180 "Control des mouvements d'avatar en utilisant la technique ""Inverse Kenimatics"" " [texte imprimé] / Cheraga,k.abdelmoumene ; LAKHFIF, A, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (55f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Génie Logiciel
animation
avatar
cinématique inverse
humanoides virtuels
control des mouvementsIndex. décimale : 004 Informatique Côte titre : MAI/0180 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0180 MAI/0180 Mémoire Bibliothéque des sciences Français Disponible
DisponibleContrôle autonomique contextualise guide par les ontologies des applications mobiles multimodales / Abderrahim Lakehal
Titre : Contrôle autonomique contextualise guide par les ontologies des applications mobiles multimodales Type de document : texte imprimé Auteurs : Abderrahim Lakehal ; Alti,Adel, Directeur de thèse Editeur : Setif:UFA Année de publication : 2016 Importance : 1 vol (87f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
Profil utilisateur
Contexte
Contrainte
Autonomique
Ontologie
AdaptationIndex. décimale : 004 Informatique Résumé : RESUME
Actuellement, les applications mobiles ont été largement utilisées dans divers domaines. Les
applications mobiles ubiquitaires ont pour objectif d’accompagner les utilisateurs à tout
moment, en tout lieu et en toute circonstance. Elles sont développées en blocs qui s’exécutent
sur des Smartphones, des laptops et des tablettes. La mobilité tient compte des contraintes
inhérentes au caractère multimédia. Ce contexte soulève, entre autre, des problèmes liés Ã
l’hétérogénéité des contenus (documents, données, flux de données ou autres données liées Ã
des services), aux terminaux (capteurs domestiques), aux préférences des utilisateurs et leurs
contextes d’usages (profils).Dans ce travail, nous tenons compte de l’ensemble de ces
problèmes en nous focalisant particulièrement sur les applications mobiles sensibles aux
contextes. Pour ce faire, nous proposons une architecture basée sur une ontologie générique
qui fournit des services sémantiquement équivalents et appropriés au contexte spécifique
d’une personne via des règles d’inférences. Afin de valider notre proposition, nous avons
utilisé les technologies issues du Web sémantique et l’intergicielKalimucho pour la
spécification et l’expérimentation des profils des utilisateurs sur plusieurs plates-formes.Note de contenu : Table des matières
INTRODUCTION GENERALE ........................................................................................ 1
Chapitre 1 : Système Ambiant Autonomique Et Web Sémantique
1. Introduction.................................................................................. 3
2. Systèmes ambiants ................................................................................... 4
2.1 Définition............................................................................................ 4
2.2 Caractéristique des systèmes ambiants................................................................ 5
2.3 Architecture des systèmes ambiants.................................................................... 5
2.4 Hétérogénéité et mobilité .................................................................................. 6
3. Contexte et Sensibilité au contexte .................................................................. 7
3.1 Définition......................................................................................... 7
3.2 Contexte et l’informatique ambiante ................................................................... 7
3.3 Sensibilité au contexte.............................................................................. 7
4. Profils utilisateurs et ses contraintes ................................................................. 8
4.1 Définition............................................................................................. 8
4.2 Modélisation du profil ............................................................................. 8
5. Système ambiant autonomique....................................................................... 9
5.1 Définition............................................................................................. 9
5.2 Boucle CADA (Collection, Analysis, Decision and Action)........................................... 10
6. Web sémantique ....................................................................................... 11
6.1 Ontologie ................................................................................................. 12
6.2 La structure d’une ontologie ................................................................................. 12
7. Conclusion ............................................................................................ 14
Chapitre 2 : Etat de l’art
1. Introduction................................................................................................. 15
2. Travaux connexes...................................................................................... 15
2.1 Architectures contextuelles pour le déploiement de services........................................ 16
2.2 Les plates-formes existantes .......................................................................................... 17
2.3 Les techniques d'adaptation .......................................................................................... 18
3. Synthèse et discussion ................................................................................................ 21
4. Conclusion ................................................................................................. 24
Chapitre 3 : Conception et ontologie développée
1. Introduction...................................................................................................... 25
2. Présentation de la solution AESCR ........................................................................... 25
3. Ontologie développée du modèle de contexte............................................................ 26
3.1 Ontologie de noyau ........................................................................................................ 26
3.2 Ontologie de domaine de contexte ................................................................................. 27
3.3 Ontologie des contraintes............................................................................................... 32
3.4 Ontologie des propriétés de contextes ........................................................................... 33
3.5 Ontologie des services contextuels................................................................................. 34
3.6 Ontologie des Evénements............................................................................................. 34
3.7 Ontologie des Situations................................................................................................. 35
4. Plateforme Kalimucho-smart .................................................................................... 36
4.1 Démarche d’intégration à Kalimucho........................................................................... 36
4.2 Architecture de la plateforme Kalimucho-smart...................................................... 36
4.3 Schéma fonctionnel............................................................................................ 40
5. Simulation de la plateforme....................................................................................... 41
6. Conclusion ................................................................................. 46
Chapitre 4 : REALISATION PROTOTYPE et EVALUATION
1. Introduction............................................................................................. 47
2. Les langages utilisés et les outils d'implémentations................................................. 48
2.1 Les langages utilisées ................................................................................................ 48
2.1.1 Langage Java.........................................................................................................48
2.1.2 Langage SQL (Structured Query Language)..................................................................................48
2.1.3 Langage PHP...............................................................................................48
2.1.4 Langage OWL (Ontology Web Language) ...................................................................................48
2.1.5 Langage SWRL (Semantic Web Rule Language).......................................................................................49
2.2 Les outils utilisés.................................................................................... 49
2.2.1 Eclipse..................................................................................49
2.2.2 Android Studio .................................................................................49
2.2.3 MySQL..............................................................................................49
2.2.4 EasyPHP................................................................................................50
2.2.5 Protégé..................................................................................................50
2.2.6 Plateforme Kalimucho .........................................................................................50
3. Implémentations et Structures de données utilisées ................................................. 51
3.1 Structure de la base de donnée «BDContext»............................................................... 51
3.2 L'implémentation de l'ontologie Smart-Adaptation-Context....................................... 55
3.3 L'implémentation des services contextuels.................................................................... 58
3.4 Architecture et fonctionnement générale de la plateforme........................................... 58
3.5 Modèle de fonctionnement de la plateforme ................................................................. 61
3.6 Description des classes java et packages AESCR ......................................................... 63
3.6.1 Package AESCR..................................................................................................63
3.6.2 Package ContextConstraintManager.................................................................................63
3.6.3 Package ContextServiceManager.............................................................................63
3.6.4 Package ContextUserManager.......................................................................................64
3.6.5 Package ContextReasoner.............................................................................................64
3.6.6 Package Repository ...........................................................................................................64
3.6.7 Package ServiceController............................................................................................64
4. Scénario d’illustration et validation .......................................................................... 65
5. Conclusion .................................................................................................................. 75
CONCLUSION GENERALE ........................................................................................... 76
Bibliographies.................................................................................................................... 77
Annexes.............................................................................................................................. 82Côte titre : MAI/0125 En ligne : https://drive.google.com/file/d/1tlvVAZTXGZXjPAV1d0_4o851IexKm45E/view?usp=shari [...] Format de la ressource électronique : Contrôle autonomique contextualise guide par les ontologies des applications mobiles multimodales [texte imprimé] / Abderrahim Lakehal ; Alti,Adel, Directeur de thèse . - [S.l.] : Setif:UFA, 2016 . - 1 vol (87f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
Profil utilisateur
Contexte
Contrainte
Autonomique
Ontologie
AdaptationIndex. décimale : 004 Informatique Résumé : RESUME
Actuellement, les applications mobiles ont été largement utilisées dans divers domaines. Les
applications mobiles ubiquitaires ont pour objectif d’accompagner les utilisateurs à tout
moment, en tout lieu et en toute circonstance. Elles sont développées en blocs qui s’exécutent
sur des Smartphones, des laptops et des tablettes. La mobilité tient compte des contraintes
inhérentes au caractère multimédia. Ce contexte soulève, entre autre, des problèmes liés Ã
l’hétérogénéité des contenus (documents, données, flux de données ou autres données liées Ã
des services), aux terminaux (capteurs domestiques), aux préférences des utilisateurs et leurs
contextes d’usages (profils).Dans ce travail, nous tenons compte de l’ensemble de ces
problèmes en nous focalisant particulièrement sur les applications mobiles sensibles aux
contextes. Pour ce faire, nous proposons une architecture basée sur une ontologie générique
qui fournit des services sémantiquement équivalents et appropriés au contexte spécifique
d’une personne via des règles d’inférences. Afin de valider notre proposition, nous avons
utilisé les technologies issues du Web sémantique et l’intergicielKalimucho pour la
spécification et l’expérimentation des profils des utilisateurs sur plusieurs plates-formes.Note de contenu : Table des matières
INTRODUCTION GENERALE ........................................................................................ 1
Chapitre 1 : Système Ambiant Autonomique Et Web Sémantique
1. Introduction.................................................................................. 3
2. Systèmes ambiants ................................................................................... 4
2.1 Définition............................................................................................ 4
2.2 Caractéristique des systèmes ambiants................................................................ 5
2.3 Architecture des systèmes ambiants.................................................................... 5
2.4 Hétérogénéité et mobilité .................................................................................. 6
3. Contexte et Sensibilité au contexte .................................................................. 7
3.1 Définition......................................................................................... 7
3.2 Contexte et l’informatique ambiante ................................................................... 7
3.3 Sensibilité au contexte.............................................................................. 7
4. Profils utilisateurs et ses contraintes ................................................................. 8
4.1 Définition............................................................................................. 8
4.2 Modélisation du profil ............................................................................. 8
5. Système ambiant autonomique....................................................................... 9
5.1 Définition............................................................................................. 9
5.2 Boucle CADA (Collection, Analysis, Decision and Action)........................................... 10
6. Web sémantique ....................................................................................... 11
6.1 Ontologie ................................................................................................. 12
6.2 La structure d’une ontologie ................................................................................. 12
7. Conclusion ............................................................................................ 14
Chapitre 2 : Etat de l’art
1. Introduction................................................................................................. 15
2. Travaux connexes...................................................................................... 15
2.1 Architectures contextuelles pour le déploiement de services........................................ 16
2.2 Les plates-formes existantes .......................................................................................... 17
2.3 Les techniques d'adaptation .......................................................................................... 18
3. Synthèse et discussion ................................................................................................ 21
4. Conclusion ................................................................................................. 24
Chapitre 3 : Conception et ontologie développée
1. Introduction...................................................................................................... 25
2. Présentation de la solution AESCR ........................................................................... 25
3. Ontologie développée du modèle de contexte............................................................ 26
3.1 Ontologie de noyau ........................................................................................................ 26
3.2 Ontologie de domaine de contexte ................................................................................. 27
3.3 Ontologie des contraintes............................................................................................... 32
3.4 Ontologie des propriétés de contextes ........................................................................... 33
3.5 Ontologie des services contextuels................................................................................. 34
3.6 Ontologie des Evénements............................................................................................. 34
3.7 Ontologie des Situations................................................................................................. 35
4. Plateforme Kalimucho-smart .................................................................................... 36
4.1 Démarche d’intégration à Kalimucho........................................................................... 36
4.2 Architecture de la plateforme Kalimucho-smart...................................................... 36
4.3 Schéma fonctionnel............................................................................................ 40
5. Simulation de la plateforme....................................................................................... 41
6. Conclusion ................................................................................. 46
Chapitre 4 : REALISATION PROTOTYPE et EVALUATION
1. Introduction............................................................................................. 47
2. Les langages utilisés et les outils d'implémentations................................................. 48
2.1 Les langages utilisées ................................................................................................ 48
2.1.1 Langage Java.........................................................................................................48
2.1.2 Langage SQL (Structured Query Language)..................................................................................48
2.1.3 Langage PHP...............................................................................................48
2.1.4 Langage OWL (Ontology Web Language) ...................................................................................48
2.1.5 Langage SWRL (Semantic Web Rule Language).......................................................................................49
2.2 Les outils utilisés.................................................................................... 49
2.2.1 Eclipse..................................................................................49
2.2.2 Android Studio .................................................................................49
2.2.3 MySQL..............................................................................................49
2.2.4 EasyPHP................................................................................................50
2.2.5 Protégé..................................................................................................50
2.2.6 Plateforme Kalimucho .........................................................................................50
3. Implémentations et Structures de données utilisées ................................................. 51
3.1 Structure de la base de donnée «BDContext»............................................................... 51
3.2 L'implémentation de l'ontologie Smart-Adaptation-Context....................................... 55
3.3 L'implémentation des services contextuels.................................................................... 58
3.4 Architecture et fonctionnement générale de la plateforme........................................... 58
3.5 Modèle de fonctionnement de la plateforme ................................................................. 61
3.6 Description des classes java et packages AESCR ......................................................... 63
3.6.1 Package AESCR..................................................................................................63
3.6.2 Package ContextConstraintManager.................................................................................63
3.6.3 Package ContextServiceManager.............................................................................63
3.6.4 Package ContextUserManager.......................................................................................64
3.6.5 Package ContextReasoner.............................................................................................64
3.6.6 Package Repository ...........................................................................................................64
3.6.7 Package ServiceController............................................................................................64
4. Scénario d’illustration et validation .......................................................................... 65
5. Conclusion .................................................................................................................. 75
CONCLUSION GENERALE ........................................................................................... 76
Bibliographies.................................................................................................................... 77
Annexes.............................................................................................................................. 82Côte titre : MAI/0125 En ligne : https://drive.google.com/file/d/1tlvVAZTXGZXjPAV1d0_4o851IexKm45E/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0125 MAI/0125 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Coordinated Snapshot Algorithm for Distributed Computing Systems Type de document : texte imprimé Auteurs : Bouzidi, Yasmine, Auteur ; Mansouri,Hossem, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (50 f .) Format : 29 cm Langues : Français (fre) Langues originales : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Système distribué
Sûreté de Fonctionnement
Tolérance aux pannes
Point de contrôle coordonné non bloquant
ingIndex. décimale : 004 - Informatique Résumé : Résumé
La restauration de restauration dans les systèmes répartis est importante pour le calcul tolérant aux pannes. Sans tolérance de panne
mécanismes, une application fonctionnant sur un système doit être restaurée à partir de zéro si une erreur se produit dans le
milieu de son exécution, entraînant une perte de l'informatique utile. Pour fournir une restauration de restauration e? Cient pour
la tolérance aux pannes dans les systèmes distribués, il est important de réduire le nombre de points de contrôle dans l'existence
de points globaux cohérents dans des algorithmes de points distribués coordonnés.
La saisie coordonnée est une approche attrayante pour ajouter de manière transparente la tolérance aux pannes
applications attribuées car elle évite les effets domino et minimise l'exigence de stockage stable. Cependant,
il subit des frais généraux élevés associés au processus de cartographie dans les systèmes informatiques mobiles. Deux
Des approches ont été utilisées pour réduire les frais généraux: d'abord, réduire le nombre de mes-
les sages et le nombre de points de contrôle; l'autre est de rendre le processus de surveillance non bloquant. Dans ce
Nous introduisons le concept du checkpoint mutable, qui est soit un point de contrôle provisoire, soit un
point de contrôle, pour concevoir des algorithmes e-cient de points de contrôle. Les points muets peuvent être sauvegardés n'importe où.
De cette façon, prendre un point de contrôle mutable évite le transfert de grandes quantités de données vers
stockage stable. Nous présentons des techniques pour minimiser le nombre de points de contrôle mutables. Résultats de simulation
de Cao et de l'algorithme singhal montrent que l'overhead de prendre des checkpoints mutables est négligeable. Basé
sur des points de contrôle mutables, notre algorithme de non-blocage évite l'effet d'avalanche et ne force qu'un minimum
nombre de processus pour prendre leurs points sur le stockage stable.Note de contenu : Sommaire
Introduction 6
1 Dependability and Fault Tolerance in Distributed Systems 7
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Dependability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Dependability Impairments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1.1 Fault . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1.2 Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1.3 Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2 Dependability attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.3 Means to Attain Dependability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.3.1 Fault prevention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.3.2 Fault tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.3.3 Fault removal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.3.4 Fault forecasting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 Failure classication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Fault Tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.1 Error Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.1.1 Redundancy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.2 Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.2.1 Error Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.2.2 Fault Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 Fault tolerance in distributed system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.1 Distributed Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.1.1 Distributed System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5.2 Fault tolerance techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.2.1 Fault tolerance by replication . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.2.2 Fault tolerance by stable storage . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2 Checkpointing Techniques 22
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Backgrounds and Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Checkpointing techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.1 Checkpoint-Based Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.1.1 Coordinated checkpoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.1.2 Uncoordinated checkpointing . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.1.3 Communication induced checkpointing . . . . . . . . . . . . . . . . . . . . . 26
2.3.2 Log Based . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.2.1 Pessimistic logging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.2.2 Optimistic logging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.2.3 Causal logging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4 Checkpointing Techniques Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 Checkpointing Algorithms Classication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5.1 Classication tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3 Coordinated Checkpointing Algorithms 33
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 ChkSim : A Distributed Checkpointing Simulator . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.1 Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2 ChkSim Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2.1 Jdom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2.2 Junit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.2.3 Apache ant(Another Neat Tool) . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.2.4 Gnuplot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.3 Simulation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.4 Software Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.5 Load Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.6 Statistic Load Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.7 Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.8 Simulator Runner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3 Cao and Singhal Checkpointing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.1.1 The Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.2.1 Checkpointing Initiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.2.2 Reception of a Checkpoint Request . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.2.3 Computation Messages Received during Checkpointing . . . . . . . . . . . . 42
3.3.2.4 Termination and Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . 43
3.3.2.5 Instead of Broadcasting commit Messages to All Processes . . . . . . . . . . 43
3.3.3 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Conclusion 47
Côte titre : MAI/0267 En ligne : https://drive.google.com/file/d/1v9BIJRc_uow9ZDl-CZC9nKSzD5X8jCvw/view?usp=shari [...] Format de la ressource électronique : Coordinated Snapshot Algorithm for Distributed Computing Systems [texte imprimé] / Bouzidi, Yasmine, Auteur ; Mansouri,Hossem, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (50 f .) ; 29 cm.
Langues : Français (fre) Langues originales : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Système distribué
Sûreté de Fonctionnement
Tolérance aux pannes
Point de contrôle coordonné non bloquant
ingIndex. décimale : 004 - Informatique Résumé : Résumé
La restauration de restauration dans les systèmes répartis est importante pour le calcul tolérant aux pannes. Sans tolérance de panne
mécanismes, une application fonctionnant sur un système doit être restaurée à partir de zéro si une erreur se produit dans le
milieu de son exécution, entraînant une perte de l'informatique utile. Pour fournir une restauration de restauration e? Cient pour
la tolérance aux pannes dans les systèmes distribués, il est important de réduire le nombre de points de contrôle dans l'existence
de points globaux cohérents dans des algorithmes de points distribués coordonnés.
La saisie coordonnée est une approche attrayante pour ajouter de manière transparente la tolérance aux pannes
applications attribuées car elle évite les effets domino et minimise l'exigence de stockage stable. Cependant,
il subit des frais généraux élevés associés au processus de cartographie dans les systèmes informatiques mobiles. Deux
Des approches ont été utilisées pour réduire les frais généraux: d'abord, réduire le nombre de mes-
les sages et le nombre de points de contrôle; l'autre est de rendre le processus de surveillance non bloquant. Dans ce
Nous introduisons le concept du checkpoint mutable, qui est soit un point de contrôle provisoire, soit un
point de contrôle, pour concevoir des algorithmes e-cient de points de contrôle. Les points muets peuvent être sauvegardés n'importe où.
De cette façon, prendre un point de contrôle mutable évite le transfert de grandes quantités de données vers
stockage stable. Nous présentons des techniques pour minimiser le nombre de points de contrôle mutables. Résultats de simulation
de Cao et de l'algorithme singhal montrent que l'overhead de prendre des checkpoints mutables est négligeable. Basé
sur des points de contrôle mutables, notre algorithme de non-blocage évite l'effet d'avalanche et ne force qu'un minimum
nombre de processus pour prendre leurs points sur le stockage stable.Note de contenu : Sommaire
Introduction 6
1 Dependability and Fault Tolerance in Distributed Systems 7
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Dependability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Dependability Impairments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1.1 Fault . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1.2 Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1.3 Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2 Dependability attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.3 Means to Attain Dependability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.3.1 Fault prevention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.3.2 Fault tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.3.3 Fault removal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.3.4 Fault forecasting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 Failure classication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Fault Tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.1 Error Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.1.1 Redundancy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.2 Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.2.1 Error Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.2.2 Fault Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 Fault tolerance in distributed system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.1 Distributed Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.1.1 Distributed System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5.2 Fault tolerance techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.2.1 Fault tolerance by replication . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.2.2 Fault tolerance by stable storage . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2 Checkpointing Techniques 22
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Backgrounds and Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Checkpointing techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.1 Checkpoint-Based Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.1.1 Coordinated checkpoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.1.2 Uncoordinated checkpointing . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.1.3 Communication induced checkpointing . . . . . . . . . . . . . . . . . . . . . 26
2.3.2 Log Based . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.2.1 Pessimistic logging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.2.2 Optimistic logging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.2.3 Causal logging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4 Checkpointing Techniques Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 Checkpointing Algorithms Classication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5.1 Classication tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3 Coordinated Checkpointing Algorithms 33
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 ChkSim : A Distributed Checkpointing Simulator . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.1 Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2 ChkSim Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2.1 Jdom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2.2 Junit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.2.3 Apache ant(Another Neat Tool) . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.2.4 Gnuplot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.3 Simulation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.4 Software Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.5 Load Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.6 Statistic Load Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.7 Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.8 Simulator Runner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3 Cao and Singhal Checkpointing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.1.1 The Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.2.1 Checkpointing Initiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.2.2 Reception of a Checkpoint Request . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.2.3 Computation Messages Received during Checkpointing . . . . . . . . . . . . 42
3.3.2.4 Termination and Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . 43
3.3.2.5 Instead of Broadcasting commit Messages to All Processes . . . . . . . . . . 43
3.3.3 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Conclusion 47
Côte titre : MAI/0267 En ligne : https://drive.google.com/file/d/1v9BIJRc_uow9ZDl-CZC9nKSzD5X8jCvw/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0267 MAI/0267 Mémoire Bibliothéque des sciences Français Disponible
DisponiblePermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkCryptanalysis and Improvement of a Security Protocol in Medical Internet of Things / Sirine Belbechouche
PermalinkPermalinkPermalink