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)$.
- **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é.
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
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]
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
Thème complet
Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale
Ce thème dans une autre classe
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).