QCM : Programmation dynamique : Fibonacci et rendu monnaie — 11 questions

Explication

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. »

Explication

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. »

Explication

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… »

Explication

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. »

Explication

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. »

Explication

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… »

Explication

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… »

Explication

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. »

Explication

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. »

Explication

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… »

Explication

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. »