Quiz: Programmation dynamique : Fibonacci et rendu monnaie — 11 Fragen

1. Qu'est-ce que le problème de redondance dans le calcul récursif de la suite de Fibonacci ?

A. L'utilisation d'une boucle au lieu d'une fonction récursive

B. La multiplication des termes au lieu de leur addition

C. La répétition de nombreux appels avec les mêmes paramètres lors du calcul récursif

D. L'oubli de calculer certains termes de la suite

Answer: (C)

Erklärung

Le problème de redondance décrit est la répétition de nombreux appels avec les mêmes paramètres, ce qui entraîne un gaspillage de temps et de mémoire dans le calcul récursif naïf de Fibonacci. À revoir : Problème de redondance dans le calcul récursif de la suite de Fibonacci. Appui du cours : « Le calcul récursif naïf de Fibonacci entraîne de nombreux appels redondants avec les mêmes paramètres, comme plusieurs appels avec n=2 ou n=3 pour n=5. »

2. Comment utiliser la programmation dynamique par mémorisation pour optimiser un algorithme récursif ?

A. Réécrire l'algorithme en itératif sans utiliser de stockage intermédiaire

B. Mémoriser les résultats des sous-problèmes dépendants dans une mémoire cache pour éviter leur recalcul

C. Calculer chaque sous-problème indépendamment à chaque appel récursif

D. Stocker uniquement le résultat final sans mémoriser les sous-problèmes intermédiaires

Answer: (B)

Erklärung

La programmation dynamique optimise les calculs récursifs en mémorisant les résultats des sous-problèmes dépendants dans une mémoire cache, ce qui évite de recalculer plusieurs fois ces sous-problèmes. À revoir : Principe et utilité de la programmation dynamique par mémorisation. Appui du cours : « **Programmation dynamique** : Une technique d'optimisation des programmes qui consiste à mémoriser les résultats des sous-problèmes pour éviter de les recalculer plusieurs fois, applicable lorsque ces sous-problèmes sont dépendants. »

3. Quel est le rôle principal de la mémoire cache dans la forme Top Down de la programmation dynamique ?

A. Stocker les résultats intermédiaires sans utiliser la récursion

B. Calculer d'abord les plus petits sous-problèmes de façon itérative

C. Remonter progressivement vers le problème initial en itérant sur la liste

D. Éviter les recalculs en vérifiant si le résultat est déjà mémorisé avant chaque calcul

Answer: (D)

Erklärung

La forme Top Down est récursive et consulte la mémoire cache avant chaque calcul pour éviter les recalculs, comme indiqué dans le passage : « En Top Down, la mémoire cache est consultée avant chaque calcul pour éviter les recalculs. » Les autres options décrivent des caractéristiques de Bottom Up ou sont incorrectes pour Top Down. À revoir : Formes Top Down et Bottom Up de la programmation dynamique. Appui du cours : « - La forme Top Down est récursive : elle applique la formule de récurrence en vérifiant d'abord si le résultat est déjà mémorisé. - La forme Bottom Up est itérative : elle calcule d'abord les plus petits sous-problèmes puis remonte progressivement vers le… »

4. Qu'est-ce que la fonction fiboTDAux dans l'application de la programmation dynamique Top Down au calcul de Fibonacci ?

A. Une fonction qui calcule récursivement le terme de Fibonacci en utilisant la mémoire cache pour éviter les recalculs

B. Une fonction qui calcule itérativement les termes de Fibonacci sans utiliser de mémoire cache

C. Une fonction qui initialise la liste de stockage des résultats intermédiaires

D. Une fonction qui retourne directement la valeur n pour n=0 ou n=1 sans calcul

Answer: (A)

Erklärung

La fonction fiboTDAux est définie comme calculant récursivement le terme de Fibonacci en utilisant la mémoire cache pour éviter les recalculs, ce qui correspond exactement à la réponse correcte. À revoir : Application de la programmation dynamique Top Down au calcul de Fibonacci. Appui du cours : « La fonction fiboTDAux calcule récursivement le terme de Fibonacci en utilisant la mémoire cache pour éviter les recalculs. »

5. Quel est le rôle de la variable 'Mini' dans la formulation récursive du problème du rendu de monnaie minimal ?

A. Stocker temporairement la valeur minimale du nombre de pièces nécessaires lors de l'exploration des possibilités

B. Calculer la somme totale des pièces utilisées pour rendre la monnaie

C. Déterminer la valeur maximale des pièces utilisées pour rendre la somme

D. Enregistrer la liste des pièces disponibles pour rendre la somme

Answer: (A)

Erklärung

La variable 'Mini' est définie comme celle qui stocke temporairement la valeur minimale du nombre de pièces nécessaires lors de l'exploration des différentes possibilités dans la fonction récursive, ce qui correspond à l'option 0. À revoir : Formulation récursive du problème du rendu de monnaie minimal. Appui du cours : « Mini : Variable utilisée pour stocker temporairement la valeur minimale du nombre de pièces nécessaires lors de l'exploration des différentes possibilités dans la fonction récursive. »

6. Quel est le rôle principal de l'analyse des appels récursifs redondants dans le rendu de monnaie ?

A. Calculer directement le nombre minimal de pièces nécessaires pour une somme donnée

B. Mettre en évidence l'inefficacité des recalculs multiples justifiant une optimisation dynamique

C. Déterminer la somme maximale pouvant être rendue avec les pièces disponibles

