Structure Fichiers et Structures de Données

ESI > Développement Logiciel > Structure Fichiers et Structures de Données

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.

ID Cours
SFSD
Niveau
2ème année CP
Semestre
Semestre 3
Crédit
4
Volumes Horaires Cours
30.00
Coef
4
Volumes Horaires TD
30.00

Pré-requis:

Structures de données dynamiques

Familles de Compétences

  • CF4 : Concevoir, réaliser et maintenir des logiciels de qualité
  • CF7 : Concevoir, mettre en œuvre et administrer des infrastructures complexes et réparties

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

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.

Travail personnel

Deux à trois TPs à réaliser + un mini projet

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,

We are using cookies to give you the best experience. You can find out more about which cookies we are using or switch them off in privacy settings.
AcceptPrivacy Settings

GDPR