Mémoires soutenus sur le thème "STRUCTURES DE DONNÉES DYNAMIQUES"

Réaction du hachage digital aux pannes système.
Concurrences dans les B-TREES.
Hachage linéaire multidimensionnel.
Hachage digital multiniveaux avec les représentations séquentielles.
HDMV : Hachage Digital Multiniveaux Virtuel.
Hachage digital (trie hashing) multi-clés.
Hachage par interpolation : Une structure de données efficace pour les fichiers multidimensionnels.
Traitement d'images à base de "quadtrees".
Désordre borné : une méthode efficace d'accès aux fichiers basée sur le concept d'élasticité des blocs.

SUJET	Réaction du hachage digital aux pannes système.
PRÉSENTÉ PAR	S.M BOUSELMANE.
Le hachage digital, conçu en 1981 par W. Litwin, utilise un arbre binaire digital pour représenter sa fonction d'accès. Une recherche d'article s'accomplit en un accès disque au plus, ce qui place la méthode parmi les meilleures techniques d'accès actuelles. Dans sa version de base, l'auteur n'étudie pas la réaction de la méthode suite à une panne système. Leen Torenvliet et P. Van Emde Boas (1) améliore l'algorithme de base afin de rendre possible la reconstruction de la fonction d'accès après une panne système. La reconstruction peut même engendrer un arbre meilleur que l'arbre original. Il s'agit dans un premier temps de faire une étude bibliographique importante. En particulier revoir les méthodes d'accès existantes aux fichiers ( classiques et nouvelles) puis faire une étude approfondie du hachage digital. Sur la base de l'article des auteurs, un effort certain est à faire pour comprendre la formalisation mathématique utilisée, sur laquelle il est demandé de retrouver les algorithmes en question (reconstruction et optimisation ). La réalisation des algorithmes est nécessaire afin de procéder aux mesures par simulation.

SUJET	Concurrences dans les B-TREES.
PRÉSENTÉ PAR	DJERARBA
Il s'agit dans un premier temps de revoir les mécanismes des B-arbres et les problèmes liés à la concurrence tels que la synchronisation (verrou, sémaphore,..) Dans un deuxième temps, sur la base des 2 articles de KWONG et WOOD : * Concurrency in B-trees and their variants * Approches to concurrency in B-trees retrouver les algorithmes en question. Enfin, définir un environnement pour tester les algorithmes.

SUJET	Hachage linéaire multidimensionnel.
PRÉSENTÉ PAR	S.EL MANSALI et K. MOKRANE
L'une des techniques d'accès aux fichiers les plus prometteuses est celle du hachage linéaire, œuvre des travaux de Litwin (1980). La méthode a connu beaucoup de succès, puisque beaucoup de travaux lui ont été consacrés cette dernière décennie. L'un des aspects les plus importants de ces travaux, concerne l'accès multidimensionnel. Il s'agit d'étudier deux méthodes (OTTO 85) et (OUKSEL 83) afin de retrouver les algorithmes puis de procéder par simulation en vu de les comparer.

SUJET	Hachage digital multiniveaux avec les représentations séquentielles.
PRÉSENTÉ PAR	R. BENGHAZEL et D. BOULANOIR
Une fois les techniques d'accès classiques existantes revues, il est question de se pencher sur le hachage dynamique, thème nouvellement proposé ces dix dernières années. Il s'en suit une étude bibliographique importante. Parmi les travaux sur ce nouveau concept du hachage, on cite particulièrement les travaux de Litwin sur la technique dite " hachage digital " ( 1981). La méthode utilise un arbre binaire particulier pour représenter sa fonction d'accès et n'exige pas plus d'un accès disque pour retrouver un article dans un fichier qui peut en contenir des millions . Le hachage digital multiniveaux (HDM) , proposé par D.E Zegour, est une extension du hachage digital pour les fichiers volumineux que le hachage digital ne peut supporter. Sa formulation consiste essentiellement à paginer la fonction d'accès générée par le hachage digital. Dans sa version de base, HDM utilise la représentation standard de l'arbre. Chaque nœud est alors un tripet (G, info, D) où G et D désignent les fils gauche et droit; info désigne l'information rattaché au nœud. Le travail consiste à examiner HDM avec une représentation séquentielle possible proposée par D.E Zegour. L'idée de base dans les représentations séquentielles est de ne pas représenter les pointeurs gauche et droit de tout nœud. Un ordre prédéfini est alors supposé. Il s'agit de concevoir des algorithmes sur ce nouveau schéma, c'est à dire résoudre les deux problèmes suivants : Comment segmenter l'arbre ainsi représenté ? Comment partager équitablement l'arbre en deux ?

