cours
cours1 min de lecture

Structures de données

Spécifier, choisir et implémenter les structures qui organisent les données — du tableau à l'arbre, en passant par les graphes.
programme

Au programme

Le chapitre TA fonde la fin du cycle Terminale sur une question centrale : comment organise-t-on les données pour pouvoir agir efficacement dessus ? Les algorithmes étudiés en parallèle au chapitre TE supposent presque tous une structure d'accueil adaptée — un parcours en largeur exige une file, une recherche dichotomique un tableau trié, un parcours d'arborescence une représentation hiérarchique.

Vous y apprenez à :

  • écrire des classes en Python, avec leurs attributs, leurs méthodes et la notion d'instance — le vocabulaire de la programmation orientée objet (TA05) — et séparer l'interface d'une structure de son implémentation (TA04), en raisonnant sur le contrat avant le code ;
  • mettre en pratique cette séparation en fournissant plusieurs codes possibles pour un même contrat — l'exemple canonique de la file FIFO implémentée par tableau puis par deux piles (TA04) ;
  • manipuler les structures linéaires : listes, piles (LIFO), files (FIFO), dictionnaires (TA03) ;
  • mesurer un arbre binaire : taille, hauteur, encadrement asymptotique (TA01) ;
  • représenter un graphe par matrice d'adjacence ou liste de successeurs, et passer d'une représentation à l'autre (TA02).

Pré-requis

Les bases Python de Première (listes, dictionnaires, fonctions) sont supposées acquises. Le chapitre PC (types construits) et PH (algorithmique de Première) sont des appuis utiles.

Plan

  1. Objet, classe, interface — TA04 + TA05 — classes, attributs, méthodes, self, encapsulation, et la distinction interface / implémentation, posées d'un seul tenant sur un exemple de compte bancaire.
  2. Implémenter une structure — la file FIFO — TA04 — application directe : une même file codée par un tableau puis par deux piles, complexité amortie.
  3. Listes, piles, files, dictionnaires — TA03 — les structures linéaires canoniques, caractérisées par leurs méthodes.
  4. Arbres binaires — TA01 — vocabulaire, mesures, encadrement de la hauteur.
  5. Graphes — TA02 — sommets, arêtes, orienté ou non, matrice d'adjacence et liste de successeurs.

À la fin du chapitre, une fiche mémo synthétique consolide les notions et propose une auto-évaluation. La source MDC d'évaluation notée (chapitre.eval.md) prépare le DS de fin de séquence.