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 :
Correction publiée après la séance.
Question 2. La version récursive naïve de Fibonacci a une complexité temporelle :
Correction publiée après la séance.
Question 3. La mémoïsation (approche top-down) consiste à :
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$ :
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 :
Correction publiée après la séance.
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$).
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é ?
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 ?
Chronométrer avec perf_counter() du module time, juste avant et juste après l’appel.
Partie B. Mémoïsation (top-down)
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 ________
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.
fibo_memo(100). Comparer le temps d’exécution avec la version naïve.Partie C. Approche ascendante (bottom-up)
def fibo_dyn(n):
if n == 0:
return 0
t = [0] * (n + 1)
t[1] = ________
for i in range(________, ________):
t[i] = ________ + ________
return t[n]
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é ?
Combien de cases du tableau servent à calculer la suivante ? Deux variables pourraient-elles suffire ?
Correction publiée après la séance.
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.
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.
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 ?
Chercher à la main une façon de rendre 6 avec moins de pièces.
Partie B. Programmation dynamique
| monnaie \ somme | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| {} (aucune) | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| {1} | |||||||
| {1, 3} | |||||||
| {1, 3, 4} |
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 ?
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.
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.
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]).
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.
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 ?
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).
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.
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).
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.
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.
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.
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.
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.
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.
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.
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)$.
É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 ?
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 ?
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).
Reprendre fibo_memo : un dictionnaire garde les valeurs déjà calculées.
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).
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$.
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.
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.