[B] Structures de données

[B.1] Structures de données, interface et implémentation

Contenus :

• Structures de données, interface et implémentation

Capacités attendues :

• Spécifier une structure de données par son interface.
• Distinguer interface et implémentation.
• Ecrire plusieurs implémentations d’une même structure de données.

Commentaires :

• 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)

[B.2] Programmation orientée objet.

Contenus :

• Vocabulaire de la programmation orientée objet : classes, attributs, méthodes, objets

Capacités attendues :

• Ecrire la définition d’une classe.
• Accéder aux attributs et méthodes d’une classe.

Commentaires :

• On n’aborde pas ici tous les aspects de la programmation objet comme le polymorphisme et l’héritage.

[B.3] Listes, piles, files et dictionnaires

Contenus :

• Listes, piles, files : structures linéaires.
• Dictionnaires, index et clé.

Capacités attendues :

• Distinguer les 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.

Commentaires :

• On distingue les modes FIFO (first in first out) et LIFO (last in first out) des piles et des files.

[B.4] Arbres

Contenus :

• Arbres : structures hiérarchiques.
• Arbres binaires : nœuds, racines, feuilles, sous-arbres gauches, sous-arbres droits.

Capacités attendues :

• Identifier des situations nécessitant une structure de données arborescente.
• Evaluer quelques mesures des arbres binaires (taille, encadrement de la hauteur, etc.)

Commentaires :

• On fait le lien avec la rubrique « algorithmique »

[B.5] Graphes

Contenus :

• Graphes : structures relationnelles.
• Sommets, arcs, arêtes, graphes orientés ou non orientés.

Capacités attendues :

• Modéliser des situations sous forme de graphes.
• Ecrire les implémentations correspondantes d’un graphe : matrice d’adjacence, liste de successeurs, de prédécesseurs.
• Passer d’une représentation à une autre.

Commentaires :

• 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 ».