Numérique et sciences informatiques (NSI) · Terminale

Exercices : la programmation dynamique

22 exercices avec correction détaillée, en 3 séries. Aucune inscription : ta progression reste sur ton appareil.

ULUMINE · Numérique et sciences informatiques (NSI) · Terminale

La programmation dynamique — S’entraîner

Feuille d’exercices

Prénom : ……………………………Date : ……………………Score : ……… / 8

Quand un tableau est en jeu, remplis-le case par case sur ton brouillon.

Exercice 1 — Coche la bonne réponse.
Quelle propriété d’un problème rend la programmation dynamique intéressante ?
- Ses données sont triées
- Ses sous-problèmes se chevauchent : les mêmes sont rencontrés plusieurs fois
- Il n’a qu’une seule solution
- Il ne contient aucune boucle
Exercice 2
Avec le système de pièces 1, 3, 4, combien de pièces utilise l’algorithme glouton pour rendre 6 ?
Écris tes calculs :
Réponse : ………………

Exercice 3

Que renvoie rendu([1, 3, 4], 10) ?

def rendu(pieces, somme):
    """nb[v] = nombre minimal de pièces pour rendre v."""
    nb = [0] + [float("inf")] * somme
    for v in range(1, somme + 1):
        for p in pieces:
            if p <= v and nb[v - p] + 1 < nb[v]:
                nb[v] = nb[v - p] + 1
    return nb[somme]

Python

Écris tes calculs :

Réponse : ………………

Exercice 4 — Coche « Vrai » ou « Faux ».
Avec la mémoïsation, le calcul de fib(n) demande un nombre d’opérations proportionnel à n.
VraiFaux
Exercice 5
Que renvoie fib_asc(10) ?
Écris tes calculs :
Réponse : ………………
Exercice 6 — Relie chaque élément de gauche à celui de droite.
Associe chaque approche à sa description.
1. 1. Récursivité naïve
2. 2. Mémoïsation
3. 3. Approche ascendante
4. 4. Algorithme glouton
- A. Remplit un tableau du plus petit au plus grand sous-problème
- B. Récursivité avec stockage des résultats déjà calculés
- C. Fait à chaque étape le choix qui semble le meilleur sur le moment
- D. Recalcule plusieurs fois les mêmes sous-problèmes
Exercice 7
Quelle est la distance d’édition entre ROSE et ROSSE ?
Écris tes calculs :
Réponse : ………………
Exercice 8
Explique pourquoi la version récursive naïve de rendu de monnaie (nb(v) = 1 + min nb(v − p), sans mémoire) est très lente pour une grande somme, et comment la programmation dynamique corrige ce défaut.

ulumine.com — exercices corrigés gratuits

ULUMINE · Numérique et sciences informatiques (NSI) · Terminale

La programmation dynamique — S’entraîner

Corrigé détaillé — pour les parents et les enseignants

Exercice 1
Réponse : Ses sous-problèmes se chevauchent : les mêmes sont rencontrés plusieurs fois
Si chaque sous-problème n’apparaissait qu’une fois (comme dans le tri fusion), mémoriser les résultats ne ferait rien gagner.
Exercice 2
Réponse : 3
Glouton : la plus grande pièce ≤ 6 est 4 ; il reste 2, rendu avec 1 + 1. Total : 3 pièces, alors que 3 + 3 n’en utilise que 2.
Exercice 3
Réponse : 3
Par exemple 4 + 3 + 3. On le lit dans le tableau : nb(10) = 1 + min(nb(9), nb(7), nb(6)) = 1 + min(3, 2, 2) = 3.
1. nb(7) = 2 (4 + 3), nb(8) = 2 (4 + 4), nb(9) = 3 (4 + 4 + 1).
2. nb(10) = 1 + 2 = 3.
Exercice 4
Réponse : Vrai
Chaque valeur fib(k) pour k de 0 à n n’est calculée qu’une fois ; les autres appels lisent le dictionnaire en temps constant.
Exercice 5
Réponse : 55
La liste f se remplit : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. f[10] = 55.
Exercice 6
Réponse : 1 → D · 2 → B · 3 → A · 4 → C
Les deux approches de la programmation dynamique donnent le même résultat ; le glouton est plus simple mais pas toujours optimal.
Exercice 7
Réponse : 1
Il suffit d’insérer un S : une seule opération.
Exercice 8
Exemple de réponse : Sans mémoire, nb(v) appelle nb(v − 1), nb(v − 3), nb(v − 4)… et chacun de ces appels en relance d’autres : les mêmes valeurs (nb(v − 4) par exemple est atteint par plusieurs chemins) sont recalculées un très grand nombre de fois ; le nombre d’appels croît exponentiellement. La programmation dynamique calcule chaque nb(k) une seule fois, soit en mémorisant les résultats dans un dictionnaire, soit en remplissant un tableau de 0 à v. Le coût devient proportionnel à v × (nombre de pièces).
C’est exactement la même situation que fib : des sous-problèmes qui se chevauchent.
- Identification des calculs répétés.
- Croissance exponentielle des appels.
- Mémoïsation ou tableau ascendant.
- Coût final proportionnel à v × nombre de pièces.

