|
PARTIE 1 : STRUCTURES DE
DONNÉES
Les
listes linéaires chaînées
Notion d'allocations statique et dynamique
Définition d'une liste linéaire chaînée
Modèle sur les listes linéaires chaînées
Exemple d'introduction
Algorithmes sur les listes
Listes linéaires chaînées particulières
Implémentation des listes linéaires chaînées avec la représentation
contiguë
Les listes en Pascal
Les files d'attente
Définition, principe, domaine d'application
Modèle
Implémentation
Les
piles
Définition, principe, domaine d'application
Modèle
Implémentation
Récursivité
Exemples d'introduction
Conception d'algorithmes récursifs
Sémantique de la récursivité
Passage d'algorithmes récursifs en algorithme itératifs
Récursivité en pascal
Les arbres
Définitions
Terminologie
Les arbres binaires
Modèle sur les arbres binaires
Parcours des arbres binaires
Arbres de recherche binaire
Application des arbres binaires
Implémentation des arbres binaires
Arbres
AVL
Les arbres m-aires
Les
arbres de recherche m-aires
Arbres
B, Arbres 2-3 ,Arbres 2-3-4
Arbres Red-Black
Implémentation des arbres
de recherche m-aires
Les graphes
Graphes orientés et non orientés
Modèle sur les graphes
Parcours des graphes : DFS & BFS
Quelques
applications sur les graphes
Implémentation
Hachage
Introduction, définitions
Fonctions de hachage
Méthodes de résolution des collisions
Comparaison entre les différentes méthodes
Étude de la distribution des données
Hachage dynamique
PARTIE
2 : STRUCTURES DE FICHIERS
Une
introduction aux structures de fichiers
Raisons de l'utilisation de l'espace secondaire
Problèmes avec le stockage externe
Différence entre la RAM et la mémoire secondaire
Fichier
Bloc d'en-tête
Fichiers statique et dynamique
Méthode d'accès
Organisation du fichier
Adressage
Critère de mesure d'une méthode d'accès
Dans les langages de programmation
Algorithmes
Objectifs du cours
Structures simples de fichiers
Fichier vu comme un tableau
Fichier vu comme une liste linéaire chaînée
Remarques
Récapitulatif
Utilisation
Exemple : recherche dichotomique
Les méthodes d'index
Des structures simples aux méthodes d'index
Index à un niveau
Index à 2 niveaux
Opérations de base
Remarques
Avantages des méthodes d'index
Indexation pour l'accès multi-clés
Introduction
Organisation d'un index secondaire
Exemple de combinaison de clés secondaires
Remarque
Les méthodes d'arbres
Des
méthodes d'index aux méthodes d'arbres
Arbres
de recherche m-aire
Les
B-arbres
Variantes
des B-arbres
Les méthodes de hachage
Introduction
Chaînage avec des listes séparées
Adressage ouvert
Avantages et inconvénients
|
