| Contenus | Capacités attendues |
|---|---|
| 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. |
| 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. |
| Listes, piles, files : structures linéaires. Dictionnaires, index et clé. |
Distinguer des structures par le jeu 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. |
| 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.). |
| 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/prédécesseurs. Passer d’une représentation à une autre. |