La mémoire, ligne par ligne

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 18 — La programmation dynamique

Énoncé

(a) Optimiser le calcul de Fibonacci pour n'utiliser qu'un espace mémoire en $O (1)$ . (b) Modifier l'implémentation de la distance de Levenshtein pour qu'elle s'exécute en n'utilisant que deux lignes de tableau, amenant l'espace mémoire à $O (min (n, m))$ . (c) Expliquer ce que cette optimisation de l'espace mémoire sacrifie et comment y remédier si nécessaire.

Corrigé

(a)

def fib_optimal(n: int) -> int:
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

(b)

def levenshtein_2lignes(u: str, v: str) -> int:
    if len(v) > len(u):
        u, v = v, u  # Assure que v est la chaîne la plus courte
    prec = list(range(len(v) + 1))
    for i in range(1, len(u) + 1):
        cour = [i] + [0] * len(v)
        for j in range(1, len(v) + 1):
            cout = 0 if u[i - 1] == v[j - 1] else 1
            cour[j] = min(prec[j] + 1,          # suppression
                          cour[j - 1] + 1,      # insertion
                          prec[j - 1] + cout)   # substitution
        prec = cour
    return prec[len(v)]

(c) Cette réduction d'espace mémoire sacrifie la possibilité de reconstruire la solution optimale (la suite des opérations d'édition). On ne conserve que la valeur finale de la distance. Si l'on souhaite à la fois économiser la mémoire et reconstruire la solution, il faut utiliser des approches de type "diviser pour régner" (comme l'algorithme de Hirschberg, hors programme) qui reconstruisent la solution en mémoire linéaire au prix d'un doublement du temps de calcul.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.