Passez ce Quiz: Programmation dynamique | Zestly

Question 1

Quel est le principe fondamental qui distingue la programmation dynamique d'une approche récursive naïve ?

Accepted Answer

La mémorisation des résultats des sous-problèmes déjà résolus.

Question 2

Parmi les caractéristiques suivantes, lesquelles sont nécessaires pour appliquer la programmation dynamique à un problème ?

Accepted Answer

La présence de sous-problèmes qui se chevauchent.

Question 3

Dans le problème du rendu de monnaie, pourquoi l'algorithme glouton ne garantit-il pas toujours le nombre minimal de pièces ?

Accepted Answer

Parce qu'un choix local optimal peut empêcher d'atteindre l'optimum global.

Question 4

Soit la suite de Fibonacci définie par $F(0)=0, F(1)=1$ et $F(n) = F(n-1) + F(n-2)$. Quelle est la complexité temporelle de l'algorithme récursif naïf ?

Answer

$O(1)$

Answer

$O(n)$

Answer

$O(n^2)$

Answer

$O(2^n)$

Question 5

Quelles sont les deux approches principales pour implémenter la programmation dynamique ?

Answer

Approche descendante (top-down) avec mémoïsation.

Answer

Approche par force brute avec recherche exhaustive.

Answer

Approche aléatoire basée sur des probabilités.

Answer

Approche ascendante (bottom-up) avec tabulation.