Structuration des Données Informatiques

Initiation et applications

Table des matières

(Sont aussi disponibles: la description du cours, un article en anglais, une liste de questions d'examen en format Postscript, une liste des questions d'examens avec leurs corrigés, des enregistrements du cours + évaluation du cours par les étudiants)

Introduction

Chapitre 1. Notion de typage

1.1.Différence de typage selon les langages

1.2. Contrôle de typage

1.2.1. Equivalence de nom

1.2.2. Equivalence de structure

1.2.3. Cas de quelques langages d'usage courant

1.3. Nomenclature

Chapitre 2. Les types scalaires

2.1. Les types discrets

2.1.1. Les entiers

2.1.2. Les types énumérés

2.1.3. Les intervalles

2.2.Fonctions prédéfinies sur les types discrets

2.3. Les réels

2.3.1. Représentation en virgule flottante

2.3.2. Représentation en virgule fixe

2.4.Compatibilité et conversion de types

2.4.1. Compatibilité

2.4.2. Conversion de type

Chapitre 3. Les structures statiques

3.1. Structures cartésiennes simples ( exercices disponibles)

3.1.1. Les tableaux

3.1.2. Les enregistrements

3.1.3. Les ensembles

3.2. Cardinalité

3.3. Structures cartésiennes complexes

3.3.1. Tableaux multidimensionnés
3.3.2. Tableaux d'enregistrements
3.3.3. Enregistrement de tableaux
3.3.4. Les chaînes de caractères

3.4. Structures paquetées

3.4.1. Cas des tableaux
3.4.2. Cas des enregistrements

Chapitre 4. Les types abstraits

4.1. Exemple : les tableaux

4.2. Exemple : les ensembles

4.3. Exemple : chaînes de caractères de longueur variable.

Chapitre 5. Les structures dynamiques

5.1. Les pointeurs

5.2. Ramassage des miettes, réutilisation de la mémoire

5.2.1. Ramassage des miettes
5.2.2. Chaînage des trous

Chapitre 6. Structures dynamiques linéaires non-récursives : les fichiers

6.1. Primitives de manipulation

6.2. Utilisation

6.3. Fichiers TEXT

Chapitre 7. Structures récursives linéaires : les chaînes

7.1. Construction ( exercices disponibles)

7.2. modification ( exercices disponibles)

7.3. Utilisation

7.3.1. Parcours
7.3.2. Recherche d'un élément

7.4. Anneaux, chaînes bidirectionnelles ( exercices disponibles)

7.4.1. Les anneaux
7.4.2. Les chaînes bidirectionnelles
7.4.3. Les anneaux bidirectionnels

7.5. Utilisation d'un élément sans données

7.6. Structures auxiliaires : Piles, files d'attente, files circulaires

7.6.1. Piles
7.6.2. Files d'attente
7.6.3. Représentation et implantation

Chapitre 8. Structures récursives non linéaires : les arbres

8.1. Les arbres binaires ordonnés ( exercices disponibles)

8.1.1. Arbres syntaxiques
8.1.2. Arbres de tri
8.1.3. Opérations sur les arbres

8.2. Arbres multiples ( exercices disponibles)

8.2.1.Représentation d'arbre multiple sous forme d'arbre binaire

8.3. Représentation d'arbres à l'aide de tableaux

8.3.1. Arbres dépliables ( exercices disponibles)

8.4. Rééquilibrage d'arbres

Chapitre 9. Structures récursives non linéaires : les listes

9.1. Opérations sur les listes ( exercices disponibles)

9.2. Détermination de l'appartenance à une liste

9.3. Partage d'éléments entre listes

9.4. Isomorphisme liste-arbre

Chapitre 10. Structures récursives non linéaires : les graphes

10.1. Nomenclature

10.2. Représentation

10.2.1. Matrice de connectivité
10.2.2. Liste de connectivité
10.2.3. Structure entièrement dynamique

10.3. Recherche en profondeur ( exercices disponibles)

10.3.1. Détection de cycles
10.3.2. Détermination des composantes connexes

10.4. Recherche en largeur ( exercices disponibles)

10.4.1. Méthode générale de parcours de graphe
10.4.2. Méthode générale appliquée au DFS
10.4.3. Méthode générale appliquée au BFS

10.5. Parcours d'un labyrinthe

Chapitre 11. Structures récursives non linéaires : les graphes orientés

11.1. Représentation d'un graphe orienté

11.2. Depth-First Search

11.3. Fermeture transitive ( exercices disponibles)

11.4. Le tri topologique

11.5. Tri topologique inverse ( exercices disponibles)

11.6. Composante fortement connexe d'un graphe orienté ( exercices disponibles)
Autres exercices disponibles

Chapitre 12. Structures récursives non linéaires : les réseaux

12.1. Capacité et écoulement

12.2. Représentation d'un réseau

12.3. Amélioration d'une fonction d'écoulement

12.4. Ecoulement optimal

Chapitre 13. Structures adressables par leur contenu : adressage associatif

13.1. Notion de clé

13.2. Recherche séquentielle

13.3. Recherche dans un tableau ordonné ( exercices disponibles)

13.3.1. Recherche binaire (ou dichotomique, ou logarithmique)
13.3.2. Recherche par interpolation

13.4. Hash-coding ("transformation de clés") ( exercices disponibles)

13.4.1. Chaînage externe
13.4.2. L'adressage ouvert

13.5. Les fonctions de h-code

13.5.1. Les méthodes de division
13.5.2. Les méthodes multiplicatives

Chapitre 14. Structures à support mixte

14.1. Mémoire virtuelle

14.2. Fichiers séquentiels indexés ( exercices disponibles)

14.2.1. Implantation
14.2.2. Mise-à-jour de fichiers séquentiels indexés
14.2.3. Clés secondaires

14.3. B-arbres (ou arbres de Bayer) ( exercices disponibles)

14.3.1. Recherche dans un B-arbre
14.3.2. Insertion
14.3.3. Structure de données (représentation interne)
14.3.4. Suppression d'un élément

Chapitre 15. Tables et arbres de décision

15.1. Les tables de décision ( exercices disponibles)

15.1.1. Propriétés des tables de décision
15.1.2. Description en terme de type abstrait
15.1.3. Exemple d'implantation
15.1.4. Conversion de tables de décisions en cascade de tests

15.2. Arbres de décision

15.2.1. Parcours d'un labyrinthe
15.2.2. Jeux de nim
15.2.3. Le jeux du Tic-Tac-Toe

15.3. Réalisation d'une procédure MiniMax

15.3.1. Variante de la méthode MiniMax : l'élagage alpha-bêta

Bertrand Ibrahim

Site Hosting: Bronco