Exercices : programmation dynamique

Exercice 1. QCM d’activation

Pour chaque question, une seule réponse est correcte.

Question 1. La programmation dynamique est particulièrement adaptée aux problèmes qui présentent :

A) des sous-problèmes indépendants (comme dans « diviser pour régner »)
B) des sous-problèmes chevauchants (un même sous-problème apparaît plusieurs fois)
C) une seule solution possible
D) une complexité toujours linéaire

Correction publiée après la séance.

Question 2. La version récursive naïve de Fibonacci a une complexité temporelle :

A) $O(n)$
B) $O(n^2)$
C) $O(2^n)$
D) $O(n \log n)$

Correction publiée après la séance.

Question 3. La mémoïsation (approche top-down) consiste à :

A) remplir un tableau du plus petit sous-problème au plus grand
B) stocker les résultats des appels récursifs déjà calculés pour éviter les recalculs
C) utiliser un algorithme glouton avec un cache
D) résoudre le problème sans récursivité

Correction publiée après la séance.

Question 4. Dans le problème du sac à dos par programmation dynamique, le tableau contient en ligne $i$ et colonne $p$ :

A) le poids maximal qu’on peut porter avec $i$ objets
B) le nombre d’objets de poids $p$
C) la valeur maximale atteignable avec les $i$ premiers objets et un poids maximal de $p$
D) le nombre de façons de remplir le sac avec $i$ objets

Correction publiée après la séance.

Question 5. Pour le système de monnaie $(1, 3, 4)$ et la somme $s = 6$, l’algorithme glouton donne :

A) deux pièces de 3 (solution optimale)
B) une pièce de 4, puis une de 1, puis une de 1 (trois pièces)
C) une pièce de 3, puis une de 3 (solution optimale)
D) six pièces de 1

Correction publiée après la séance.

Exercice 2. Fibonacci : comparer les approches (guidé)

Cet exercice compare les trois approches vues en cours pour calculer les termes de la suite de Fibonacci.

Partie A. Approche récursive naïve

Écrire la fonction récursive fibo(n) (cas de base : $F_0 = 0$, $F_1 = 1$).
Indice
Si n vaut 0 ou 1, renvoyer n ; sinon, renvoyer la somme des deux termes précédents, calculés par deux appels récursifs.
Dessiner l’arbre des appels pour fibo(5). Combien de fois fibo(2) est-il calculé ?
Indice
Chaque appel fibo(k) avec k ≥ 2 a deux fils, fibo(k - 1) et fibo(k - 2). Dessiner l’arbre niveau par niveau, puis compter les nœuds fibo(2).
Tester fibo(35). Combien de temps cela prend-il approximativement ?
Indice
Chronométrer avec perf_counter() du module time, juste avant et juste après l’appel.

Partie B. Mémoïsation (top-down)

Compléter la fonction suivante qui utilise un dictionnaire pour stocker les résultats :

def fibo_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in ________:
        return ________
    if n == 0 or n == 1:
        return n
    memo[n] = fibo_memo(________, memo) + fibo_memo(________, memo)
    return ________

Indice

Le dictionnaire memo garde les valeurs déjà calculées : si n y figure, renvoyer memo[n] sans rien recalculer. Sinon, calculer la valeur à partir de n - 1 et n - 2, la ranger dans memo[n], puis la renvoyer.

Tester avec fibo_memo(100). Comparer le temps d’exécution avec la version naïve.

Partie C. Approche ascendante (bottom-up)

Compléter la fonction suivante qui remplit un tableau de gauche à droite :

def fibo_dyn(n):
    if n == 0:
        return 0
    t = [0] * (n + 1)
    t[1] = ________
    for i in range(________, ________):
        t[i] = ________ + ________
    return t[n]

Indice

t[i] contiendra le terme d’indice i : t[0] vaut déjà 0, il reste à fixer t[1]. La boucle remplit ensuite les cases de 2 à n, chacune à partir des deux précédentes.

Quelle est la complexité en temps et en espace de cette fonction ? Peut-on réduire l’espace mémoire utilisé ?
Indice
Combien de cases du tableau servent à calculer la suivante ? Deux variables pourraient-elles suffire ?

Correction publiée après la séance.

Exercice 3. Rendu de monnaie (guidé)

On dispose du système de monnaie monnaie = [1, 3, 4] et on souhaite rendre la somme $s = 6$ avec le minimum de pièces.

Partie A. Algorithme glouton

