Pré-requis:
Structures de données dynamiques
Familles de Compétences
Type de compétence:
TEC : Technique
MET : Méthodologique
MOD : Modélisation
OPE : Opérationnel
Niveau de compétence:
Base | Intermédiaire | Avancé |
Famille de Compétence | Compétence | Elément de Compétence | Type |
---|---|---|---|
CF4 | C4.0: Développer des programmes informatiques | C40.7: Concevoir des structures de fichiers efficaces et répondant aux besoins de tout type d’applications, y compris le cas des données volumineuses et massives. | MOD |
C40.8: Identifier les différents types d’organisation des fichiers et effectuer un choix d’organisation répondant aux besoins des applications | MET | ||
C4.A: Analyser et concevoir des algorithmes | C4A.1: Etudier les structures de données et de fichiers et analyser l’efficacité des algorithmes | MET | |
CF7 | C7.7: Exploiter un système d’exploitation centralisé | C77.6: Différencier les technologies de stockage | OPE |
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.
Deux à trois TPs à réaliser + un mini projet
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,