Quiz de programmation dynamique : entraînement de Terminale NSI

Quiz

16 questions · correction immédiate · ton score reste sur ton appareil.

1. Quelle phrase décrit le mieux la programmation dynamique ?

   Résoudre un problème en le décomposant en sous-problèmes, résolus des plus petits aux plus grands, en mémorisant les résultats intermédiairesTrier les données puis chercher la solution par dichotomieParcourir tous les cas possibles sans jamais rien mémoriserÉcrire le programme le plus court possible grâce à la récursivité
   Valider

2. La programmation dynamique a été introduite au début des années 1950 par Richard Bellman, et à l'époque le mot « programmation » signifiait planification et ordonnancement.

   VraiFaux
   Valider

3. Pourquoi l'algorithme diviser pour régner « naïf » est-il inefficace pour calculer le $n$-ième terme de la suite de Fibonacci ?

   Parce qu'il résout plusieurs fois le même sous-problèmeParce qu'il ne fonctionne que pour $n$ pairParce qu'il utilise une boucle for au lieu d'une récursionParce qu'il découpe le problème en trop peu de morceaux
   Valider

4. La suite de Fibonacci est définie par $F_0 = 0$, $F_1 = 1$ et $F_n = F_{n-1} + F_{n-2}$ ⁶. Calcule $F_7$.

   Ta réponse
   Valider

5. On calcule $F_5$ avec la fonction récursive naïve fib(n) qui renvoie n si n vaut 0 ou 1, et fib(n-1) + fib(n-2) sinon. Combien d'appels de la fonction sont effectués au total, en comptant l'appel initial et les appels de base ?

   Ta réponse appels
   Valider

6. Combien d'additions une méthode ascendante (boucle qui construit $F_2$, puis $F_3$, etc.) effectue-t-elle pour obtenir $F_{10}$, à partir de $F_0$ et $F_1$ ?

   Ta réponse additions
   Valider

7. Quelles sont les étapes typiques de la conception d'un algorithme de programmation dynamique ? (plusieurs réponses)

   Plusieurs réponses possibles.

   Définir les sous-problèmesÉcrire une relation de récurrenceDonner l'algorithme, en méthode ascendante ou descendanteTrier les données en ordre décroissant avant tout calcul
   Valider

8. Dans la programmation dynamique, les sous-problèmes sont toujours indépendants les uns des autres, comme dans la méthode diviser pour régner.

   VraiFaux
   Valider

9. Quel est le lien entre programmation dynamique et mémoïsation ?

   Ce sont deux techniques voisines, fondées sur l'idée de ne pas refaire un calcul déjà faitLa mémoïsation est une méthode de tri, la programmation dynamique une méthode de rechercheLa mémoïsation interdit toute récursivitéCe sont deux noms exactement identiques, sans aucune différence de mise en œuvre
   Valider

10. Pour le problème du rendu de monnaie avec une récursion, on cherche le nombre minimal de pièces pour une somme somme. La ligne mini = min(mini, 1 + dynRecursif(valeursFaciales, somme - x)) signifie :

    Pour chaque pièce x utilisable, on compare le meilleur résultat trouvé avec « une pièce x plus la solution optimale du reste »On additionne toutes les pièces disponibles puis on retire la plus grandeOn choisit toujours la plus grande pièce possible, sans comparerOn trie les valeurs faciales par ordre croissant
    Valider

11. On dispose de pièces de valeurs 1, 3 et 4 (en quantité illimitée). Quel est le nombre minimal de pièces pour rendre la somme 6 ?

    Ta réponse pièces
    Valider

12. Avec les pièces 1, 3 et 4, l'algorithme glouton (toujours prendre la plus grande pièce possible) donne toujours le même nombre de pièces que la programmation dynamique.

    VraiFaux
    Valider

13. Le problème du sac à dos est NP-difficile. Que dit-on de sa résolution par programmation dynamique ?

    Elle est pseudo-polynomialeElle est impossibleElle est toujours logarithmiqueElle ne nécessite aucun tableau
    Valider

14. Pour calculer $F_n$ par boucle, tu remplis un tableau de $n + 1$ cases. Comment réduire la mémoire utilisée ?

    Ne garder que les deux dernières valeurs calculées, car $F_n$ ne dépend que de $F_{n-1}$ et $F_{n-2}$Doubler la taille du tableau pour aller plus viteRecalculer chaque terme depuis le début à chaque tourIl est impossible de réduire la mémoire
    Valider

15. Dans une résolution par programmation dynamique, on retient parfois « d'où l'on vient » dans un second tableau (par exemple g[s] = s - x). À quoi cela sert-il ?

    À reconstruire la solution elle-même (quelles pièces ont été choisies), et pas seulement sa valeurÀ accélérer le tri des piècesÀ supprimer les sous-problèmes inutiles de la récurrenceÀ remplacer la relation de récurrence
    Valider

16. Parmi ces problèmes, lesquels sont traités par programmation dynamique ? (plusieurs réponses)

    Plusieurs réponses possibles.

    La plus longue sous-chaîne commune de deux textesLe sac à dosLa détection de rupturesLe calcul de la somme de deux entiers positifs
    Valider