Programmer la fonction rendu_glouton(monnaie, s) qui applique l’algorithme glouton : on rend toujours la plus grande pièce possible.
Indice
Parcourir les pièces de la plus grande à la plus petite, avec reversed(monnaie), et rendre chacune tant qu’elle ne dépasse pas la somme restante.
Code à copier puis compléter
```
def rendu_glouton(monnaie, s):
    resultat = []
    for piece in reversed(monnaie):
        while s >= ...:
            resultat.append(piece)
            s = ...
    return resultat
```
Tester avec rendu_glouton([1, 3, 4], 6). La solution est-elle optimale ?
Indice
Chercher à la main une façon de rendre 6 avec moins de pièces.

Partie B. Programmation dynamique

Remplir à la main le tableau suivant, où chaque case contient le nombre minimal de pièces pour atteindre la somme en colonne avec les pièces disponibles en ligne :

monnaie \ somme	0	1	2	3	4	5	6
{} (aucune)	0	∞	∞	∞	∞	∞	∞
{1}
{1, 3}
{1, 3, 4}

Indice

Avec des pièces de 1 seulement, il faut j pièces pour la somme j. Sur les lignes suivantes, chaque case est le minimum de deux nombres : la case du dessus (sans utiliser la nouvelle pièce), et 1 plus la case située v colonnes plus à gauche sur la même ligne (en utilisant une pièce de valeur v).

Quelle est la relation de récurrence permettant de remplir la case $(i, j)$ du tableau ?
Indice
Traduire la méthode utilisée pour remplir le tableau : la case $(i, j)$ est le minimum de deux possibilités, ne pas utiliser la pièce $v_i$, ou en utiliser au moins une.

Programmer la fonction rendu_dynamique(monnaie, s) qui retourne le nombre minimal de pièces pour rendre la somme s.

Indice

Construire un tableau t de len(monnaie) + 1 lignes et s + 1 colonnes rempli de float("inf"), avec 0 dans la colonne de la somme 0, puis le remplir ligne par ligne avec la relation de la question 4.

Code à copier puis compléter

def rendu_dynamique(monnaie, s):
    n = len(monnaie)
    t = []
    for i in range(n + 1):
        t.append([float("inf")] * (s + 1))
        t[i][0] = 0
    for i in range(1, n + 1):
        v = monnaie[i - 1]
        for j in range(1, s + 1):
            t[i][j] = t[i - 1][j]
            if j >= v and t[i][j - v] + 1 < t[i][j]:
                t[i][j] = ...
    return t[...][...]

Modifier la fonction pour qu’elle retourne également la décomposition en pièces (par exemple [3, 3] pour rendre 6 avec le système [1, 3, 4]).
Indice
Remonter le tableau depuis la case t[n][s] : si sa valeur vient de la case du dessus, la pièce de la ligne n’est pas utilisée et l’on monte d’une ligne ; sinon, on ajoute cette pièce à la décomposition et l’on recule de sa valeur sur la même ligne.

Correction publiée après la séance.

Exercice 4. Sac à dos

On dispose des objets suivants et d’un sac pouvant porter au maximum $w = 7$ kg :

Objet	Valeur	Poids
A	5	3
B	8	4
C	4	2
D	6	1

Appliquer l’algorithme glouton « meilleur rapport valeur/poids » et donner la solution obtenue. Est-elle optimale ?
Indice
Calculer le rapport valeur/poids de chaque objet, puis prendre les objets dans l’ordre décroissant de ce rapport tant qu’ils tiennent dans les 7 kg. Comparer ensuite avec d’autres choix d’objets.
Construire le tableau de programmation dynamique de taille $5 \times 8$ (quatre objets + ligne 0, poids de 0 à 7).
Indice
La case (i, p) donne la meilleure valeur avec les i premiers objets et un poids maximal p. Elle vaut la plus grande de deux valeurs : la case du dessus (objet i non pris) et, si l’objet tient, sa valeur plus la case de la ligne du dessus située poids colonnes plus à gauche.
En déduire la valeur maximale et les objets sélectionnés en remontant dans le tableau.
Indice
La valeur maximale est dans la dernière case. En remontant ligne par ligne : si la valeur diffère de celle de la ligne du dessus, l’objet de la ligne est pris, et l’on retire son poids au numéro de colonne.

Programmer la fonction sac_a_dos(objets, w) où objets est une liste de tuples (valeur, poids).

Indice

Traduire la construction du tableau de la question 2 par deux boucles imbriquées, sur les objets puis sur les poids de 0 à w, puis la remontée de la question 3.

Code à copier puis compléter

def sac_a_dos(objets, w):
    n = len(objets)
    t = []
    for i in range(n + 1):
        t.append([0] * (w + 1))
    for i in range(1, n + 1):
        valeur, poids = objets[i - 1]
        for p in range(w + 1):
            t[i][p] = t[i - 1][p]
            if p >= poids and t[i - 1][p - poids] + valeur > t[i][p]:
                t[i][p] = ...
    selection = []
    p = w
    for i in range(n, 0, -1):
        if t[i][p] != t[i - 1][p]:
            selection.append(i - 1)
            p = p - ...
    return t[n][w], selection