D. Éliminer les pièces inutiles dans la liste des valeurs monétaires

Answer: (B)

Erklärung

L'analyse montre que plusieurs sous-problèmes sont recalculés plusieurs fois, entraînant une inefficacité majeure. Cela justifie l'utilisation d'une approche dynamique pour optimiser le rendu de monnaie. À revoir : Analyse des appels récursifs redondants dans le rendu de monnaie. Appui du cours : « - Pour som=5, plusieurs sous-problèmes sont recalculés plusieurs fois, ce qui montre une inefficacité majeure dans la méthode brute. - Cette redondance entraîne une complexité exponentielle et un gaspillage de ressources, soulignant la nécessité d'une… »

7. Comment la programmation dynamique Top Down optimise-t-elle le rendu de monnaie dans l'implémentation décrite ?

A. En utilisant une liste stock uniquement pour stocker le résultat final

B. En recalculant systématiquement chaque somme pour garantir la précision

C. En ignorant les sous-problèmes déjà calculés et en recalculant tout à chaque appel

D. En mémorisant les résultats intermédiaires dans une liste stock pour éviter de recalculer les mêmes sous-problèmes

Answer: (D)

Erklärung

La fonction renduM_TD initialise une liste stock pour mémoriser les résultats intermédiaires, et renduM_TD_Aux vérifie si stock[som] a déjà été calculé pour retourner le résultat sans recalcul, ce qui optimise le rendu de monnaie. À revoir : Utilisation de la programmation dynamique Top Down pour le rendu de monnaie. Appui du cours : « - La fonction renduM_TD initialise une liste stock pour mémoriser les résultats intermédiaires. - La fonction renduM_TD_Aux applique la programmation dynamique Top Down en vérifiant si stock[som] est déjà calculé. - Si stock[som] > 0, le résultat est… »

8. Quelle est la conséquence directe de l'utilisation de la mémoire cache dans le rendu de monnaie ?

A. Transformer une solution récursive exponentielle en une solution efficace

B. Réduire le nombre minimal de pièces nécessaires pour rendre une somme

C. Éliminer complètement le besoin de calculs récursifs

D. Augmenter la taille du tableau stock pour gérer plus de pièces

Answer: (A)

Erklärung

La mémoire cache stocke et réutilise les résultats des sous-problèmes, ce qui permet de transformer une solution récursive exponentielle en une solution efficace, comme indiqué dans le texte. À revoir : Construction et rôle de la mémoire cache dans le rendu de monnaie. Appui du cours : « La mémoire cache permet de stocker et réutiliser les résultats des sous-problèmes. Elle est essentielle pour transformer une solution récursive exponentielle en une solution efficace. »

9. Qu'est-ce que le tableau 'garde' dans la détermination du nombre minimal de pièces pour un rendu de monnaie ?

A. Un tableau qui stocke pour chaque somme l'indice de la pièce utilisée pour atteindre le minimum

B. Un tableau qui indique la valeur totale des pièces utilisées pour chaque somme

C. Un tableau qui calcule le nombre total de pièces nécessaires pour chaque somme

D. Un tableau qui liste toutes les combinaisons possibles de pièces pour une somme donnée

Answer: (A)

Erklärung

Le tableau 'garde' stocke précisément, pour chaque somme, l'indice de la pièce utilisée pour obtenir le nombre minimal de pièces, ce qui permet ensuite de reconstruire la composition des pièces utilisées. À revoir : Détermination du nombre minimal de pièces et des pièces utilisées. Appui du cours : « Le tableau 'garde' stocke pour chaque somme l'indice de la pièce utilisée pour atteindre le minimum. »

10. Comment l'algorithme modifié utilise-t-il le tableau 'garde' pour déterminer la liste des pièces optimales ?

A. En remplaçant les valeurs dans 'stock' par celles dans 'garde' pour obtenir la liste

B. En triant les pièces selon leurs valeurs dans 'garde' avant de les retourner

C. En comptant simplement le nombre total de pièces dans 'garde'

D. En effectuant une boucle soustractive qui utilise 'garde' pour reconstruire la liste des pièces utilisées

Answer: (D)

Erklärung

La reconstruction de la liste se fait par une boucle soustractive utilisant 'garde', ce tableau contient les indices des pièces qui permettent de retrouver la composition optimale à partir du montant total. À revoir : Algorithme modifié pour retourner la liste des pièces optimales. Appui du cours : « - La fonction modifiée retourne à la fois le nombre minimal de pièces et la liste des pièces utilisées. - Elle utilise deux tableaux : 'stock' pour les minima et 'garde' pour les indices des pièces. - La reconstruction de la liste se fait par une boucle… »

11. Qui est crédité d'avoir proposé la méthode permettant d'éviter les appels récursifs redondants en programmation dynamique ?

A. Alan Turing

B. Claude Shannon

C. John von Neumann

D. Richard Bellman

Answer: (D)

Erklärung

Le passage mentionne explicitement que l'américain Richard Bellman a eu l'idée de mémoriser les résultats des sous-problèmes pour éviter les recalculs redondants, ce qui correspond à la programmation dynamique. À revoir : Exemple pratique d’application du rendu de monnaie optimal. Appui du cours : « 2- La méthode de Bellman (1950) Pour éviter ces appels récursifs redondants et coûteux, l'américain Richard Bellman a eu une idée relativement simple : on va mémoriser les résultats des sous-problèmes afin de ne pas les recalculer plusieurs fois. »