tnsi

5️⃣ Algorithmique

Bulletin Officiel : contenu, capacités attendues

Le travail de compréhension et de conception d’algorithmes se poursuit en terminale notamment via l’introduction des structures d’arbres et de graphes montrant tout l’intérêt d’une approche récursive dans la résolution algorithmique de problèmes. On continue l’étude de la notion de coût d’exécution, en temps ou en mémoire et on montre l’intérêt du passage d’un coût quadratique en n² à nlog₂n ou de n à nlog₂n. Le logarithme en base 2 est ici manipulé comme simple outil de comptage (taille en bits d’un nombre entier).

Contenu	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