| Structures de données, interface et implémentation. | Spécifier une structure de données par son interface.
Distinguer interface et implémentation. Écrire plusieurs implémentations
d’une même structure de données | L’abstraction des structures de
données est introduite après plusieurs implémentations d’une structure simple comme la file (avec un tableau ou avec deux piles). |
| Vocabulaire de la programmation objet : classes, attributs, méthodes, objets. | Écrire la définition d’une classe. Accéder aux attributs et méthodes d’une classe. | On n’aborde pas ici tous les aspects de la programmation objet comme le polymorphisme et l’héritage. |
| Listes, piles, files : structures linéaires.
Dictionnaires, index et clé. | Distinguer des structures par le jeun des méthodes qui les caractérisent.
Choisir une structure de données adaptée à la situation à modéliser.
Distinguer la recherche d’une valeur dans une liste et dans un dictionnaire. | On distingue les modes FIFO (first in first out) et LIFO (last in first out) des piles et des files. Les listes n’existent pas de façon native en Python. |
| Arbres : structures hiérarchiques. Arbres binaires : nœuds, racines,
feuilles, sous-arbres gauches, sous-arbres droits. | Identifier des situations nécessitant une structure de données arborescente.
Évaluer quelques mesures des arbres binaires (taille, encadrement de la hauteur, etc.). | On fait le lien avec la rubrique « algorithmique ». |
| Graphes : structures relationnelles. Sommets, arcs, arêtes, graphes orientés ou non orientés. | Modéliser des situations sous forme de graphes.
Écrire les implémentations correspondantes d’un graphe : matrice d’adjacence, liste de successeurs/de prédécesseurs.
Passer d’une représentation à une autre. | On s’appuie sur des exemples comme le réseau routier, le réseau électrique, internet, les réseaux sociaux.
Le choix de la représentation dépend du traitement qu’on veut mettre en place : on fait le lien avec la rubrique « algorithmique ». |