Structures de données abstraites
En informatique, un type de données abstrait (ADT) est un modèle mathématique pour les types de données où un type de données est défini par son comportement (sémantique) à partir de le point de vue d’un utilisateur des données, notamment en termes de valeurs possibles, d’opérations possibles sur des données de ce type, et le comportement de ces opérations. Cela contraste avec les structures de données, qui sont des représentations concrètes des données et qui sont le point de vue d’un implémenteur et non d’un utilisateur.
Formellement, un ADT peut être défini comme une « classe d’objets dont le comportement logique est défini par un ensemble de valeurs et un ensemble d’opérations » ; ceci est analogue à une structure algébrique en mathématiques. Ce que l’on entend par « comportement » varie selon l’auteur, les deux principaux types de spécifications formelles pour le comportement étant la spécification axiomatique (algébrique) et un modèle abstrait; ceux-ci correspondent respectivement à la sémantique axiomatique et à la sémantique opérationnelle d’une machine abstraite. Certains auteurs incluent également la complexité de calcul (« coût »), à la fois en termes de temps (pour les opérations de calcul) et d’espace (pour la représentation des valeurs).
La raison pour laquelle nous utilisons des structures abstraites est qu’elles utilisent efficacement la mémoire basée sur la conception des données qui y sont stockées. Avec de très grandes quantités de données ou des données qui changent très fréquemment, la structure des données peut faire une énorme différence dans l’efficacité (temps d’exécution) de votre programme informatique.
Dans un langage plus courant, une structure de données abstraite n’est qu’un arrangement de données que nous avons intégré dans un arrangement ordonné.
Une vue d’ensemble parfaite
Quelques types de structures de données abstraites
Évaluées par l’IB
- structure de données statique et dynamique
- tableaux
- tableaux bidimensionnels
- pile
- file d’attente
- liste chaînée
- arbre
- binaire arbre
- collections
- récursivité
NON évalué par l’IB, mais vous devriez les connaître
- listes
- dictionnaires
- ensembles
- tuple
Opérations de base des structures de données
J’ai trouvé cette excellente diapositive de Simon Allardice.
Comparaison de différentes structures de données
| Structure de données | Forces | Faiblesses |
| tableaux | Insertion et suppression d’éléments, en parcourant la collection | Tri et recherche, Insertion et suppression – surtout si vous insérez et supprimez au début ou à la fin du tableau |
| liste chaînée | indexation directe, facile à créer et à utiliser | accès direct, recherche et tri |
| pile et file d’attente | conçu pour LIFO/FIFO | accès direct, recherche et tri |
| arbre binaire | vitesse d’insertion et de suppression, vitesse d’accès, maintien de l’ordre trié | certains frais généraux |
- Les structures fixes sont plus rapides / plus petites
- Lorsque vous envisagez d’utiliser une structure de données abstraite, vous devriez vous demander: qu’est-ce qui contient le plus de données et qu’est-ce qui contient les données les plus fréquemment modifiées?
Comparaison des structures de données statiques et dynamiques
Cette comparaison est utilisée dans notre manuel d’informatique.
| Structure de données statique | Structure de données dynamique |
| Inefficace car la mémoire est allouée et peut ne pas être nécessaire. | Efficace car la quantité de mémoire varie selon les besoins. |
| Accès rapide à chaque élément de données car l’emplacement de la mémoire est fixé lors de l’écriture du programme. | Accès plus lent à chaque élément car l’emplacement mémoire est alloué au moment de l’exécution. |
| Les adresses mémoire allouées seront contiguës pour un accès plus rapide. | Les adresses mémoire allouées peuvent être fragmentées, ce qui ralentit l’accès. |
| Les structures ont une taille fixe, ce qui les rend plus prévisibles. Par exemple, ils peuvent contenir un en-tête. | Les structures varient en taille, il doit donc y avoir un mécanisme pour connaître la taille de la structure actuelle. |
| La relation entre les différents éléments de données ne change pas. | La relation entre les différents éléments de données changera au fur et à mesure de l’exécution du programme. |
Choisir la structure de données à utiliser
Ce graphique est utilisé avec une immense gratitude du département d’informatique de la Dartford Grammar School.
- Identifient une situation qui nécessite l’utilisation de la pensée récursive.
- Identifiez la pensée récursive dans une solution de problème spécifiée.
- Trace un algorithme récursif pour exprimer une solution à un problème.
- Décrire les caractéristiques d’un réseau bidimensionnel.
- Construire des algorithmes à l’aide de tableaux bidimensionnels.
- Décrire les caractéristiques et les applications d’une pile.
- Construire des algorithmes en utilisant les méthodes d’accès d’une pile.
- Décrire les caractéristiques et les applications d’une file d’attente.
- Construire des algorithmes en utilisant les méthodes d’accès d’une file d’attente.
- Explique l’utilisation des tableaux comme piles statiques et files d’attente.
- Décrire les caractéristiques et les caractéristiques d’une structure de données dynamique.
- Décrivez le fonctionnement logique des listes chaînées.
- Listes chaînées d’esquisses (simples, doubles et circulaires).
- Décrire les caractéristiques et les applications d’une collection.
- Construire des algorithmes en utilisant les méthodes d’accès d’une collection.
- Discuter de la nécessité de sous-programmes et de collections au sein de solutions programmées.
- Construire des algorithmes en utilisant des sous-programmes prédéfinis, des tableaux unidimensionnels et/ou des collections.
- Décrivez comment les arbres fonctionnent logiquement (binaires et non binaires).
- Définir les termes: parent, enfant gauche, enfant droit, sous-arbre, racine et feuille.
- Indique le résultat de la traversée de l’arbre inorder, postorder et précommande.
- Esquisser des arbres binaires.
- Définit le terme structure de données dynamique.
- Comparez l’utilisation de structures de données statiques et dynamiques.
- Suggère une structure adaptée à une situation donnée.
Leave a Reply