Laboratoire visuel : programmation dynamique
Chaque case intérieure de la table dépend de trois voisines : nord-ouest, nord et ouest. Déroulez le remplissage du code du cours, ou choisissez vous-même l’ordre des cases : une case n’est acceptée que si ses trois voisines sont déjà calculées.
Laboratoire visuel : programmation dynamique
Les bords sont donnés. Choisissez une case vide : elle n’est acceptée que si ses voisines nord-ouest, nord et ouest sont calculées. Choisissez une case remplie pour revoir son calcul.
Table vide
Alignement
Lire la table en texte
Compteurs
Journal
À explorer
- Partez de la case en bas à droite et lisez un alignement dans la table. Quelle dernière colonne ajoute chaque pas ? Pourquoi l’alignement se construit-il de droite à gauche ?
- Pour
grapheetgirafe, quelle règle d’égalité donne l’alignement du CM 9 ? Cherchez celui qui insèrei, remplacepparf, puis supprimeh. - Question de sortie du CM 9. Quelle est la distance entre
amietmai? Retrouvez les trois alignements optimaux à l’aide du sélecteur « En cas d’égalité ». - Sur
ttatatgcgtettatcccctta, essayez les deux règles d’égalité de la PLSC. Pourquoitatttettatctsont-ils tous les deux des PLSC ? - Interdisez les substitutions pour
grapheetgirafe. Quel est le lien entre les lettres conservées, le coût de l’alignement et la longueur de la PLSC ?
Les algorithmes suivis
Les cases intérieures sont calculées par lignes, par colonnes croissantes, comme dans le code du cours ; les deux autres ordres sont des variantes qui respectent les mêmes dépendances. Pour la suite double, les bords valent 1 et f est choisie parmi trois fonctions.
Suite double
def suite_double(n, m, f, bord_gauche, bord_haut):
T = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
T[i][0] = bord_gauche(i)
for j in range(1, m + 1):
T[0][j] = bord_haut(j)
for i in range(1, n + 1):
for j in range(1, m + 1):
T[i][j] = f(T[i - 1][j - 1], T[i - 1][j], T[i][j - 1])
return T
Le compteur d’appels suit la version récursive directe :
def suite_double_recursif(i, j, f, bord_gauche, bord_haut):
if i == 0:
return bord_haut(j)
if j == 0:
return bord_gauche(i)
return f(suite_double_recursif(i - 1, j - 1, f, bord_gauche, bord_haut),
suite_double_recursif(i - 1, j, f, bord_gauche, bord_haut),
suite_double_recursif(i, j - 1, f, bord_gauche, bord_haut))
Plus longue sous-suite commune
def plsc_table(u, v):
n, m = len(u), len(v)
A = [[0] * (m + 1) for _ in range(n + 1)]
provenance = [[None] * (m + 1) for _ in range(n + 1)]
for i in range(n):
for j in range(m):
if u[i] == v[j]:
A[i + 1][j + 1] = A[i][j] + 1
provenance[i + 1][j + 1] = "diag"
elif A[i][j + 1] >= A[i + 1][j]:
A[i + 1][j + 1] = A[i][j + 1]
provenance[i + 1][j + 1] = "haut"
else:
A[i + 1][j + 1] = A[i + 1][j]
provenance[i + 1][j + 1] = "gauche"
return A, provenance
from plsc_table import plsc_table
def plsc(u, v):
_, provenance = plsc_table(u, v)
i, j = len(u), len(v)
lettres = []
while i > 0 and j > 0:
if provenance[i][j] == "diag":
lettres.append(u[i - 1])
i, j = i - 1, j - 1
elif provenance[i][j] == "haut":
i = i - 1
else:
j = j - 1
lettres.reverse()
return "".join(lettres)
Distance d’édition
Un alignement écrit u au-dessus de v, avec des trous. Son coût est le nombre de colonnes où les deux symboles diffèrent. La distance d’édition est le plus petit de ces coûts.
Dans la case (I, J), on examine la dernière colonne d’un alignement des préfixes u[:I] et v[:J].
| Dernière colonne | Préfixes plus courts | Coût ajouté |
|---|---|---|
u[I-1] / v[J-1] |
D[I-1][J-1] |
0 si les lettres coïncident, 1 pour une substitution |
u[I-1] / – |
D[I-1][J] |
1 pour une suppression |
– / v[J-1] |
D[I][J-1] |
1 pour une insertion |
distance_edition.py renvoie seulement D[n][m]. Pour reconstruire un alignement, le laboratoire déduit chaque flèche des valeurs de la table, comme dans l’exercice du polycopié sur la PLSC sans table de provenance. En remontant jusqu’à (0, 0), il ajoute à gauche la dernière colonne de chaque paire de préfixes. Quand les lettres coïncident, il suit la diagonale.
Sans substitutions, chaque colonne à deux lettres conserve une lettre commune. Avec k lettres conservées, il reste n + m − 2·k insertions et suppressions. Minimiser ce coût revient à choisir une plus longue sous-suite commune, de longueur A[n][m].
def distance_edition(u, v):
n, m = len(u), len(v)
D = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
D[i][0] = i
for j in range(m + 1):
D[0][j] = j
for i in range(n):
for j in range(m):
if u[i] == v[j]:
D[i + 1][j + 1] = D[i][j]
else:
D[i + 1][j + 1] = 1 + min(D[i][j], D[i][j + 1], D[i + 1][j])
return D[n][m]