La programmation dynamique
==========================
<br><br>
*Ce document a été créé en collaboration avec moi-même. Il s'agit d'un résumé sous forme d'un diaporama du cours correspondant (accessible [ici](programmation-dynamique))*
---
# Introduction
----
## Introduction
On dispose de la grille $2 \times 3$ ci-dessous.
<img class="centre image-responsive" alt="une grille" src="data/prog_dyn_intro.png">
**Question** : Combien de chemins mènent du coin supérieur gauche au coin inférieur droit, en se déplaçant uniquement le long des traits horizontaux vers la droite et le long des traits verticaux vers le bas ?
----
## Introduction
**Idée** : pour arriver à un coin donné, soit on vient du coin juste à gauche, soit du coin juste au-dessus
<div class="r-stack">
<img class="" alt="une grille" src="data/prog_dyn_intro.png">
<img class="fragment" alt="une grille" src="data/prog_dyn_intro_1.png">
</div>
<p class="fragment"><strong>Réponse</strong> : 10 chemins pour une grille $2\times 3$</p>
<p class="fragment">Et pour une grille $10\times 10$ ? <span class="fragment">184756 chemins ...</span></p>
----
## Introduction
**Moralité**
- Il semble intéressant de calculer la réponse en fonction des résultats précédents : c'est le principe de la *programmation dynamique*
- On verra que c'est même primordial dès que le nombre de possibilités devient très grand
---
# Principe de la programmation dynamique
----
## Principe de la programmation dynamique
- **Programmation dynamique** : technique dûe à *Richard Bellman* dans les années 1950
<img class="r-stretch centre image-responsive" alt="Richard Bellman" src="data/Richard_Bellman.jpg">
<p><small>By <a rel="nofollow" class="external free" href="http://optlinealjur.blogspot.ru/2012/02/richard-bellman-ernest.html">http://optlinealjur.blogspot.ru/2012/02/richard-bellman-ernest.html</a>, <a href="//en.wikipedia.org/wiki/File:Richard_Ernest_Bellman.jpg" title="Fair use of copyrighted material in the context of Richard E. Bellman">Fair use</a>, <a href="https://en.wikipedia.org/w/index.php?curid=43193672">Link</a></small></p>
- Bellman est aussi connu pour l'algorithme de Bellman-Ford (= plus court chemin du protocole RIP)
----
## Principe de la programmation dynamique
- Méthode algorithmique développée initialement pour résoudre des problèmes d'optimisation (maximiser/minimiser)
- Idée générale : **déterminer un résultat sur la base de calculs précédents**
- Plus précisément :
- résoudre un problème en le décomposant en sous-problèmes
- résoudre les sous-problèmes du plus petit au plus grand
- **en stockant les résultats intérmédiaires**
---
# Illustration avec la suite de Fibonacci
----
## Rappels
- Suite de Fibonacci : chaque terme est la somme des deux précédents (les deux premiers sont 0 et 1)
- Cela donne : 0 - 1 - 1 - 2 - 3 - 5 - 8 - 13 - 21 - ...
- Mathématiquement : suite $(F_n)$ définie par
<div>
$$\begin{equation*}
\left\{
\begin{aligned}
F_0 & = 0 \\
F_1 & = 1 \\
F_n & = F_{n-1} + F_{n-2}, & \text{pour tout } n \geq 2.
\end{aligned}
\right.
\end{equation*}$$
</div>
----
### Version récursive naïve ...
- Déjà vue :
```python
def fibo(n):
"""Version récursive naïve"""
if n == 0 or n == 1: # ou n <= 1
return n
else:
return fibo(n-1) + fibo(n-2)
```
----
### ... mais inefficace
- Arbre d'appels pour `fibo(5)` :
```text
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
```
- Beaucoup d'appels redondants
----
### ... mais inefficace
- Le nombre d'appels récursifs explose rapidement dès que $n$ augmente un peu
```python
import time
def temps_fibo(n):
t0 = time.time()
resultat = fibo(n)
t1 = time.time()
print(f"{resultat} \nrésultat obtenu en {t1-t0} s.")
```
```python
>>> temps_fibo(5)
5
résultat obtenu en 0.0 s.
>>> temps_fibo(30)
832040
résultat obtenu en 0.0 s.
>>> temps_fibo(37)
24157817
résultat obtenu en 10.93546175956726 s.
```
----
### ... mais inefficace
- Pire : l'algo ne donne pas de réponse si $n$ est trop grand !
- **Peut-on faire mieux ?**
- Oui ! En évitant de refaire les calculs déjà effectués.
- Il faut **stocker les résultats intermédiaires**
----
### Version récursive avec *mémoïsation*
- Idée très simple (pour calculer $F_n$):
- on reprend l'algorithme récursif
- mais on commence par vérifier si on ne connaît pas déjà la réponse :
- si oui : on la renvoie directement
- si non : on la calcule récursivement et on stocke le résultat avant de le renvoyer
----
### Version récursive avec *mémoïsation*
- Utilisation d'un **tableau** `memo` pour stocker les valeurs $F_0$, $F_1$, $F_2$, ..., $F_n$
- Si $F_i$ n'est pas encore calculée, alors `memo[i]` vaut `None`
```python
def fibo_memo(n, memo): # version récursive avec mémoïsation
if memo[n] is not None: # si calcul déjà effectué
return memo[n] # on renvoie directement sa valeur
elif n == 0 or n == 1:
memo[n] = n
return n # ou memo[n]
else:
memo[n] = fibo_memo(n-1, memo) + fibo_memo(n-2, memo)
return memo[n]
```
```python
def fibo(n): # version récursive naïve
if n == 0 or n == 1: # ou n <= 1
return n
else:
return fibo(n-1) + fibo(n-2)
```
----
### Version récursive avec *mémoïsation*
- La fonction d'interface est alors :
```python
def fibo(n):
"""Version récursive avec mémoïsation.
Utilisation d'un tableau pour stocker les résultats."""
memo = [None] * (n+1) # initialisation du tableau
return fibo_memo(n, F)
```
----
### Version récursive avec *mémoïsation*
- On peut également utiliser un **dictionnaire** `memo` pour stocker les valeurs $F_0$, $F_1$, $F_2$, ..., $F_n$ (comme valeurs associées aux clés $0$, $1$, $2$, ..., $n$)
```python
def fibo_memo(n, memo):
if n in memo: # si calcul déjà effectué
return memo[n] # on renvoie directement sa valeur
elif n == 0 or n == 1:
memo[n] = n
return n # ou memo[n]
else:
memo[n] = fibo_memo(n-1, memo) + fibo_memo(n-2, memo)
return memo[n]
```
```python
def fibo(n):
"""Version récursive avec mémoïsation.
Utilisation d'un dictionnaire pour stocker les résultats."""
memo = {} # initialisation avec un dictionnaire vide
return fibo_memo(n, memo)
```
----
### Version récursive avec *mémoïsation*
- On peut aussi utiliser une fonction *englobante*
```python
def fibo(n):
memo = [None] * (n+1)
def fibo_memo(n):
if memo[n] is not None: # si calcul déjà effectué
return memo[n] # on renvoie directement sa valeur
elif n == 0 or n == 1:
memo[n] = n
return memo[n]
else:
memo[n] = fibo_memo(n-1) + fibo_memo(n-2)
return memo[n]
return fibo_memo(n)
```
- Permet d'éviter d'avoir à passer `memo` en paramètre à la fonction récursive
----
### Version récursive avec *mémoïsation*
- Efficacité : bien meilleure !
- Car plus aucun appel redondant. Exemple : `fibo(5)` se réduit à
```text
fib(5)
/ \
fib(4) fib(3)
/ \
fib(3) fib(2)
/ \
fib(2) fib(1)
/ \
fib(1) fib(0)
```
----
### Version récursive avec *mémoïsation*
- Les valeurs sont calculées quasiment instantanément
```python
>>> temps_fibo(5) # version récursive avec mémoïsation
5
résultat obtenu en 0.0 s.
```
```python
>>> temps_fibo(30)
832040
résultat obtenu en 0.0 s.
```
```python
>>> temps_fibo(37)
24157817
résultat obtenu en 0.0 s.
```
```python
>>> temps_fibo(850)
1949885951587339044875793733356219760673772926586260591210358470405525665390243100575540781157408285819450131557173898143210104351541330710230926558457389046268596497514105167175
résultat obtenu en 0.001992464065551758 s.
```
----
### Version itérative *ascendante*
- Autre manière de résoudre le problème :
- version **itérative** (non récursive)
- dite **ascendante** : on calcule les solutions des sous-problèmes *du plus petit au plus grand*
- On dit aussi méthode *bottom-up* ou *bas-haut*
- Le principe reste similaire : mémoïsation pour stocker les résultats intermédiaires
----
### Version itérative *ascendante*
On peut toujours appliquer les trois étapes suivantes :
- **Étape 1 : Créer et initialiser le tableau** : pour stocker les résultats
- **Étape 2 : Remplir le reste du tableau** : on utilise la formule de récurrence qui permet de calculer la valeur d'une case à partir de celles déjà calculées
- **Étape 3 : Renvoyer le résultat** qui est dans la **dernière case** remplie du tableau
----
### Version itérative *ascendante*
**Étape 1 : Créer et initialiser le tableau**
- on crée un tableau `F` de taille `n + 1` pour stocker les valeurs $F_0$, $F_1$, $F_2$, ..., $F_n$
- que l'on initialise avec `n + 1` zéros
```python
F = [0, 0, 0, 0, 0, 0, ..., 0]
```
- et on y stocke les valeurs déjà connues (à savoir $F_0$ et $F_1$)
```python
F = [0, 1, 0, 0, 0, 0, ..., 0]
```
----
### Version itérative *ascendante*
**Étape 2 : Remplir le reste du tableau**
- On utilise la relation de récurrence : $F_{i} = F_{i-1} + F_{i-2}$ pour $i \geq 2$
- Pour `i` allant de 2 à `n`, on obtient `F[i]` en faisant le calcul `F[i-1] + F[i-2]` (ces deux cases sont déjà remplies)
```python
F = [0, 1, 0, 0, 0, 0, ..., 0]
F = [0, 1, 1, 0, 0, 0, ..., 0]
F = [0, 1, 1, 2, 0, 0, ..., 0]
F = [0, 1, 1, 2, 3, 0, ..., 0]
...
F = [0, 1, 1, 2, 3, 5, ..., x] # arrêt lorsque case n remplie
```
----
### Version itérative *ascendante*
**Étape 3 : Renvoyer le résultat**
- La valeur de $F_n$ est dans la case `n` du tableau (`F[n]`)
- Il n'y a qu'à la renvoyer
**En Python**
```python
def fibo(n):
"""Version itérative ascendante"""
# Étape 1 : Créer et initialiser le tableau
F = [0] * (n+1)
F[0] = 0 # pas indispensable car déjà initialisé à 0
F[1] = 1
# Étape 2 : Remplir le reste du tableau
for i in range(2, n + 1):
F[i] = F[i-1] + F[i-2]
# Étape 3 : Renvoyer le résultat (dernière case)
return F[n]
```
----
### Version itérative *ascendante*
- Performances semblables à la version récursive avec mémoïsation
```python
>>> temps_fibo(850) # version itérative ascendante
1949885951587339044875793733356219760673772926586260591210358470405525665390243100575540781157408285819450131557173898143210104351541330710230926558457389046268596497514105167175
résultat obtenu en 0.0 s.
```
---
## Bilan des versions avec mémoïsation
- Dans les deux cas (récursive avec mémoïsation ou itérative ascendante) :
- Beaucoup plus efficaces en temps
- Plus coûteuses en mémoire car il faut stocker les résultats intermédiaires
- Programmation dynamique : utiliser plus de mémoire pour gagner en temps
---
# Autres problèmes
----
## Exemples
- Le calcul des termes de la suite de Fibonacci n'est pas un problème d'optimisation (il n'y a rien à maximiser/minimiser)
- De nombreux problèmes peuvent être résolus par programmation dynamique, dont beaucoup de problèmes d'optimisation :
- Problème du rendu de monnaie (traité en exercice)
- Problème du sac-à-dos (version gloutonne abordée en classe de Première)
- Alignement de séquences (traité en exercice)
- Problème du plus court chemin ([Algorithme de Bellman-Ford](https://fr.wikipedia.org/wiki/Algorithme_de_Bellman-Ford) utilisé par le protocole RIP)
- etc.
---
## ✍️ À faire
Faire les exercices
---
# Rendu de monnaie
<img class="centre image-responsive" width="250" src="data/money.png" alt="argent">
<p class="legende"><small>Crédits : Image par <a href="https://pixabay.com/fr/users/memed_nurrohmad-3307648/?utm_source=link-attribution&utm_medium=referral&utm_campaign=image&utm_content=1673582">Memed_Nurrohmad</a> de <a href="https://pixabay.com/fr//?utm_source=link-attribution&utm_medium=referral&utm_campaign=image&utm_content=1673582">Pixabay</a></small></p>
----
## Rendu de monnaie
- **Problème** : rendre la monnaie en utilisant le moins de pièces
- C'est un problème d'**optimisation** : on veut **minimiser** le nombre de pièces
- Déjà abordé en première avec une version **gloutonne**... mais qui ne donne pas toujours le meilleur résultat
- La programmation dynamique permet d'obtenir le résultat *optimal*
----
### Rendu de monnaie
- **Idée** : pour rendre la somme $s$ de manière optimale :
- il faut rendre une pièce $p$
- et la somme $s-p$ de manière optimale
- On peut alors tester *toutes* les pièces $p$ possibles et prendre *celle qui minimise* le rendu de $s-p$
- Cela donne la relation de récurrence (où $\text{nb}$ est le nombre optimal de pièces rendues) :
<div>
$$\begin{equation*}
\text{nb}(s) =
\left\{
\begin{array}{ll}
0 & \text{si } s = 0 \\
1 + \displaystyle\min_{p\leq s}(\text{nb}(s-p)) & \text{sinon}
\end{array}
\right.
\end{equation*}
$$
</div>
----
### Rendu de monnaie
<div>
$$\begin{equation*}
\text{nb}(s) =
\left\{
\begin{array}{ll}
0 & \text{si } s = 0 \\
1 + \displaystyle\min_{p\leq s}(\text{nb}(s-p)) & \text{sinon}
\end{array}
\right.
\end{equation*}
$$
</div>
- On vient de définir comment résoudre le problème du rendu à partir du rendu de sommes plus petites (sous-problèmes)
- C'est bien un problème d'optimisation : on recherche un minimum
- Finalement, on teste toutes les solutions pour trouver la meilleure : comme pour la *force brute*
----
### Rendu de monnaie
- La version récursive a une efficacité catastrophique :
```python
def rendu_recursif(pieces, somme):
if somme == 0:
return 0
else:
nb_pieces = somme # nb_pieces = 1 + 1 + ... + 1 dans le pire des cas
for p in pieces:
if p <= somme:
nb_pieces = min(nb_pieces, 1 + rendu_recursif(pieces, somme-p))
return nb_pieces
```
- L'appel `rendu_recursif([1, 2], 100)` ne termine pas...
----
### Rendu de monnaie (récursive mémoïsée)
- On peut faire beaucoup mieux en stockant les résultats intermédiaires dans un tableau `memo` de taille `somme + 1` initialisé à des valeurs `None`
- Dans la case `i` on stocke le nombre optimal de pièces pour rendre la somme `i`
```python
def rendu_recursif_memo(pieces, somme, memo):
if memo[somme] is not None: # si calcul déjà effectué
return memo[somme] # on le renvoie directement
elif somme == 0:
memo[somme] = 0
return 0
else:
nb_pieces = somme # nb_pieces = 1 + 1 + ... + 1 dans le pire des cas
for p in pieces:
if p <= somme: # inutile de tester les pièces de valeur > somme
nb_pieces = min(
nb_pieces,
1 + rendu_recursif_memo(pieces, somme - p, memo)
)
memo[somme] = nb_pieces
return nb_pieces
```
----
### Rendu de monnaie (récursive mémoïsée)
- La version récursive avec mémoïsation est très efficace :
```python
def rendu_recursif_memoise(pieces, somme):
"""Version récursive avec mémoïsation"""
memo = [None] * (somme + 1) # intialisation du tableau avec des None
return rendu_recursif_memo(pieces, somme, memo)
```
```python
>>> rendu_recursif_memoise([1, 2], 100)
50
```
----
### Rendu de monnaie (itérative ascendante)
**Version itérative ascendante**
- On procède en trois étapes (classique)
- On peut utiliser un tableau `nb` pour stocker les résultats
```python
def rendu_iteratif_ascendant(pieces, somme):
"""Version itérative ascendante"""
# ÉTAPE 1 : création et initialisation du tableau
nb = [0] * (somme+1) # nb[0] est ainsi bien initialisé
# ÉTAPE 2 : remplissage du reste du tableau par indice croissant
for s in range(1, somme + 1):
nb[s] = s # nb[n] = 1 + 1 + ... + 1 dans le pire des cas
for p in pieces:
if p <= s:
nb[s] = min(nb[s], 1 + nb[s-p]) # même formule de récurrence
# ÉTAPE 3 : le résultat est dans la dernière case
return nb[s]
```
```python
>>> rendu_iteratif_ascendant([1, 2], 100) # très efficace
50
```
---
# Alignement de séquences
<img class="r-stretch" src="data/Multalign.svg" alt="alignement de séquences d'ADN">
<p><small>Crédits : <a href="https://commons.wikimedia.org/wiki/File:Multalign.svg">Fdardel</a>, <a href="https://creativecommons.org/licenses/by-sa/3.0">CC BY-SA 3.0</a>, via Wikimedia Commons</small></p>
----
## Alignement de séquences
- **Problème** : comment *aligner* deux chaînes de caractères de manière optimale ? (= pour faire correspondre le plus de caractères)
- Très utilisé en bio-informatique pour trouver des concordances dans des brins d'ADN (longueur des chaînes très grandes : il faut un algo efficace)
- **Comment faire ?** Définir la *distance* entre deux chaînes et *minimiser* cette distance (problème d'optimisation)
----
## Alignement de séquences
- Distance entre deux chaînes, notée $d(T_1, T_2)$ = nombre d'opérations pour passer de $T_1$ à $T_2$ au moyen :
- d'insertion (d'un caractère dans $T_1$)
- de suppression (d'un caractère dans $T_1$)
- de substitution (d'un caractère de $T_1$ par un autre caractère)
- **Distance d'édition**, notée $\text{dE}(T_1, T_2)$ = nombre *minimal* d'opérations pour passer de $T_1$ à $T_2$.
- On cherche donc à minimiser le coût pour passer de $T_1$ à $T_2$
----
## Alignement de séquences
- **Exemple** : alignement optimal des chaînes `SUCCES` et `ECHECS` :
```
S U C C E - S
- E C H E C S
```
- Le coût vaut 4
- suppression de S : <span><strong>-</strong></span>UCCES (coût = 1)
- substitution de U par E : <span><strong>E</strong></span>CCES (coût = 1)
- correspondance de C : E<span><strong>C</strong></span>CES
- substitution de C par H : EC<span><strong>H</strong></span>ES (coût = 1)
- correspondance de E : ECH<span><strong>E</strong></span>S
- insertion de C : ECHE<span><strong>C</strong></span>S (coût = 1)
- correspondance de S : ECHEC<span><strong>S</strong></span>
----
## Alignement de séquences
- On peut calculer la distance entre deux chaînes à partir de celles de chaînes plus petites
- Supposons avoir aligné $T_1[1..i]$ et $T_2[1..j]$ et regardons l'alignement le plus à droite. Il y a 3 possibilités (4 en fait) :
- $T_1[i]$ s'aligne sur « - ». Cela demande à avoir aligné $T_1[1..i-1]$ et $T_2[1..j]$ et **supprimé** $T_1[i]$.
- « - » s'aligne sur $T_2[j]$. Cela demande à avoir aligné $T_1[1..i]$ et $T_2[1..j-1]$ et **inséré** $T_2[j]$.
- $T_1[i]$ s'aligne sur $T_2[j]$ :
- si $T_1[i] \neq T_2[j]$, cela demande à avoir aligné $T_1[1..i-1]$ et $T_2[1..j-1]$ et **substitué** $T_1[i]$ par $T_2[j]$.
- si $T_1[i] = T_2[j]$, cela demande à avoir aligné $T_1[1..i-1]$ et $T_2[1..j-1]$ et c'est tout (sans surcoût : **correspondance**)
<!-- - $T_1[i]$ s'aligne sur « - » : cela demande à avoir aligné $T_1[1..i-1]$ et $T_2[1..j]$ et **supprimé** $T_1[i]$
- « - » est aligné avec $T_2[j]$ : donc $T_1[1..i]$ et $T_2[1..j-1]$ sont alignés et on a **inséré** $T_2[j]$
- $T_1[i]$ est aligné avec $T_2[j]$ mais $T_1[i] \neq T_2[j]$ : donc $T_1[1..i-1]$ et $T_2[1..j-1]$ sont alignés et on a **substitué** $T_1[i]$ par $T_2[j]$
- $T_1[i]$ est aligné avec $T_2[j]$ et $T_1[i] = T_2[j]$ : donc $T_1[1..i-1]$ et $T_2[1..j-1]$ sont alignés et $T_1[i]$ et $T_2[j]$ **correspondent** (substitution du caractère par lui-même) -->
----
## Alignement de séquences
- Il y a donc 3 possiblités pour le coût.
- La distance d'édition est calculée en prenant le minimum des 3 coûts engendrés
- On aboutit à la relation de récurrence suivante :
<div>
$$\text{dE}(T_1[1..i], T_2[1..j]) = \min \left\{
\begin{array}{l}
\text{dE}(T_1[1..i-1], T_2[1..j]) + 1 \quad \text{(suppression)} \\
\text{dE}(T_1[1..i], T_2[1..j-1]) + 1 \quad \text{(insertion)} \\
\text{dE}(T_1[1..i-1], T_2[1..j-1]) + \text{sub}(T_1[i], T_2[j])
\end{array}
\right.$$
</div>
<div>
où $\text{sub}(a, b) = \left\{
\begin{array}{l}
1 \text{ si } a \neq b \quad \text{(substitution)}\\
0 \text{ si } a = b \quad \text{(correspondance)}
\end{array}
\right.
$
</div>
----
### Version itérative ascendante
- On note $n_1$ la taille de $T_1$ et $n_2$ la taille de $T_2$
- On va utiliser un tableau `d` pour stocker les résultats :
- `d` est de taille $(n_1 + 1)\times(n_2 + 1)$
- `d[i][j]` $= \text{dE}(T_1[1..i], T_2[1..j])$
- le résultat sera dans la dernière case
<img class="centre image-responsive" alt="tableau pour l'alignement de séquence" src="data/tableau_align_seq.png">
----
### Version itérative ascendante
- On utilise les trois étapes classiques
- **Étape 1 : Création et initialisation du tableau**
- Tableau `d` de taille $(n_1 + 1)\times(n_2 + 1)$ constitué de zéros
- 1ères ligne et colonne : alignement avec le mot vide ($\varepsilon$)
<img class="centre image-responsive" alt="tableau pour l'alignement de séquence" src="data/tableau_align_seq1.png">
----
### Version itérative ascendante
- **Étape 2 : Remplissage du reste du tableau**
- Ligne par ligne
- À l'aide de la formule de récurrence vue précédemment
<div>
$$\text{d[i][j]} = \min \left\{
\begin{array}{l}
\text{d[i-1][j]} + 1 \text{ (suppression)}\\
\text{d[i][j-1]} + 1 \text{ (insertion)}\\
\text{d[i-1][j-1]} + \left\{
\begin{array}{l}
0 \text{ si } T_1[i] = T_2[j] \text{ (correspondance)}\\
1 \text{ si } T_1[i] \neq T_2[j] \text{ (substitution)}
\end{array}
\right.
\end{array}
\right.$$
</div>
<img class="r-stretch centre image-responsive" alt="tableau pour l'alignement de séquence" src="data/tableau_align_seq4.png">
----
### Version itérative ascendante
- **Étape 3 : Le résultat est dans la dernière case**
- On la renvoie ! (ici 4)
<img class="centre image-responsive" alt="tableau pour l'alignement de séquence" src="data/tableau_align_seq4.png">
----
### Version itérative ascendante
**En Python**
<pre class="stretch language-python"><code>def dE(t1, t2):
"""Version itérative ascendante"""
# ÉTAPE 1 : création et initialisation du tableau
n1 = len(t1)
n2 = len(t2)
d = [[0] * (n2 + 1) for i in range(n1 + 1)]
for i in range(n1 + 1): # remplissage première colonne
d[i][0] = i
for j in range(n2 + 1): # remplissage première ligne
d[0][j] = j
# ÉTAPE 2 : remplissage du reste du tableau par indice croissant
for i in range(1, n1 + 1):
for j in range(1, n2 + 1):
if t1[i-1] == t2[j-1]: # le k-ième caractère est en position k-1
cout_sub = 0 # correspondance
else:
cout_sub = 1 # substitution
d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + cout_sub)
# ÉTAPE 3 : le résultat est dans la dernière case
return d[n1][n2], d # on renvoie aussi le tableau d pour l'observer</code></pre>
----
### Version itérative ascendante
- C'est efficace (même sur des chaînes plus longues)
```python
>>> dE('SUCCES', 'ECHECS')
(4,
[[0, 1, 2, 3, 4, 5, 6],
[1, 1, 2, 3, 4, 5, 5],
[2, 2, 2, 3, 4, 5, 6],
[3, 3, 2, 3, 4, 4, 5],
[4, 4, 3, 3, 4, 4, 5],
[5, 4, 4, 4, 3, 4, 5],
[6, 5, 5, 5, 4, 4, 4]])
```
```python
>>> dE('ALGORITHME', 'ALGORIHTME')
(2,
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
[1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
[2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8],
[3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7],
[4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6],
[5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5],
[6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4],
[7, 6, 5, 4, 3, 2, 1, 1, 1, 2, 3],
[8, 7, 6, 5, 4, 3, 2, 1, 2, 2, 3],
[9, 8, 7, 6, 5, 4, 3, 2, 2, 2, 3],
[10, 9, 8, 7, 6, 5, 4, 3, 3, 3, 2]])
```
----
### Version itérative ascendante
- Pour trouver un **alignement optimal**
- on peut remonter depuis `d[n1][n2]` vers `d[0][0]`
- en choisissant le "meilleur" des 3 voisins, celui par lequel on a pu arriver (il y a parfois plusieurs choix)
- cela permet de savoir si on fait une suppression, une insertion ou une substitution
<img class="centre image-responsive" alt="alignement optimal" src="data/tableau_align_seq3.png">
----
### Version itérative ascendante
<img class="centre image-responsive" alt="alignement optimal" src="data/tableau_align_seq3.png">
- On peut construire un alignement optimal à partir de ce chemin (en partant du début ou de la fin) :
```
S U C C E - S
- E C H E C S
```
---
# Bilan
----
## Bilan
- **Programmation dynamique** = technique pour améliorer l'efficacité d'un algorithme en *évitant les calculs redondants*
- Pour cela on **stocke les résultats intermédiaires** (évite de les recalculer) : on parle de **mémoïsation**
- Cela améliore le coût en temps mais augmente celui en mémoire
- Permet de résoudre un problème à partir des solutions de sous-problèmes (comme *diviser pour régner*)
----
## Bilan
- Souvent utilisée pour résoudre des problèmes d'*optimisation*
- On peut procéder :
- de manière *récursive* en veillant à utiliser les résultats déjà calculés plutôt que de les calculer à nouveau (approche *descendante*)
- de manière *itérative* : du plus petit problème au plus grand (approche *ascendante*)
- Dans les deux cas, on s'appuie sur une formule de récurrence qui permet de calculer le résultat d'un problème à partir des résultats des problèmes plus petits
---
### Références
- Cours sur la [Recherche textuelle](data/diu2019_bloc5_séance4.pdf) de l'équipe pédagogique du DIU EIL de l'Université de Nantes.
- Articles Wikipédia sur la [Programmation dynamique](https://fr.wikipedia.org/wiki/Programmation_dynamique) et sur la [Distance de Levensthein](https://fr.wikipedia.org/wiki/Distance_de_Levenshtein)
- Livre *Spécialité Numérique et sciences informatiques : 24 leçons avec exercices corrigés - Terminale*, éditions Ellipses, T. Balabonski, S. Conchon, J.-C. Filliâtre, K. Nguyen. Site du livre : [http://www.nsi-terminale.fr/](http://www.nsi-terminale.fr/)
- Cours de David Roche sur le Pixees : [Programmation dynamique](https://pixees.fr/informatiquelycee/n_site/nsi_term_algo_progdyn.html)
- Un cours sur la programmation dynamique : [http://www-desir.lip6.fr/~spanjaard/pmwiki/uploads/ProgrammationDynamique.pdf](http://www-desir.lip6.fr/~spanjaard/pmwiki/uploads/ProgrammationDynamique.pdf)
---
Germain BECKER, Lycée Mounier, ANGERS
Ressource éducative libre distribuée sous [Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International](http://creativecommons.org/licenses/by-sa/4.0/)
