NSI (Spé) — Algorithmique
Programmation dynamique et recherche textuelle
Principe de la programmation dynamique, mémoïsation, exemples classiques, algorithme de recherche textuelle naïve
Résumé synthétiqueFiche en 4 sectionsQuiz de 10 questionsGratuit, sans pub
Résumé
Calculer fib(50) naïvement peut prendre… des minutes, alors que la valeur tient en un instant : le programme recalcule sans cesse les mêmes choses. La programmation dynamique corrige ce gaspillage. Son idée : découper un problème en sous-problèmes qui se chevauchent, puis mémoriser chaque résultat pour ne le calculer qu'une fois. Sur Fibonacci, on passe ainsi de $O(2^n)$ (exponentiel, ingérable) à $O(n)$ (linéaire). Deux variantes : top-down (récursif + mémoïsation) et bottom-up (itératif, on remplit un tableau). Le rendu de monnaie illustre qu'une approche gloutonne peut échouer là où la programmation dynamique trouve l'optimum. On termine par la recherche textuelle : repérer un motif dans un texte, en $O(n \times m)$ pour la méthode naïve.
La programmation dynamique s'applique quand un problème se décompose en sous-problèmes qui reviennent plusieurs fois. Plutôt que de les recalculer, on stocke leur résultat. C'est l'art d'échanger un peu de mémoire contre énormément de temps.
- S'applique quand les sous-problèmes se chevauchent (les mêmes reviennent encore et encore).
- Deux conditions : sous-structure optimale (la solution optimale se compose de sous-solutions optimales) et chevauchement.
- Top-down : récursif + mémoïsation (on garde en cache ce qu'on a déjà calculé).
- Bottom-up : itératif, on remplit un tableau des petits cas vers les grands.
- Différence avec diviser-pour-régner : là, les sous-problèmes sont indépendants (tri fusion) ; ici, ils se recoupent.
- Mémoïsation : ranger les résultats dans un dictionnaire ou un tableau pour réutilisation immédiate.
Exemple
Sans mémoïsation, calculer fib(5) déclenche le calcul de fib(3) deux fois et de fib(2) trois fois. Sur fib(50), ces répétitions explosent en milliards d'appels : c'est exactement ce chevauchement que la programmation dynamique élimine.
Piège à éviter
Ne pas repérer le chevauchement et garder la récursivité naïve mène à une complexité exponentielle $O(2^n)$, vite inutilisable. Le réflexe : « les mêmes sous-calculs reviennent-ils ? » → si oui, mémoïser.
Fibonacci est l'exemple-roi : la version récursive naïve recalcule sans fin les mêmes termes. La mémoïsation garde chaque fib(k) en mémoire après son premier calcul, faisant chuter la complexité de $O(2^n)$ à $O(n)$.
Calcul naïf de fib(5) : fib(3) est recalculé 2 fois, fib(2) 3 fois. La mémoïsation ne calcule chaque valeur qu'une seule fois.
- Récursif naïf : fib(n) = fib(n-1) + fib(n-2). Complexité $O(2^n)$, inutilisable au-delà de n ≈ 35.
- Cause : un même fib(k) est recalculé un grand nombre de fois.
- Mémoïsation (top-down) : un dictionnaire memo ; si n in memo, on renvoie directement. Complexité $O(n)$.
- Bottom-up (itératif) : remplir un tableau de fib(0) à fib(n). Complexité $O(n)$.
- Optimisation mémoire : deux variables suffisent (le terme courant et le précédent) → mémoire $O(1)$.
- Le passage de $O(2^n)$ à $O(n)$ résume toute la puissance de la programmation dynamique.
Exemple
memo = {}
def fib(n):
if n <= 1:
return n
if n in memo: # déjà calculé : réutilisation
return memo[n]
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
# fib(50) est maintenant instantané.
def fib(n):
if n <= 1:
return n
if n in memo: # déjà calculé : réutilisation
return memo[n]
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
# fib(50) est maintenant instantané.
Piège à éviter
En mémoïsation, pense à enregistrer le résultat (memo[n] = ...) AVANT de le renvoyer : si tu renvoies fib(n-1) + fib(n-2) sans le stocker dans memo, le cache reste vide et la complexité retombe à $O(2^n)$.
Rendre une somme avec le moins de pièces possible semble facile : prendre à chaque fois la plus grosse pièce. Cette stratégie gloutonne échoue pourtant sur certains systèmes de pièces — là où la programmation dynamique garantit l'optimum.
- Problème : avec un système de pièces (ex. 1, 2, 5, 10), atteindre une somme S avec un minimum de pièces.
- Glouton : prendre la plus grande pièce ≤ somme restante. Rapide mais pas toujours optimal.
- Contre-exemple : pièces 1, 3, 4 et S = 6 → glouton 4 + 1 + 1 = 3 pièces, optimal 3 + 3 = 2 pièces.
- Dynamique : nb[s] = 1 + min(nb[s - p]) pour chaque pièce p ≤ s, avec nb[0] = 0.
- On remplit un tableau nb de taille S + 1 : nb[s] = nombre minimal de pièces pour la somme s.
- Complexité : $O(S \times k)$ en temps (k = nombre de pièces), $O(S)$ en mémoire.
Exemple
def rendu(S, pieces):
nb = [0] + [float('inf')] * S # nb[0] = 0
for s in range(1, S + 1):
for p in pieces:
if p <= s:
nb[s] = min(nb[s], nb[s - p] + 1)
return nb[S]
# rendu(6, [1, 3, 4]) -> 2
nb = [0] + [float('inf')] * S # nb[0] = 0
for s in range(1, S + 1):
for p in pieces:
if p <= s:
nb[s] = min(nb[s], nb[s - p] + 1)
return nb[S]
# rendu(6, [1, 3, 4]) -> 2
Piège à éviter
Croire que le glouton donne toujours l'optimum pour le rendu de monnaie est une erreur classique. Il ne le garantit que pour des systèmes de pièces particuliers (dits canoniques, comme l'euro). En général, seule la programmation dynamique assure le minimum.
Trouver un motif dans un texte (un mot dans un document) est une opération omniprésente. La méthode naïve teste toutes les positions de départ ; des algorithmes plus malins sautent des positions pour aller plus vite.
- Problème : repérer les occurrences d'un motif P (longueur m) dans un texte T (longueur n).
- Algorithme naïf : pour chaque position i de 0 à n - m, comparer T[i:i+m] avec P.
- Complexité du naïf : $O(n \times m)$ dans le pire cas (ex. texte « aaaaab », motif « aab »).
- Boyer-Moore : compare de droite à gauche et saute des positions grâce au caractère non concordant ; très rapide en pratique.
- En Python : motif in texte ou texte.find(motif) utilisent des implémentations optimisées.
- Applications : recherche dans un éditeur, grep dans le terminal, moteurs de recherche.
Exemple
def recherche_naive(T, P):
positions = []
n, m = len(T), len(P)
for i in range(n - m + 1):
if T[i:i + m] == P: # comparaison de la fenêtre
positions.append(i)
return positions
# recherche_naive('abcabc', 'bc') -> [1, 4]
positions = []
n, m = len(T), len(P)
for i in range(n - m + 1):
if T[i:i + m] == P: # comparaison de la fenêtre
positions.append(i)
return positions
# recherche_naive('abcabc', 'bc') -> [1, 4]
Piège à éviter
La recherche naïve atteint son pire cas $O(n \times m)$ sur des textes très répétitifs (« aaaaa… »). Pour de gros volumes, on préfère Boyer-Moore ou les fonctions intégrées de Python plutôt que de recoder la version naïve.
Quiz - Programmation dynamique et recherche textuelle
10 questions
S'entraîner
- Quiz : Programmation dynamique et recherche textuelle10 questions corrigées sur ce chapitre
- Bac 2026 NSI – MétropoleSujet officiel
- Bac 2025 NSI – MétropoleSujet officiel
- Bac 2024 NSI – MétropoleSujet officiel
- Annales du bac de NSITous les sujets officiels, par année
- Coefficient de NSI au bacPoids de l'épreuve dans la note finale
Thème complet
Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale
Ce thème dans une autre classe
Articles utiles
Questions fréquentes
Les points clés à retenir sur Programmation dynamique et recherche textuelle, extraits du quiz de révision.
La programmation dynamique s'applique quand les sous-problèmes :
Réponse :
Se chevauchent (les mêmes apparaissent plusieurs fois)
La programmation dynamique est utile quand les sous-problèmes se chevauchent : les mêmes calculs reviennent plusieurs fois. La mémoïsation évite de les refaire.
Quelle est la complexité du calcul récursif naïf de Fibonacci ?
Réponse :
O(2ⁿ)
L'appel récursif naïf de fib(n) engendre un arbre d'appels de taille exponentielle O(2ⁿ), car fib(n) appelle fib(n-1) et fib(n-2), et ces appels se dédoublent.
La mémoïsation consiste à :
Réponse :
Stocker les résultats déjà calculés pour ne pas les recalculer
La mémoïsation stocke les résultats des sous-problèmes dans une structure (dictionnaire, tableau) pour les réutiliser directement si le même sous-problème se présente.
Avec la mémoïsation, quelle est la complexité du calcul de fib(n) ?
Réponse :
O(n)
Avec la mémoïsation, chaque valeur fib(k) n'est calculée qu'une seule fois et stockée. Il y a n valeurs à calculer, d'où une complexité O(n).