Correction publiée après la séance.

Exercice 5. Distance d’édition

La distance d’édition (ou distance de Levenshtein) entre deux chaînes est le nombre minimal d’opérations (insertion, suppression, substitution) pour transformer l’une en l’autre. Ce problème est fondamental en bio-informatique pour comparer des séquences ADN.

Construire à la main le tableau de programmation dynamique pour transformer "BAIN" en "BRIN".
Rappel : la case $(i, j)$ contient la distance d’édition entre les $i$ premiers caractères de la première chaîne et les $j$ premiers de la seconde.
Indice
La première ligne et la première colonne valent 0, 1, 2, … : on insère ou on supprime tous les caractères. Chaque autre case est le minimum de trois valeurs : la case du dessus plus 1 (suppression), la case de gauche plus 1 (insertion), la case en diagonale plus 0 si les deux caractères sont égaux, plus 1 sinon (substitution).
En déduire la distance d’édition et les opérations effectuées.
Indice
La distance est dans la dernière case. Pour les opérations, remonter depuis cette case en suivant chaque fois la case qui a donné le minimum.

Programmer la fonction distance_edition(a, b) qui retourne la distance d’édition entre deux chaînes a et b.

Indice

Traduire la construction du tableau : remplir la première ligne et la première colonne, puis chaque autre case avec le minimum des trois possibilités.

Code à copier puis compléter

def distance_edition(a, b):
    n, m = len(a), len(b)
    t = []
    for i in range(n + 1):
        t.append([0] * (m + 1))
    for i in range(n + 1):
        t[i][0] = i
    for j in range(m + 1):
        t[0][j] = ...
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                cout = 0
            else:
                cout = 1
            t[i][j] = min(t[i - 1][j] + 1, t[i][j - 1] + 1, ...)
    return t[n][m]

Tester avec les paires suivantes : ("CHAT", "CHATS"), ("NICHE", "CHIEN"), ("ALGORITHME", "ALTRUISME").

Correction publiée après la séance.

Exercice 6. Montée d’escalier (synthèse)

Un escalier comporte $n$ marches numérotées de 1 à $n$. Un marcheur part du sol (marche 0) et peut monter d’une ou deux marches à chaque pas. On note $f(n)$ le nombre de façons d’atteindre la marche $n$.

Calculer à la main $f(1)$, $f(2)$, $f(3)$, $f(4)$ et $f(5)$.
Indice
Écrire toutes les suites de pas de 1 et de 2 dont la somme vaut n : pour n = 3, il y a 1 + 1 + 1, 1 + 2 et 2 + 1.
Justifier que $f(n) = f(n-1) + f(n-2)$ pour $n \geq 3$, avec $f(1) = 1$ et $f(2) = 2$. Quelle suite connue reconnaît-on ?
Indice
Le dernier pas vers la marche n part soit de la marche n − 1, soit de la marche n − 2.
Écrire une version récursive naïve montee_recursive(n), puis la tester pour $n = 40$. Que constate-t-on ?
Indice
Même structure que fibo à l’exercice 2, avec les cas de base f(1) = 1 et f(2) = 2.

Écrire une version avec mémoïsation montee_memo(n).

Indice

Reprendre fibo_memo : un dictionnaire garde les valeurs déjà calculées.

Code à copier puis compléter

def montee_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 2:
        return n
    memo[n] = montee_memo(..., memo) + montee_memo(..., memo)
    return memo[n]

Écrire une version bottom-up montee_dyn(n).
Indice
Reprendre fibo_dyn : un tableau t de taille n + 1, avec t[1] = 1 et t[2] = 2, rempli de gauche à droite.
Extension : chaque marche a maintenant un coût $c_i$ (l’énergie dépensée pour y poser le pied). On cherche à atteindre la marche $n$ en minimisant le coût total. On note $C(i)$ le coût minimal pour atteindre la marche $i$. Donner la relation de récurrence, puis programmer la fonction cout_minimal(couts) où couts est la liste des coûts des marches de 1 à $n$.
Indice
Pour atteindre la marche i, on vient de la marche i − 1 ou de la marche i − 2 : laquelle choisir pour que le coût soit le plus petit ? Remplir ensuite un tableau de gauche à droite, comme pour montee_dyn.
Code à copier puis compléter
```
def cout_minimal(couts):
    n = len(couts)
    if n == 1:
        return couts[0]
    t = [0] * n
    t[0] = couts[0]
    t[1] = couts[1]
    for i in range(2, n):
        t[i] = couts[i] + min(..., ...)
    return t[n - 1]
```

Correction publiée après la séance.