Logo ESI
Bannière
ESI talents

Bienvenue



Retour - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Syllabus SFSD
Télécharger



Crédits : 4

SFSD
Structure Fichiers et Structures de Données
File and data structures

Coef : 4
VH Cours : 30.00
VH TD : 30.00
Pré-requis :
Structures de données dynamiques

Ingénierie des Compétences

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

Description du programme de la matière

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.

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,

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -