Algorithmique

Au programme

Le chapitre TE rassemble les cinq grandes méthodes algorithmiques au programme de Terminale. Là où le chapitre TA pose les structures de données — arbres, graphes, piles, files — ce chapitre TE en exploite la matière : il s'agit maintenant de calculer, de parcourir, de rechercher, d'optimiser.

Vous y apprendrez à :

• mesurer et parcourir un arbre binaire — taille, hauteur, parcours infixe, préfixe, suffixe, parcours en largeur ; rechercher et insérer une clé dans un arbre binaire de recherche (TE01) ;
• explorer un graphe en profondeur (DFS) et en largeur (BFS), détecter un cycle, trouver un chemin — l'exemple du labyrinthe et celui du routage Internet (TE02) ;
• appliquer la méthode « diviser pour régner » — le tri fusion comme exemple canonique d'un coût en $\mathcal{O}(n \log n)$, et le théorème maître pour l'analyser (TE03) ;
• résoudre par programmation dynamique — mémoïsation top-down et tabulation bottom-up, sur l'exemple du rendu de monnaie et de l'alignement de séquences (TE04) ;
• rechercher un motif dans un texte avec l'algorithme de Boyer-Moore, qui prétraite le motif pour aller plus vite que la force brute (TE05).

Plan

1. Algorithmes sur les arbres binaires — TE01 — taille, hauteur, parcours infixe/préfixe/suffixe, parcours en largeur, recherche et insertion dans un ABR.
2. Algorithmes sur les graphes — TE02 — DFS et BFS, détection de cycle, recherche de chemin ; labyrinthe et routage en illustration.
3. Diviser pour régner — TE03 — le tri fusion, le théorème maître, la rotation d'une image bitmap en mémoire constante.
4. Programmation dynamique — TE04 — rendu de monnaie, plus court chemin sur grille, alignement de séquences ; mémoïsation top-down vs tabulation bottom-up.
5. Recherche textuelle — TE05 — Boyer-Moore, prétraitement du motif, règle du mauvais caractère.

À la fin du chapitre, une fiche mémo synthétique consolide les coûts et les schémas, et une auto-évaluation permet de jauger sa maîtrise. La source MDC d'évaluation notée (chapitre.eval.md) prépare le DS de fin de séquence — elle inclut des exercices ::python-exec pour pratiquer en conditions.