États
Identifier précisément les sous-problèmes à résoudre.
Terminale NSI • Algorithmique • QCM /20
La programmation dynamique
Résoudre efficacement un problème en réutilisant les résultats des sous-problèmes déjà calculés.
F₀ → F₁ → F₂ → F₃
1. Pourquoi la programmation dynamique ?
Éviter de résoudre plusieurs fois le même problème.
Certains problèmes se décomposent en sous-problèmes qui se recouvrent. La programmation dynamique calcule chaque état utile une seule fois et réutilise sa valeur. Elle s'appuie sur une relation de récurrence et des cas de base.
Transition
Exprimer chaque résultat à partir d'états plus petits.
Mémorisation
Conserver les résultats pour éviter les recalculs.
Attention : la programmation dynamique ne s'applique pas automatiquement à toute récursion. Elle est particulièrement intéressante quand des sous-problèmes identiques réapparaissent et que leurs solutions peuvent être combinées.
2. Fibonacci : le problème des recalculs
F(0)=0, F(1)=1 et F(n)=F(n−1)+F(n−2) pour n ≥ 2.
def fib_naif(n):
if n < 2:
return n
return fib_naif(n - 1) + fib_naif(n - 2)Par exemple, fib_naif(5) appelle fib_naif(4) et fib_naif(3) ; le calcul de fib_naif(4) appelle encore fib_naif(3). L'arbre des appels répète les mêmes calculs : son temps d'exécution croît exponentiellement.
3. Mémoïsation : approche descendante
Top-down : conserver les résultats des appels récursifs.
def fib_memo(n, memo=None):
if memo is None:
memo = {0: 0, 1: 1}
if n not in memo:
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
print(fib_memo(10)) # 55Le dictionnaire memo associe chaque indice à sa valeur. Chaque état de 0 à n est calculé au plus une fois : temps O(n), mémoire O(n). Comme l'algorithme reste récursif, une valeur de n très élevée peut provoquer une RecursionError en Python.
4. Tabulation : approche ascendante
Bottom-up : construire les résultats du plus petit au plus grand.
def fib_table(n):
if n < 2:
return n
table = [0, 1]
for i in range(2, n + 1):
table.append(table[i - 1] + table[i - 2])
return table[n]Cette version a également un temps O(n) et une mémoire O(n). Elle évite la profondeur de récursion.
Optimisation mémoire
def fib_optimise(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return aSeules les deux valeurs précédentes sont utiles : temps O(n), mémoire supplémentaire O(1).
5. Animation : construction de la table Fibonacci
Observe la relation entre chaque état et les deux précédents.
Simulateur pas à pas
6. Autre exemple : monter un escalier
À chaque mouvement, on monte une ou deux marches.
Notons W(n) le nombre de façons d'atteindre la marche n. Le dernier mouvement vient de la marche n−1 (un pas) ou n−2 (deux pas), donc :
W(0)=1, W(1)=1 et W(n)=W(n−1)+W(n−2) pour n ≥ 2.
def nb_facons(n):
a, b = 1, 1
for _ in range(n):
a, b = b, a + b
return a
print(nb_facons(4)) # 5Pour 4 marches, les cinq possibilités sont : 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 et 2+2.
7. Comparer les méthodes
Complexités pour calculer F(n).
| Méthode | Temps | Mémoire | Point important |
|---|---|---|---|
| Récursion naïve | Exponentiel | O(n) pile d'appels | Recalculs nombreux |
| Mémoïsation | O(n) | O(n) | Dictionnaire et récursion |
| Tabulation | O(n) | O(n) | Table remplie progressivement |
| Tabulation optimisée | O(n) | O(1) | Deux variables suffisent |
Ces complexités supposent que les opérations arithmétiques élémentaires sont en temps constant ; pour de très grands entiers, leur coût réel augmente avec le nombre de chiffres.
8. Exercices corrigés
Essaye de répondre avant d'ouvrir la correction.
Exercice 1 : calculer F(7) à partir de F(0)=0 et F(1)=1.
F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8 et F(7)=13.
Exercice 2 : expliquer pourquoi mémoïser F(5) évite des calculs.
F(3), F(2), etc., apparaissent dans plusieurs branches de l'arbre d'appels. Une fois leurs résultats mémorisés, les appels suivants utilisent directement la valeur enregistrée.
Exercice 3 : combien de façons de monter 5 marches avec des pas de 1 ou 2 ?
W(0)=1, W(1)=1, W(2)=2, W(3)=3, W(4)=5 et W(5)=8.
9. QCM de révision — 20 questions
Une seule bonne réponse par question, note sur 20 et explications.