Programme officiel

Contenus Capacités attendues
Algorithmes sur les arbres binaires et sur les arbres binaires de recherche.

Calculer la taille et la hauteur d’un arbre.

Parcourir un arbre de différentes façons (ordres infixe, préfixe ou suffixe ; ordre en largeur d’abord).

Rechercher une clé dans un arbre de recherche, insérer une clé.

Algorithmes sur les graphes.

Parcourir un graphe en profondeur d’abord, en largeur d’abord.

Repérer la présence d’un cycle dans un graphe.

Chercher un chemin dans un graphe.

Méthode « diviser pour régner ». Écrire un algorithme utilisant la méthode « diviser pour régner ».
Programmation dynamique. Utiliser la programmation dynamique pour écrire un algorithme.
Recherche textuelle. Étudier l’algorithme de Boyer-Moore pour la recherche d’un motif dans un texte.

Séquences

Partie I

  1. Algorithmes sur les arbres
  2. Algorithmes sur les graphes

Partie II

  1. Diviser pour régner
  2. Programmation dynamique

Partie III

  1. Algorithme de Boyer-Moore

TP Jupyter

  1. Mise en pratique des algorithmes sur les arbres
  2. Mise en pratique des algorithmes sur les graphes

sources

  • Le site pixees de David Roche
  • Le site NSI d'Alain Busser
  • Le site NSI de M. Pelegrina