SUJET	HDMV : Hachage Digital Multiniveaux Virtuel.
PRÉSENTÉ PAR	AMRIOU
Le thème principal est le hachage dynamique, nouvellement proposé ces dix dernières années. Il s'en suit une étude bibliographique importante. Parmi les travaux sur ce nouveau concept du hachage, on cite particulièrement les travaux de Litwin sur la technique dite " hachage digital " ( 1981). La méthode utilise un arbre binaire particulier pour représenter sa fonction d'accès et n'exige pas plus d'un accès disque pour retrouver un article dans un fichier qui peut en contenir des millions. Le hachage digital multiniveaux (HDM) , proposé par D.E Zegour, est une extension du hachage digital pour les fichiers volumineux que le hachage digital ne peut supporter. Sa formulation consiste essentiellement à paginer la fonction d'accès générée par le hachage digital. Le travail consistera à examiner HDM avec la technique de bufférisation LRU. Aussi, on baptisera la nouvelle méthode, hachage digital multiniveaux virtuel (HDMV). Une étude comparative ( par simulation) avec la technique d'arbre B, la plus usitée actuellement, est aussi à faire.

SUJET	Hachage digital (trie hashing) multi-clés.
PRÉSENTÉ PAR	AMRANI
Sur la base de l'article de OTTO 85 (A multidimensional digital hashing for files with composites keys), Il s'agit, dans un premier temps, de retrouver les algorithmes de transformation clé-adresse, insertion, suppression et requête à intervalle. L'algorithme de suppression est a concevoir de manière récursive. Puis, dans un deuxième temps, faire une simulation en vue de montrer les performances de la méthode. Une comparaison avec des méthodes concurrentes est aussi à prévoir.

SUJET	Hachage par interpolation : Une structure de données efficace pour les fichiers multidimensionnels.
PRÉSENTÉ PAR	AIDOUNE
Le travail consiste à : - se familiariser avec les structures de données classiques. Plus particulièrement les arbres B et les méthodes de hachage. - étudier en détail la méthode proposée pour retrouver les algorithmes inconnus du public de recherche, d'insertion, de suppression et de requête à intervalle. Éventuellement, faire des critiques et suggestions. - étudier les performances de la méthode pour la comparer aux méthodes concurrentes classiques ou nouvelles. Il serait souhaitable de faire une démonstration graphique afin de montrer la méthode et faire une application directe de ce travail, recherche documentaire par exemple.

SUJET	Traitement d'images à base de "quadtrees"
PRÉSENTÉ PAR	BENZINE
Toute image peut être représentée par une structure de données spéciale, appelée quadtree. Comme son nom l'indique l'image est découpée en quatre zones ( quatre fils ). Chaque zone se découpe à son tour en quatre zones. Et ainsi de suite ... Dans un premier temps, il faut se pencher sur les diverses manières de représenter les quadtrees en mémoire en examinant les deux opérations: passage d'une image en une quadtree et réciproquement. Ensuite, il faut étudier et développer toutes les opérations sur les images - de type ensembliste telles que l'union , l'intersection, .. - de type transformations telles que les symétrie, les rotations, .. - de type zoom. Quelques propriétés géométriques seront étudiées comme le calcul d'air, le périmètre, etc.. Le travail consiste à réaliser un logiciel capable de traiter les images ayant au moins les taches précitées. Le logiciel projet‚ doit être convivial et posséder au moins les propriétés de portabilité et d'extension.

SUJET	Désordre borné : une méthode efficace d'accès aux fichiers basée sur le concept d'élasticité des blocs.
PRÉSENTÉ PAR	L.TAILEB et M.L AZZOUZ
Le hachage digital est une technique d'accès conçue pour les fichiers dynamiques, monoclés et ordonnés. La technique utilise un arbre digital pour représenter sa fonction d'accès. Cet arbre ne peut être contenu en mémoire centrale quand le fichier devient volumineux. Pour remédier à ceci, quelques extensions ont été proposées mais ne font que segmenter ou compacter l'arbre digital sans toucher aux cases du fichier. Le technique du désordre borné est une autre extension fort intéressante. La méthode conserve le hachage digital de base pour l'accès au fichier. Par contre le fichier est vu comme un ensemble de blocs, chaque bloc contient un ensemble de cases. A l'intérieur d'un bloc, les cases sont adressées par une autre fonction de hachage (classique). Le fichier est donc ordonné globalement bloc par bloc, mais à l'intérieur d'un bloc les articles sont désordonnés, d'où l'appellation de la méthode. Le but de ce travail est de retrouver et réaliser tous les algorithmes qui s'y rattachent, puis de faire une simulation en vue de montrer les performances de la méthode.