Algorithmique avancée en Terminale
Cours complet, points clés à retenir et exercices d'entraînement de algorithmique avancée pour les élèves de Terminale. Conforme au programme officiel.
Réviser notion par notion
Ce que tu vas réviser
- Récursivité : principe, pile d'appels, cas de base
- Diviser pour régner : tri fusion, recherche dichotomique
- Programmation dynamique : mémoïsation, sous-problèmes
- Algorithmes sur les graphes : parcours en largeur (BFS) et profondeur (DFS)
- Recherche textuelle : algorithme naïf et Boyer-Moore
Récursivité : principe et pile d'appels
Une fonction récursive s'appelle elle-même pour résoudre un problème en le décomposant en sous-problèmes plus simples. Chaque appel s'empile en mémoire jusqu'à atteindre un cas de base qui arrête la récursion.
Exemple
Chercher un document dans des dossiers imbriqués : tu ouvres un dossier, et si tu trouves d'autres dossiers dedans, tu les ouvres de la même façon jusqu'à trouver le fichier.
À retenir : Toute fonction récursive doit avoir un cas de base pour éviter une boucle infinie et un débordement de pile.
Diviser pour régner : tri fusion
Le tri fusion divise le tableau en deux moitiés, les trie récursivement, puis les fusionne. C'est un algorithme en $O(n \log n)$ très efficace et stable.
Exemple
Trier une pile de 100 examens : tu les divises en deux piles de 50, tu tries chaque pile, puis tu les mets ensemble en ordre.
À retenir : Le tri fusion est plus lent que le tri rapide en moyenne mais garantit toujours $O(n \log n)$ et préserve l'ordre des éléments égaux.
Diviser pour régner : recherche dichotomique
La recherche dichotomique divise un tableau trié en deux et élimine la moitié où l'élément ne peut pas être. Elle répète jusqu'à trouver l'élément en $O(\log n)$.
Exemple
Chercher un mot dans un dictionnaire : tu ouvres au milieu, tu vois si le mot est avant ou après, puis tu recommences dans la bonne moitié.
À retenir : La recherche dichotomique ne fonctionne que sur un tableau trié et est beaucoup plus rapide que la recherche linéaire.
Programmation dynamique : mémoïsation
La mémoïsation stocke les résultats des sous-problèmes déjà calculés pour éviter de les recalculer. C'est une optimisation de la récursivité.
Exemple
Calculer la suite de Fibonacci : au lieu de recalculer fib(5) cent fois, tu le calcules une fois et tu le réutilises.
À retenir : La mémoïsation transforme une récursion exponentielle en complexité polynomiale en sauvegardant les résultats intermédiaires.
Programmation dynamique : sous-problèmes
La programmation dynamique résout un problème en le décomposant en sous-problèmes qui se chevauchent, puis combine leurs solutions optimales.
Exemple
Planifier un voyage : tu calcules le meilleur chemin pour chaque étape, puis tu les combines pour obtenir le meilleur trajet global.
À retenir : Un problème de programmation dynamique doit avoir une sous-structure optimale : la solution optimale se construit à partir de solutions optimales de sous-problèmes.
Parcours en profondeur : DFS
Le parcours en profondeur explore un graphe en allant aussi loin que possible dans une branche avant de revenir en arrière. Il utilise une pile (récursion ou structure).
Exemple
Explorer un labyrinthe : tu avances le plus loin possible dans un couloir, puis tu reviens en arrière pour essayer un autre chemin.
À retenir : DFS est utile pour détecter les cycles, trouver les composantes connexes et explorer tous les chemins possibles.
Parcours en largeur : BFS
Le parcours en largeur explore un graphe niveau par niveau, en visitant tous les voisins avant de passer aux suivants. Il utilise une file d'attente.
Exemple
Trouver le chemin le plus court dans un réseau : tu explores d'abord tous les voisins directs, puis leurs voisins, etc.
À retenir : BFS trouve toujours le chemin le plus court dans un graphe non pondéré et est plus efficace que DFS pour cette tâche.
Recherche textuelle : algorithme naïf
L'algorithme naïf cherche un motif dans un texte en le comparant à chaque position. C'est simple mais lent en $O(n \times m)$.
Exemple
Chercher le mot 'chat' dans un livre : tu lis chaque position et tu vérifies si les 4 lettres suivantes forment 'chat'.
À retenir : L'algorithme naïf est facile à comprendre mais inefficace sur de grands textes avec des motifs longs.
Recherche textuelle : algorithme Boyer-Moore
Boyer-Moore accélère la recherche en comparant le motif de droite à gauche et en sautant des positions quand un caractère ne correspond pas.
Exemple
Chercher 'chat' : si tu lis 'x' à la position du 't', tu sais que tu peux sauter plusieurs positions au lieu de vérifier chacune.
À retenir : Boyer-Moore est beaucoup plus rapide que l'algorithme naïf en pratique, surtout avec des alphabets grands et des motifs longs.
Les points clés
- La récursivité doit toujours avoir un cas de base pour terminer
- Diviser pour régner réduit la complexité en décomposant le problème
- La programmation dynamique évite de recalculer les mêmes sous-problèmes
- DFS explore en profondeur avec une pile, BFS explore en largeur avec une file
- Boyer-Moore est plus efficace que la recherche naïve grâce aux sauts intelligents
L'essentiel
L'algorithmique avancée combine récursivité, décomposition de problèmes et structures de données pour résoudre efficacement des problèmes complexes.
Exercices d'entraînement
Entraîne-toi sur ces exercices, puis fais-toi corriger pas à pas par le tuteur.
Exercice 1
Soit la fonction récursive suivante : ```python def mystere(n): if n == 0: return 1 else: return n * mystere(n - 1) ``` 1. Identifiez le cas de base et le cas récursif. 2. Tracez l'exécution de mystere(4) en dessinant la pile d'appels. 3. Que calcule cette fonction ?
Corrige cet exercice avec le tuteur →Exercice 2
On souhaite implémenter la **recherche dichotomique** sur un tableau trié. 1. Écrivez une fonction récursive `recherche_dichotomique(tab, cible, gauche, droite)` qui retourne l'indice de `cible` dans `tab`, ou -1 si absent. 2. Analysez la complexité temporelle en fonction de la taille n du tableau. 3. Testez avec `tab = [1, 3, 5, 7, 9, 11]` et `cible = 7`.
Corrige cet exercice avec le tuteur →