tnsi

1️⃣ Structures de données

Bulletin Officiel : contenu, capacités attendues

L’écriture sur des exemples simples de plusieurs implémentations d’une même structure de données permet de faire émerger les notions d’interface et d’implémentation, ou encore de structure de données abstraite. Le paradigme de la programmation objet peut être utilisé pour réaliser des implémentations effectives des structures de données, même si ce n’est pas la seule façon de procéder.

Contenu	Capacités attendues
Structures de données, interface et implémentation Dictionnaires, index et clé	- 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 - Distinguer la recherche d’une valeur dans une liste et dans un dictionnaire
Vocabulaire de la Programmation Orientée 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	- 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
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/de prédécesseurs - Passer d’une représentation à une autre