Quand un tableau est en jeu, remplis-le case par case sur ton brouillon.

Exercices corrigés : 0 / 8

Exercice 1 sur 8
QCM
Quelle propriété d’un problème rend la programmation dynamique intéressante ?
Choisis une réponse
Ses données sont triéesSes sous-problèmes se chevauchent : les mêmes sont rencontrés plusieurs foisIl n’a qu’une seule solutionIl ne contient aucune boucle
Aide d’ULU pour cet exercice
Exercice 2 sur 8
Calcul
Avec le système de pièces 1, 3, 4, combien de pièces utilise l’algorithme glouton pour rendre 6 ?
Ta réponse
Aide d’ULU pour cet exercice

Exercice 3 sur 8

Calcul

Que renvoie rendu([1, 3, 4], 10) ?

def rendu(pieces, somme):
    """nb[v] = nombre minimal de pièces pour rendre v."""
    nb = [0] + [float("inf")] * somme
    for v in range(1, somme + 1):
        for p in pieces:
            if p <= v and nb[v - p] + 1 < nb[v]:
                nb[v] = nb[v - p] + 1
    return nb[somme]

Python

Aide d’ULU pour cet exercice

Exercice 4 sur 8
Vrai ou faux
Avec la mémoïsation, le calcul de fib(n) demande un nombre d’opérations proportionnel à n.
Vrai ou faux ?
VraiFaux
Aide d’ULU pour cet exercice
Exercice 5 sur 8
Calcul
Que renvoie fib_asc(10) ?
Ta réponse
Aide d’ULU pour cet exercice
Exercice 6 sur 8
Association
Associe chaque approche à sa description.
- Récursivité naïve
- Mémoïsation
- Approche ascendante
- Algorithme glouton
Aide d’ULU pour cet exercice
Exercice 7 sur 8
Calcul
Quelle est la distance d’édition entre ROSE et ROSSE ?
Ta réponse
Aide d’ULU pour cet exercice
Exercice 8 sur 8
Question ouverte
Explique pourquoi la version récursive naïve de rendu de monnaie (nb(v) = 1 + min nb(v − p), sans mémoire) est très lente pour une grande somme, et comment la programmation dynamique corrige ce défaut.
Ta réponse
Aide d’ULU pour cet exercice

À découvrir aussi

Terminale · Numérique et sciences informatiques (NSI)

La récursivité

Fonctions récursives en Python : cas de base, appels récursifs, pile d’appels, terminaison et comparaison avec l’itératif. Cours et exercices de NSI Terminale.

Terminale · Numérique et sciences informatiques (NSI)

La programmation orientée objet

Classes, objets, attributs et méthodes en Python : constructeur __init__, self, interface et références. Cours et exercices de programmation objet en NSI Terminale.

Terminale · Numérique et sciences informatiques (NSI)

Listes, piles, files et dictionnaires

Interface et implémentation des structures linéaires : listes chaînées, piles (LIFO), files (FIFO) et dictionnaires en Python. Cours et exercices de NSI Terminale.