| Objectifs: | Cette matière aborde les aspects fondamentaux de la science informatique. Elle fait suite au module ALSDD dans tous ses aspects. Elle traite de l’organisation interne des données fournissant à l’étudiant des bases solides le rendant capable de concevoir des structures de fichiers adaptables aux nouveaux besoins des applications.
Les principaux objectifs sont les suivants:
- Elaboration de solutions algorithmiques manipulant des structures de fichiers concerne l’aspect performance.
- Etude des structures de fichiers (données et algorithmes) ainsi que l’évaluation des performances à travers l’analyse de complexité (notation de Landau) adaptées aux opérations d’entrées/sorties.
- Préparation de l’étudiant pour les nouvelles problématiques des données massives telles ( Big Data, etc.)
- Introduction des opérations de haut niveau telles que le tri, la jointure, la fusion, etc. |
| Contenu: | I- Généralités sur les fichiers (6 h.)
Concepts de base (fichiers, E/S, Supports et technologies actuelles, terminologie...)
Complexité des algorithmes sur les structures de fichiers
Modèle générique pour la manipulation et l’évaluation des structures de fichiers
II- Les méthodes d’accès séquentielles (6 h.)
Organisation contiguë
Organisation chaînée
Traitement des formats variables des enregistrements
Les fichiers ordonnés
Classification des structures simples
III- Les méthodes d’index (4 h.)
Index primaire
Index secondaire
Index multiniveaux
IV- Les méthodes à base d’arbres de recherche (6 h.)
Fichier arborescent
Index arborescent
B-Arbres et variantes
V- Les méthodes à base Hachage (4 h.)
Fonction de hachage et Méthodes de résolution de collisions pour l’accès externe
Méthodes à base de Hachage statique
Méthodes à base de Hachage dynamique
VI- Opérations de haut niveau sur les fichiers (4 h.)
Notion base de données et traitements de requêtes
Algorithme du tri externe (par fusions multiples)
Opération de type jointure de deux fichiers
a. Algorithme ‘par boucles imbriquées’
b. Algorithme ‘par tri-fusion’
c. Algorithme ‘par hachage’
RECOMMANDATION :
Certaines séances de TD doivent se dérouler en salles machines. |
| Bibliographie: | K.R. Venugopal, K.G. Srinivasa & P.M. Krishnaraj, « File Structures Using C++ », McGraw-Hill Education,
Reema Thareja, « Data & File Structures Using C », Oxford University Press,
Alan L. Tharp, « FILE ORGANIZATION AND PROCESSING », Wiley India Pvt. Limited, 2008.
M.J. Folk, B. Zoellick & G. Riccardi, “File structures”, Addison-wesley,
D.E. Zegour, « Structures de données et de fichiers », Ed. Chihab,
D. Knuth, “The art of computer programming”, 3rd Ed. Vol. 3, Addison-wesley,
A. Aho, J. Hopcroft & J Ullman, “Data structures and algorithms”, Addison-wesley, |
