Programme officiel

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.

Séquences

Partie I

  1. Les structures linéaires
  2. Dictionnaires, index et clé.

Partie II

  1. Structures hiéarchiques : les arbres
  2. Structures relationnelles : les graphes

TP Jupyter

  1. TP sur les piles, files
  2. TP sur les dictionnaires et la performance du hachage
  3. Initiation à la Programmation Orientée Objet
  4. Créer une classe pour représenter une liste chaînée
  5. Créer une classe pour représenter un arbre binaire
  6. TP sur les graphes

sources