Lernzettel: Programmation dynamique : Fibonacci et rendu monnaie

📋 Plan du Cours

1. Problème de redondance dans le calcul récursif de la suite de Fibonacci
2. Principe et utilité de la programmation dynamique par mémorisation
3. Formes Top Down et Bottom Up de la programmation dynamique
4. Application de la programmation dynamique Top Down au calcul de Fibonacci
5. Formulation récursive du problème du rendu de monnaie minimal
6. Analyse des appels récursifs redondants dans le rendu de monnaie
7. Utilisation de la programmation dynamique Top Down pour le rendu de monnaie
8. Construction et rôle de la mémoire cache dans le rendu de monnaie
9. Détermination du nombre minimal de pièces et des pièces utilisées
10. Algorithme modifié pour retourner la liste des pièces optimales
11. Exemple pratique d’application du rendu de monnaie optimal

📖 1. Problème de redondance dans le calcul récursif de la suite de Fibonacci

🔑 Notions clés & Définitions

• Suite de Fibonacci : Une suite numérique où chaque terme est défini par 0 pour n=0, 1 pour n=1, et la somme des deux termes précédents pour tout n supérieur ou égal à 2.

📝 Points essentiels

• 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.
• Pour n=5, la fonction fibo est appelée plusieurs fois avec les mêmes valeurs, par exemple 3 appels avec n=2.
• Ce problème de redondance s'aggrave rapidement avec l'augmentation de n, entraînant un gaspillage de temps et de mémoire.

💡 À retenir

La récursivité naïve dans Fibonacci illustre clairement le gaspillage dû aux calculs répétitifs inutiles.

📖 2. Principe et utilité de la programmation dynamique par mémorisation

🔑 Notions clés & Définitions

• 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.
• Mémoire cache : Un espace de stockage temporaire, souvent sous forme de tableau ou de liste, utilisé pour conserver les solutions des sous-problèmes afin d'éviter leur recalcul.

📝 Points essentiels

• La programmation dynamique évite les recalculs redondants en mémorisant les résultats des sous-problèmes dépendants.
• La mémoïsation utilise une mémoire cache sous forme de tableau ou liste pour stocker ces résultats.
• Cette méthode est applicable lorsque les sous-problèmes partagent des sous-sous-problèmes communs, c'est-à-dire qu'ils sont dépendants.
• Richard Bellman a introduit cette technique en 1950 pour optimiser les calculs récursifs.
• Pour proposer une résolution par la programmation dynamique, il nous faut mémoriser les résultats pour les sommets 0, 1, 2, …, som.

💡 À retenir

La programmation dynamique optimise les calculs récursifs en stockant les résultats intermédiaires pour éliminer les redondances.

📖 3. Formes Top Down et Bottom Up de la programmation dynamique

🔑 Notions clés & Définitions

• Stock : Valeur mémorisée dans la liste de mémoire cache correspondant au résultat du sous-problème d'indice i.
• Top Down : 1 2 5 1 1 1 1 1 1 111 2 2 22 2 1 1 2 Terminale Spécialité NSI Algorithmes Voici ici la version Top Down (forme récursive).
• Bottom Up :
  • Une forme itérative appelée "Bottom Up" (du bas vers le haut): ➢ On résout en premier les problèmes du plus petit niveau, puis ceux du niveau supérieur et au fur et à mesure, on mémorise ces résultats dans la liste de mémoire cache.
• Programmation dynamique : Pour résoudre ce problème de façon récursive, sans parler encore de programmation dynamique, il faut commencer par établir une formule de récurrence.

📝 Points essentiels

• 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 problème initial.
• En Top Down, la mémoire cache est consultée avant chaque calcul pour éviter les recalculs.
• En Bottom Up, les résultats sont stockés au fur et à mesure dans une liste sans appel récursif.
• Dans la pratique, la programmation dynamique peut prendre deux formes:
  • Une forme récursive appelée "Top Down" (du haut vers le bas): ➢ On appelle directement la formule de récurrence.

💡 À retenir

La programmation dynamique peut s'implémenter soit par récursion contrôlée (Top Down), soit par itération progressive (Bottom Up).

📖 4. Application de la programmation dynamique Top Down au calcul de Fibonacci

🔑 Notions clés & Définitions

📝 Points essentiels

• La fonction fiboTD initialise une liste de taille n+1 pour stocker les résultats intermédiaires.
• La fonction fiboTDAux calcule récursivement le terme de Fibonacci en utilisant la mémoire cache pour éviter les recalculs.
• Si le terme fiboTDAux(n) est déjà calculé (stock[n]>0), il est retourné directement sans recalcul.
• La condition d'arrêt est atteinte pour n=0 ou n=1, retournant n directement.

💡 À retenir

L'approche Top Down applique la mémoïsation pour rendre le calcul de Fibonacci récursif efficace et sans redondance.

📖 5. Formulation récursive du problème du rendu de monnaie minimal

🔑 Notions clés & Définitions

• 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.
• Nbre : Tableau ou fonction qui associe à chaque somme la valeur minimale du nombre de pièces nécessaires pour la rendre.
• Si som : On peut alors présenter cette formule de récurrence : nbre[som ]
• Problème du rendu de monnaie : Problème consistant à déterminer le nombre minimal de pièces ou billets nécessaires pour rendre une somme donnée à partir d'une liste de valeurs disponibles.

📝 Points essentiels

• Le problème du rendu de monnaie consiste à rendre une somme donnée avec un nombre minimal de pièces ou billets.
• La formule de récurrence est : nbre[som] = 0 si som = 0, sinon 1 + min(nbre[som - pi]) pour toutes pièces pi ≤ som.
• La fonction récursive renduMonnaie(lst, som) calcule ce minimum en testant toutes les pièces possibles.
• Pour une somme à rendre som, on va noter nbre[som] le nombre minimal de pièces.
• Reprenons le problème initial : Quel est le nombre minimal de pièces (ou billets) à utiliser pour rendre une somme donnée ?

💡 À retenir

Le problème du rendu de monnaie consiste à rendre une somme donnée avec un nombre minimal de pièces ou billets.

📖 6. Analyse des appels récursifs redondants dans le rendu de monnaie

🔑 Notions clés & Définitions

• Exemple : Pour notre système monétaire, la liste sera [0.01,0.02,0.05,0.1,0.2,0.5,1,2,5,10,20,50,100,200,500].

📝 Points essentiels

• 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 optimisation par approche dynamique.
• La méthode brute traite tous les cas possibles sans éviter les recalculs, ce qui limite son efficacité pour des sommes plus grandes.

💡 À retenir

L'analyse de l'arbre d'appels récursifs met en évidence les inefficacités dues aux recalculs multiples dans le rendu de monnaie, justifiant l'utilisation d'une approche dynamique.

📖 7. Utilisation de la programmation dynamique Top Down pour le rendu de monnaie

🔑 Notions clés & Définitions

• RMTD : Fonction qui initialise la liste de stockage et appelle la fonction auxiliaire pour le rendu de monnaie en utilisant la programmation dynamique Top Down.

📝 Points essentiels

• 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 retourné directement pour éviter le recalcul.

💡 À retenir

La programmation dynamique Top Down optimise le rendu de monnaie en mémorisant les solutions partielles pour éviter les recalculs.

📖 8. Construction et rôle de la mémoire cache dans le rendu de monnaie

🔑 Notions clés & Définitions

📝 Points essentiels

• La mémoire cache est un tableau stock de taille som+1 initialisé à zéro.
• Chaque indice i de stock contient le nombre minimal de pièces pour rendre la somme i.
• 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.

💡 À retenir

La mémoire cache est la clé pour transformer la récursivité inefficace du rendu de monnaie en une solution dynamique efficace.

📖 9. Détermination du nombre minimal de pièces et des pièces utilisées

🔑 Notions clés & Définitions

• Mini : Fonction renduM_TD(lst, som): stock = liste de 0 de taille de lst + 1 retourner renduM_TD_Aux(lst, som, stock) fonction renduM_TD_Aux(lst, som, stock): si som

📝 Points essentiels

• Le tableau 'garde' stocke pour chaque somme l'indice de la pièce utilisée pour atteindre le minimum.
• À partir de 'garde', la liste des pièces utilisées peut être reconstruite par soustractions successives de la valeur de la pièce indiquée.

💡 À retenir

Le tableau 'garde' permet de retrouver la composition exacte des pièces utilisées pour un rendu de monnaie optimal.

📖 10. Algorithme modifié pour retourner la liste des pièces optimales

🔑 Notions clés & Définitions

📝 Points essentiels

• 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 soustractive utilisant 'garde'.
• Cette version fournit une solution optimale complète, incluant nombre et composition des pièces.

💡 À retenir

L'algorithme enrichi permet de déterminer la composition optimale des pièces pour le rendu de monnaie, en plus du nombre minimal.

📖 11. Exemple pratique d’application du rendu de monnaie optimal

🔑 Notions clés & Définitions

📝 Points essentiels

• L'exemple montre que pour som=9 avec la liste de pièces donnée, la solution optimale est 3 pièces : [2, 2, 5].
• Le programme calcule automatiquement le nombre minimal de pièces et la liste des pièces à rendre.
• La méthode permet de gérer des systèmes monétaires complexes avec de nombreuses pièces.

💡 À retenir

L'exemple pratique démontre la puissance de la programmation dynamique pour résoudre efficacement des problèmes concrets de rendu de monnaie.

🧩 Compléments de couverture

1. Détail source à réviser : Spécialité NSI Algorithmes Chapitre 15 – La programmation dynamique Introduction : Nous allons aborder la deuxième stratégie d'optimisation de programme : la programmation dynamique qui permet d'éviter de faire plusieurs (Source: "Spécialité NSI Algorithmes Chapitre 15 – La programmation dynamique Introduction : Nous allons aborder la deuxième stratégie d'optimisation de programme : la programmation dynamique qui permet d'éviter de faire plusieurs fois les mêmes calculs. 1- Mise en évidence avec la suite de Fibonacci Nous avons étudié dans le chapitre précédent que la")
2. Détail source à réviser : de programme : la programmation dynamique qui permet d'éviter de faire plusieurs fois les mêmes calculs. 1- Mise en évidence avec la suite de Fibonacci Nous avons étudié dans le chapitre précédent que la méthode « divise (Source: "de programme : la programmation dynamique qui permet d'éviter de faire plusieurs fois les mêmes calculs. 1- Mise en évidence avec la suite de Fibonacci Nous avons étudié dans le chapitre précédent que la méthode « diviser pour régner » découpe un problème en sous-problèmes indépendants (qui ne se chevauchent pas), résout chaque sous-problèmes, et combine")
3. Détail source à réviser : un problème en sous-problèmes indépendants (qui ne se chevauchent pas), résout chaque sous-problèmes, et combine les solutions des sous-problèmes pour former une solution au problème initial. Il y a cependant des cas où (Source: "un problème en sous-problèmes indépendants (qui ne se chevauchent pas), résout chaque sous-problèmes, et combine les solutions des sous-problèmes pour former une solution au problème initial. Il y a cependant des cas où les sous-problèmes ne sont pas indépendants ! On peut alors retrouver un même sous-problème dans des appels récursifs différents, et")
4. Détail source à réviser : ne sont pas indépendants ! On peut alors retrouver un même sous-problème dans des appels récursifs différents, et donc être amené à le résoudre plusieurs fois, ce qui ressemble fort à du gaspillage de temps et de mémoire (Source: "ne sont pas indépendants ! On peut alors retrouver un même sous-problème dans des appels récursifs différents, et donc être amené à le résoudre plusieurs fois, ce qui ressemble fort à du gaspillage de temps et de mémoire. Prenons en exemple l'étude de la suite de Fibonacci qui est définie par : un ={0 si n = 0 1 si n = 1 un− 1+un−2 si n ≥ 2} La fonction")
5. Détail source à réviser : l'étude de la suite de Fibonacci qui est définie par : un ={0 si n = 0 1 si n = 1 un− 1+un−2 si n ≥ 2} La fonction algorithme récursive permettant de calculer le terme d'indice n de cette suite qui nous vient rapidement (Source: "l'étude de la suite de Fibonacci qui est définie par : un ={0 si n = 0 1 si n = 1 un− 1+un−2 si n ≥ 2} La fonction algorithme récursive permettant de calculer le terme d'indice n de cette suite qui nous vient rapidement à l'idée est la suivante : fonction fibo(n): si n == 0 ou n == 1 : retourner n sinon: retourner fibo(n-1) + fibo(n-2) Étudions le cas")
6. Détail source à réviser : suivante : fonction fibo(n): si n == 0 ou n == 1 : retourner n sinon: retourner fibo(n-1) + fibo(n-2) Étudions le cas pour n = 5 et essayons de représenter les appels successifs de cette fonction sous la forme d'un arbre (Source: "suivante : fonction fibo(n): si n == 0 ou n == 1 : retourner n sinon: retourner fibo(n-1) + fibo(n-2) Étudions le cas pour n = 5 et essayons de représenter les appels successifs de cette fonction sous la forme d'un arbre : fibo(5) fibo(4) fibo(3) fibo(3) fibo(2) fibo(2) fibo(1) fibo(2) fibo(1) fibo(1) fibo(0) fibo(1) fibo(0) fibo(1) fibo(0) Terminale")
7. Détail source à réviser : fibo(3) fibo(3) fibo(2) fibo(2) fibo(1) fibo(2) fibo(1) fibo(1) fibo(0) fibo(1) fibo(0) fibo(1) fibo(0) Terminale Spécialité NSI Algorithmes On peut s'apercevoir que plusieurs appels récursifs à cette fonction sont réali (Source: "fibo(3) fibo(3) fibo(2) fibo(2) fibo(1) fibo(2) fibo(1) fibo(1) fibo(0) fibo(1) fibo(0) fibo(1) fibo(0) Terminale Spécialité NSI Algorithmes On peut s'apercevoir que plusieurs appels récursifs à cette fonction sont réalisés avec le même valeur de paramètre : ➢ 3 appels avec la valeur 2 ➢ 2 appels avec la valeur 3 Remarques : • Il est évident que la")
8. Détail source à réviser : de paramètre : ➢ 3 appels avec la valeur 2 ➢ 2 appels avec la valeur 3 Remarques : • Il est évident que la situation s'empirerait pour des valeurs de n plus grandes. • Il y a donc un grand nombre d'opérations qui sont in (Source: "de paramètre : ➢ 3 appels avec la valeur 2 ➢ 2 appels avec la valeur 3 Remarques : • Il est évident que la situation s'empirerait pour des valeurs de n plus grandes. • Il y a donc un grand nombre d'opérations qui sont inutiles car redondantes. 2- La méthode de Bellman (1950) Pour éviter ces appels récursifs redondants et coûteux, l'américain Richard")
9. Détail source à réviser : 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 (Source: "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. Cette technique n'est valable que si les sous-problèmes sont dépendants, c'est-à-dire que ces")
10. Détail source à réviser : plusieurs fois. Cette technique n'est valable que si les sous-problèmes sont dépendants, c'est-à-dire que ces sous-problèmes ont des sous-sous-problèmes communs. La mémorisation des solutions des sous-problèmes est une s (Source: "plusieurs fois. Cette technique n'est valable que si les sous-problèmes sont dépendants, c'est-à-dire que ces sous-problèmes ont des sous-sous-problèmes communs. La mémorisation des solutions des sous-problèmes est une sorte de mémoire cache implémentée sous forme de tableau ou de liste. Cette technique porte le nom de programmation dynamique. Dans la")
11. Détail source à réviser : implémentée sous forme de tableau ou de liste. Cette technique porte le nom de programmation dynamique. Dans la pratique, la programmation dynamique peut prendre deux formes: • Une forme récursive appelée "Top Down" (du (Source: "implémentée sous forme de tableau ou de liste. Cette technique porte le nom de programmation dynamique. Dans la pratique, la programmation dynamique peut prendre deux formes: • Une forme récursive appelée "Top Down" (du haut vers le bas): ➢ On appelle directement la formule de récurrence. ➢ Lors d'un appel récursif, avant d'effectuer le calcul, on")
12. Détail source à réviser : ➢ On appelle directement la formule de récurrence. ➢ Lors d'un appel récursif, avant d'effectuer le calcul, on vérifie dans la liste de la mémoire cache si ce calcul n'a pas déjà été fait. On parle aussi de technique de (Source: "➢ On appelle directement la formule de récurrence. ➢ Lors d'un appel récursif, avant d'effectuer le calcul, on vérifie dans la liste de la mémoire cache si ce calcul n'a pas déjà été fait. On parle aussi de technique de mémoïsation (https://fr.wikipedia.org/wiki/Mémoïsation). • Une forme itérative appelée "Bottom Up" (du bas vers le haut): ➢ On résout en")
13. Détail source à réviser : tps://fr.wikipedia.org/wiki/Mémoïsation). • Une forme itérative appelée "Bottom Up" (du bas vers le haut): ➢ On résout en premier les problèmes du plus petit niveau, puis ceux du niveau supérieur et au fur et à mesure, o (Source: "tps://fr.wikipedia.org/wiki/Mémoïsation). • Une forme itérative appelée "Bottom Up" (du bas vers le haut): ➢ On résout en premier les problèmes du plus petit niveau, puis ceux du niveau supérieur et au fur et à mesure, on mémorise ces résultats dans la liste de mémoire cache. ➢ On continue jusqu'au niveau qui nous intéresse. Terminale Spécialité NSI")
14. Détail source à réviser : dans la liste de mémoire cache. ➢ On continue jusqu'au niveau qui nous intéresse. Terminale Spécialité NSI Algorithmes 2-1- Calcul de la suite de Fibonacci en "Top Down" On va appliquer la forme "Top Down" sur la suite d (Source: "dans la liste de mémoire cache. ➢ On continue jusqu'au niveau qui nous intéresse. Terminale Spécialité NSI Algorithmes 2-1- Calcul de la suite de Fibonacci en "Top Down" On va appliquer la forme "Top Down" sur la suite de Fibonacci pour le rang n. Il nous faut donc mémoriser les termes d'indice 0,1,2,…,n. Nous allons donc stocker ces résultats")
15. Détail source à réviser : le rang n. Il nous faut donc mémoriser les termes d'indice 0,1,2,…,n. Nous allons donc stocker ces résultats intermédiaires dans une liste de (n+1) éléments initialisés à 0 : fonction fiboTD(n): stock = liste de 0 de tai (Source: "le rang n. Il nous faut donc mémoriser les termes d'indice 0,1,2,…,n. Nous allons donc stocker ces résultats intermédiaires dans une liste de (n+1) éléments initialisés à 0 : fonction fiboTD(n): stock = liste de 0 de taille n+1 stock[1] = 1 retourner fiboTDAux fonction fiboTDAux(n, stock): si n == 0 ou n == 1: retourner n sinon: si stock[n] > 0: retourner")
16. Détail source à réviser : 1 retourner fiboTDAux fonction fiboTDAux(n, stock): si n == 0 ou n == 1: retourner n sinon: si stock[n] > 0: retourner stock[n] sinon: stock[n] = fiboTDAux(n-1, stock) + fiboTDAux(n-2, stock) retourner stock[n] Précision (Source: "1 retourner fiboTDAux fonction fiboTDAux(n, stock): si n == 0 ou n == 1: retourner n sinon: si stock[n] > 0: retourner stock[n] sinon: stock[n] = fiboTDAux(n-1, stock) + fiboTDAux(n-2, stock) retourner stock[n] Précisions : • La première fonction crée la liste de 0 de taille n+1 et place 1 dans l'indice 1. Elle permet le premier appel de la fonction")
17. Détail source à réviser : crée la liste de 0 de taille n+1 et place 1 dans l'indice 1. Elle permet le premier appel de la fonction récursive qui effectue les calculs. • La première condition de la deuxième fonction permet l’arrêt des appels récur (Source: "crée la liste de 0 de taille n+1 et place 1 dans l'indice 1. Elle permet le premier appel de la fonction récursive qui effectue les calculs. • La première condition de la deuxième fonction permet l’arrêt des appels récursifs quand n vaut 0 ou 1. • La dernière condition de la deuxième fonction permet de retourner la valeur de la suite de Fibonacci si")
18. Détail source à réviser : n vaut 0 ou 1. • La dernière condition de la deuxième fonction permet de retourner la valeur de la suite de Fibonacci si elle a déjà été calculée et stockée dans le tableau sinon de la calculer puis de la retourner . 2-2 (Source: "n vaut 0 ou 1. • La dernière condition de la deuxième fonction permet de retourner la valeur de la suite de Fibonacci si elle a déjà été calculée et stockée dans le tableau sinon de la calculer puis de la retourner . 2-2- Calcul de la suite de Fibonacci en "Buttom Up" On va appliquer la forme "Bottom Up" sur la suite de Fibonacci pour le rang n. On va")
19. Détail source à réviser : de Fibonacci en "Buttom Up" On va appliquer la forme "Bottom Up" sur la suite de Fibonacci pour le rang n. On va mémoriser les valeurs de la suite quand n augmente et les stocker au fur et à mesure dans une liste : fonct (Source: "de Fibonacci en "Buttom Up" On va appliquer la forme "Bottom Up" sur la suite de Fibonacci pour le rang n. On va mémoriser les valeurs de la suite quand n augmente et les stocker au fur et à mesure dans une liste : fonction fiboBU(n): stock = liste de 0 de taille n+1 stock[1] = 1 pour les indices i de 2 à n+1: stock[i] = stock[i-1] + stock[i-2] retourner")
20. Détail source à réviser : = liste de 0 de taille n+1 stock[1] = 1 pour les indices i de 2 à n+1: stock[i] = stock[i-1] + stock[i-2] retourner stock[n] Précision : Ici, il y a pas d'appel récursif mais la formule de récurrence de la suite est sous (Source: "= liste de 0 de taille n+1 stock[1] = 1 pour les indices i de 2 à n+1: stock[i] = stock[i-1] + stock[i-2] retourner stock[n] Précision : Ici, il y a pas d'appel récursif mais la formule de récurrence de la suite est sous la forme itérative. Terminale Spécialité NSI Algorithmes 3- Le problème du rendu de monnaie Ce problème doit vous être connu puisque")
21. Détail source à réviser : Terminale Spécialité NSI Algorithmes 3- Le problème du rendu de monnaie Ce problème doit vous être connu puisque vous l'avez déjà rencontré en classe de première sur la notion des algorithmes gloutons (Activité 23). Repr (Source: "Terminale Spécialité NSI Algorithmes 3- Le problème du rendu de monnaie Ce problème doit vous être connu puisque vous l'avez déjà rencontré en classe de première sur la notion des algorithmes gloutons (Activité 23). Reprenons le problème initial : Quel est le nombre minimal de pièces (ou billets) à utiliser pour rendre une somme donnée ? On part d'une")
22. Détail source à réviser : initial : Quel est le nombre minimal de pièces (ou billets) à utiliser pour rendre une somme donnée ? On part d'une liste de pièce ou billet possible dans un système monétaire connu [p1,p2,p3,…,pn]. Exemple : Pour notre (Source: "initial : Quel est le nombre minimal de pièces (ou billets) à utiliser pour rendre une somme donnée ? On part d'une liste de pièce ou billet possible dans un système monétaire connu [p1,p2,p3,…,pn]. Exemple : Pour notre système monétaire, la liste sera [0.01,0.02,0.05,0.1,0.2,0.5,1,2,5,10,20,50,100,200,500]. Pour résoudre ce problème de façon récursive,")
23. Détail source à réviser : la liste sera [0.01,0.02,0.05,0.1,0.2,0.5,1,2,5,10,20,50,100,200,500]. Pour résoudre ce problème de façon récursive, sans parler encore de programmation dynamique, il faut commencer par établir une formule de récurrence. (Source: "la liste sera [0.01,0.02,0.05,0.1,0.2,0.5,1,2,5,10,20,50,100,200,500]. Pour résoudre ce problème de façon récursive, sans parler encore de programmation dynamique, il faut commencer par établir une formule de récurrence. Pour une somme à rendre som, on va noter nbre[som] le nombre minimal de pièces. A partir de som, on peut choisir de rendre d'abord p1 ou")
24. Détail source à réviser : rendre som, on va noter nbre[som] le nombre minimal de pièces. A partir de som, on peut choisir de rendre d'abord p1 ou p2 ou p3 … ou pn. Les sommes inférieures à som obtenables à partir de som sont donc som - p1, som – (Source: "rendre som, on va noter nbre[som] le nombre minimal de pièces. A partir de som, on peut choisir de rendre d'abord p1 ou p2 ou p3 … ou pn. Les sommes inférieures à som obtenables à partir de som sont donc som - p1, som – p2, som – p3,…, som – pn. On peut alors présenter cette formule de récurrence : nbre[som ]={0 si som = 0 1+min(nbre [som− pi]) si som > 0")
25. Détail source à réviser : – pn. On peut alors présenter cette formule de récurrence : nbre[som ]={0 si som = 0 1+min(nbre [som− pi]) si som > 0 avec i ∈ [1,n] et pi < som} On peut proposer la fonction suivante permettant de rendre la somme som av (Source: "– pn. On peut alors présenter cette formule de récurrence : nbre[som ]={0 si som = 0 1+min(nbre [som− pi]) si som > 0 avec i ∈ [1,n] et pi < som} On peut proposer la fonction suivante permettant de rendre la somme som avec les pièces ou billets présents dans la liste en exemple ci-dessus : fonction renduMonnaie(lst, som): si som == 0: retourner 0 sinon:")
26. Détail source à réviser : présents dans la liste en exemple ci-dessus : fonction renduMonnaie(lst, som): si som == 0: retourner 0 sinon: mini = som + 1 pour tous les indices i de la liste lst: si lst[i] ≤ som: nbre = 1 + renduMonnaie(lst,som-lst[ (Source: "présents dans la liste en exemple ci-dessus : fonction renduMonnaie(lst, som): si som == 0: retourner 0 sinon: mini = som + 1 pour tous les indices i de la liste lst: si lst[i] ≤ som: nbre = 1 + renduMonnaie(lst,som-lst[i]) si nbre < mini: mini = nbre retourner mini Précision : La technique pour le calcul du minimum est des plus classiques. On")
27. Détail source à réviser : mini: mini = nbre retourner mini Précision : La technique pour le calcul du minimum est des plus classiques. On initialise d'abord une variable arbitrairement "trop grande" destinée à contenir in fine ce minimum (dans no (Source: "mini: mini = nbre retourner mini Précision : La technique pour le calcul du minimum est des plus classiques. On initialise d'abord une variable arbitrairement "trop grande" destinée à contenir in fine ce minimum (dans notre cas som + 1). On parcourt ensuite un à un les éléments de notre liste sur lequel on effectue la minimisation en mettant à jour si")
28. Détail source à réviser : parcourt ensuite un à un les éléments de notre liste sur lequel on effectue la minimisation en mettant à jour si nécessaire. Nous avons logiquement restreint l'ensemble des pièces à celles plus petites que la somme à ren (Source: "parcourt ensuite un à un les éléments de notre liste sur lequel on effectue la minimisation en mettant à jour si nécessaire. Nous avons logiquement restreint l'ensemble des pièces à celles plus petites que la somme à rendre. Cet algorithme fait bien partie de la méthode "diviser pour régner" puisque nous avons divisé le problème initial puis appliqué un")
29. Détail source à réviser : fait bien partie de la méthode "diviser pour régner" puisque nous avons divisé le problème initial puis appliqué un traitement récursif. Nous sommes de plus dans une situation où les sous-problèmes ne sont pas indépendan (Source: "fait bien partie de la méthode "diviser pour régner" puisque nous avons divisé le problème initial puis appliqué un traitement récursif. Nous sommes de plus dans une situation où les sous-problèmes ne sont pas indépendants. Terminale Spécialité NSI Algorithmes Pour s'en assurer, on peut représenter les appels à cette fonction récursive sous la forme d'un")
30. Détail source à réviser : NSI Algorithmes Pour s'en assurer, on peut représenter les appels à cette fonction récursive sous la forme d'un arbre. On a pris som = 5. Les valeurs inscrites sur les liaisons correspondent aux valeurs des pièces ou bil (Source: "NSI Algorithmes Pour s'en assurer, on peut représenter les appels à cette fonction récursive sous la forme d'un arbre. On a pris som = 5. Les valeurs inscrites sur les liaisons correspondent aux valeurs des pièces ou billets inclues dans la liste suivante : lst= [1,2,5,10,20,50,100,200,500]. RM* = renduMonnaie RM*(lst, 5) RM(lst,4) RM(lst,3) RM(lst,")
31. Détail source à réviser : dans la liste suivante : lst= [1,2,5,10,20,50,100,200,500]. RM* = renduMonnaie RM*(lst, 5) RM(lst,4) RM(lst,3) RM(lst, 0) RM(lst,3) RM(lst,2) RM(lst,2) RM(lst,1) RM(lst,2) RM(lst,1) RM(lst,1) RM(lst,0) RM(lst,1) RM(lst,0 (Source: "dans la liste suivante : lst= [1,2,5,10,20,50,100,200,500]. RM* = renduMonnaie RM*(lst, 5) RM(lst,4) RM(lst,3) RM(lst, 0) RM(lst,3) RM(lst,2) RM(lst,2) RM(lst,1) RM(lst,2) RM(lst,1) RM(lst,1) RM(lst,0) RM(lst,1) RM(lst,0) RM(lst,0) RM(lst,1) RM(lst,0) RM(lst,0) RM(lst,0) RM(lst,0) RM(lst,0) Remarques : • Tous les cas sont traités. Les algorithmes qui")
32. Détail source à réviser : RM(lst,0) RM(lst,0) RM(lst,0) RM(lst,0) RM(lst,0) Remarques : • Tous les cas sont traités. Les algorithmes qui traitent tous les cas sont appelés "force brute". • La profondeur minimale de la feuille 0 est de 1, il y a u (Source: "RM(lst,0) RM(lst,0) RM(lst,0) RM(lst,0) RM(lst,0) Remarques : • Tous les cas sont traités. Les algorithmes qui traitent tous les cas sont appelés "force brute". • La profondeur minimale de la feuille 0 est de 1, il y a une seule possibilité avec le rendu d'une pièce de 5. • Dans certains cas, il arrive qu'une feuille ne soit pas nulle, la valeur")
33. Détail source à réviser : avec le rendu d'une pièce de 5. • Dans certains cas, il arrive qu'une feuille ne soit pas nulle, la valeur retournée par la fonction est dans notre cas (som + 1) et cette solution ne sera pas retenue. • On remarque égale (Source: "avec le rendu d'une pièce de 5. • Dans certains cas, il arrive qu'une feuille ne soit pas nulle, la valeur retournée par la fonction est dans notre cas (som + 1) et cette solution ne sera pas retenue. • On remarque également de nombreux appels redondants, ce qui nous oriente vers une résolution en approche dynamique. Pour proposer une résolution par la")
34. Détail source à réviser : appels redondants, ce qui nous oriente vers une résolution en approche dynamique. Pour proposer une résolution par la programmation dynamique, il nous faut mémoriser les résultats pour les sommets 0, 1, 2, …, som. Nous a (Source: "appels redondants, ce qui nous oriente vers une résolution en approche dynamique. Pour proposer une résolution par la programmation dynamique, il nous faut mémoriser les résultats pour les sommets 0, 1, 2, …, som. Nous allons donc stocker ces résultats intermédiaires dans une liste de (som + 1) éléments initialisés à 0. 1 2 5 1 1 1 1 1 1 111 2 2 22 2 1 1")
35. Détail source à réviser : ces résultats intermédiaires dans une liste de (som + 1) éléments initialisés à 0. 1 2 5 1 1 1 1 1 1 111 2 2 22 2 1 1 2 Terminale Spécialité NSI Algorithmes Voici ici la version Top Down (forme récursive). fonction rendu (Source: "ces résultats intermédiaires dans une liste de (som + 1) éléments initialisés à 0. 1 2 5 1 1 1 1 1 1 111 2 2 22 2 1 1 2 Terminale Spécialité NSI Algorithmes Voici ici la version Top Down (forme récursive). fonction renduM_TD(lst, som): stock = liste de 0 de taille de lst + 1 retourner renduM_TD_Aux(lst, som, stock) fonction renduM_TD_Aux(lst, som, stock):")
36. Détail source à réviser : = liste de 0 de taille de lst + 1 retourner renduM_TD_Aux(lst, som, stock) fonction renduM_TD_Aux(lst, som, stock): si som == 0: retourner 0 sinon: si stock[som] > 0: retourner stock[som] sinon: mini = som + 1 pour tous (Source: "= liste de 0 de taille de lst + 1 retourner renduM_TD_Aux(lst, som, stock) fonction renduM_TD_Aux(lst, som, stock): si som == 0: retourner 0 sinon: si stock[som] > 0: retourner stock[som] sinon: mini = som + 1 pour tous les indices i de la liste lst: si lst[i] ≤ som: nbre = 1 + renduM_TD_Aux(lst,som-lst[i],stock) si nbre < mini: mini = nbre stock[som]")
37. Détail source à réviser : la liste lst: si lst[i] ≤ som: nbre = 1 + renduM_TD_Aux(lst,som-lst[i],stock) si nbre < mini: mini = nbre stock[som] = mini retourner mini Voici l'arbre obtenu avec la version Top Down: RMTD* = renduMonnaie RMTD*(lst, 5) (Source: "la liste lst: si lst[i] ≤ som: nbre = 1 + renduM_TD_Aux(lst,som-lst[i],stock) si nbre < mini: mini = nbre stock[som] = mini retourner mini Voici l'arbre obtenu avec la version Top Down: RMTD* = renduMonnaie RMTD*(lst, 5) RMTD(lst,4) RMTD(lst,3) RM(lst, 0) RMTD(lst,3) RMTD(lst,2) RMTD(lst,2) RMTD(lst,1) RMTD(lst,1) RMTD(lst,0) RMTD(lst,0) A l'issue du")
38. Détail source à réviser : RM(lst, 0) RMTD(lst,3) RMTD(lst,2) RMTD(lst,2) RMTD(lst,1) RMTD(lst,1) RMTD(lst,0) RMTD(lst,0) A l'issue du programme, nous obtenons une liste de mémoire cache, qui nous donne, pour toutes les valeurs inférieures ou égal (Source: "RM(lst, 0) RMTD(lst,3) RMTD(lst,2) RMTD(lst,2) RMTD(lst,1) RMTD(lst,1) RMTD(lst,0) RMTD(lst,0) A l'issue du programme, nous obtenons une liste de mémoire cache, qui nous donne, pour toutes les valeurs inférieures ou égales à som, le nombre minimum de pièces. Dans notre exemple, on a stock qui correspond au tableau suivant : i 0 1 2 3 4 5 stock[i] 0")
39. Détail source à réviser : nombre minimum de pièces. Dans notre exemple, on a stock qui correspond au tableau suivant : i 0 1 2 3 4 5 stock[i] 0 1 1 2 2 1 Pour être complet, il nous reste à donner le nombre d'exemplaire de chaque 1 2 5 1 1 1 2 2 2 (Source: "nombre minimum de pièces. Dans notre exemple, on a stock qui correspond au tableau suivant : i 0 1 2 3 4 5 stock[i] 0 1 1 2 2 1 Pour être complet, il nous reste à donner le nombre d'exemplaire de chaque 1 2 5 1 1 1 2 2 2 1 Terminale Spécialité NSI Algorithmes pièce ou billet dont il faut se servir pour rendre som. Il nous faut alors modifier les fonctions")
40. Détail source à réviser : NSI Algorithmes pièce ou billet dont il faut se servir pour rendre som. Il nous faut alors modifier les fonctions ci-dessus en faisant intervenir un nouveau tableau qu'on appellera "garde" dont le contenu est égal au num (Source: "NSI Algorithmes pièce ou billet dont il faut se servir pour rendre som. Il nous faut alors modifier les fonctions ci-dessus en faisant intervenir un nouveau tableau qu'on appellera "garde" dont le contenu est égal au numéro de la pièce utilisée. On peut aisément, à partir des arbres vus précédemment voir exemple que : i 0 1 2 3 4 5 garde[i] 0 1 2 1 2")
41. Détail source à réviser : utilisée. On peut aisément, à partir des arbres vus précédemment voir exemple que : i 0 1 2 3 4 5 garde[i] 0 1 2 1 2 3 Précisions : Cela correspond au minimum de pièces. Par exemple : Pour som = 5, le minimum de pièce es (Source: "utilisée. On peut aisément, à partir des arbres vus précédemment voir exemple que : i 0 1 2 3 4 5 garde[i] 0 1 2 1 2 3 Précisions : Cela correspond au minimum de pièces. Par exemple : Pour som = 5, le minimum de pièce est 1 et sa valeur est 5, ce qui correspond à la 3ème place dans notre système. Pour som = 3, le minimum de pièce est de 2 et on passe par")
42. Détail source à réviser : 5, ce qui correspond à la 3ème place dans notre système. Pour som = 3, le minimum de pièce est de 2 et on passe par le chemin de la pièce de valeur 2, c'est à dire la 2ème pièce. Pour obtenir la liste des pièces et bille (Source: "5, ce qui correspond à la 3ème place dans notre système. Pour som = 3, le minimum de pièce est de 2 et on passe par le chemin de la pièce de valeur 2, c'est à dire la 2ème pièce. Pour obtenir la liste des pièces et billets à utiliser, il suffit de faire des soustractions successives. Par exemple, pour som = 5, puisque garde[5]=3, on doit d'abord rendre")
43. Détail source à réviser : suffit de faire des soustractions successives. Par exemple, pour som = 5, puisque garde[5]=3, on doit d'abord rendre la 3ème pièce, celle-ci vaut 5, il ne reste rien à rendre puisque som-5=0. Si nous prenons som = 3, pui (Source: "suffit de faire des soustractions successives. Par exemple, pour som = 5, puisque garde[5]=3, on doit d'abord rendre la 3ème pièce, celle-ci vaut 5, il ne reste rien à rendre puisque som-5=0. Si nous prenons som = 3, puisque garde[3]=1, on doit d'abord rendre puisque la 1ère pièce, celle-ci vaut 1, il nous reste à rendre som-1 = 2, puisque garde[2] = 2,")
44. Détail source à réviser : doit d'abord rendre puisque la 1ère pièce, celle-ci vaut 1, il nous reste à rendre som-1 = 2, puisque garde[2] = 2, on rend ensuite la 2ème pièce de valeur 2 et il ne reste plus rien à rendre. D'un point de vue algorithm (Source: "doit d'abord rendre puisque la 1ère pièce, celle-ci vaut 1, il nous reste à rendre som-1 = 2, puisque garde[2] = 2, on rend ensuite la 2ème pièce de valeur 2 et il ne reste plus rien à rendre. D'un point de vue algorithmique, on va retourner une liste "piece" constituée des valeurs des pièces à retourner. Les fonctions modifiées deviennent alors les")
45. Détail source à réviser : une liste "piece" constituée des valeurs des pièces à retourner. Les fonctions modifiées deviennent alors les suivantes : fonction renduM_TD(lst, som): stock = liste de 0 de taille de lst + 1 garde = liste de 0 de taille (Source: "une liste "piece" constituée des valeurs des pièces à retourner. Les fonctions modifiées deviennent alors les suivantes : fonction renduM_TD(lst, som): stock = liste de 0 de taille de lst + 1 garde = liste de 0 de taille de lst + 1 retourner renduM_TD_Aux(lst, som, stock, garde) fonction renduM_TD_Aux(lst, som, stock, garde): si som == 0: retourner")
46. Détail source à réviser : renduM_TD_Aux(lst, som, stock, garde) fonction renduM_TD_Aux(lst, som, stock, garde): si som == 0: retourner 0,[] sinon: si stock[som] > 0: retourner stock[som],garde[som] sinon: mini = som + 1 pour tous les indices i de (Source: "renduM_TD_Aux(lst, som, stock, garde) fonction renduM_TD_Aux(lst, som, stock, garde): si som == 0: retourner 0,[] sinon: si stock[som] > 0: retourner stock[som],garde[som] sinon: mini = som + 1 pour tous les indices i de la liste lst: si lst[i] ≤ som: nbre = 1 + renduM_TD_Aux(lst,som-lst[i],stock,garde)[0] si nbre < mini: mini = nbre stock[som] =")
47. Détail source à réviser : si lst[i] ≤ som: nbre = 1 + renduM_TD_Aux(lst,som-lst[i],stock,garde)[0] si nbre < mini: mini = nbre stock[som] = mini garde[som] = i+1 som2, piece = som, [] tant que som2 > 0: ajouter à piece l'élément lst[garde[som2]-1 (Source: "si lst[i] ≤ som: nbre = 1 + renduM_TD_Aux(lst,som-lst[i],stock,garde)[0] si nbre < mini: mini = nbre stock[som] = mini garde[som] = i+1 som2, piece = som, [] tant que som2 > 0: ajouter à piece l'élément lst[garde[som2]-1] soustraire à som2 la valeur lst[garde[som2]-1] retourner mini, piece Terminale Spécialité NSI Algorithmes Si nous souhaitons rendre de")
48. Détail source à réviser : soustraire à som2 la valeur lst[garde[som2]-1] retourner mini, piece Terminale Spécialité NSI Algorithmes Si nous souhaitons rendre de manière optimale une valeur 9 avec la liste des pièces et billets donnée, on obtient, (Source: "soustraire à som2 la valeur lst[garde[som2]-1] retourner mini, piece Terminale Spécialité NSI Algorithmes Si nous souhaitons rendre de manière optimale une valeur 9 avec la liste des pièces et billets donnée, on obtient, en ayant notre programme le résultat suivant : (3,[2, 2, 5]). Il nous faut bien 3 pièces : 2 pièces de 2 et un billet de")
49. Détail source à réviser : ce avec la suite de Fibonacci Nous avons étudié dans le chapitre précédent que la méthode « diviser pour régner » découpe un problème en sous-problèmes indépendants (qui ne se chevauchent pas), résout chaque sous-problèm (Source: "ce avec la suite de Fibonacci Nous avons étudié dans le chapitre précédent que la méthode « diviser pour régner » découpe un problème en sous-problèmes indépendants (qui ne se chevauchent pas), résout chaque sous-problèmes, et combine les solutions des sous-problèmes pour")
50. Détail source à réviser : Prenons en exemple l'étude de la suite de Fibonacci qui est définie par : un ={0 si n = 0 1 si n = 1 un− 1+un−2 si n ≥ 2} La fonction algorithme récursive permettant de calculer le terme d'indice n de cette suite qui nou (Source: "Prenons en exemple l'étude de la suite de Fibonacci qui est définie par : un ={0 si n = 0 1 si n = 1 un− 1+un−2 si n ≥ 2} La fonction algorithme récursive permettant de calculer le terme d'indice n de cette suite qui nous vient rapidement à l'idée est la suivante : fonction fibo(n): si n == 0 ou n == 1 : retourner n sinon: retourner fibo(n-1) + fibo(n-2)...")
51. Détail source à réviser : ient rapidement à l'idée est la suivante : fonction fibo(n): si n == 0 ou n == 1 : retourner n sinon: retourner fibo(n-1) + fibo(n-2) Étudions le cas pour n = 5 et essayons de représenter les appels successifs de cette (Source: "ient rapidement à l'idée est la suivante : fonction fibo(n): si n == 0 ou n == 1 : retourner n sinon: retourner fibo(n-1) + fibo(n-2) Étudions le cas pour n = 5 et essayons de représenter les appels successifs de cette")
52. Détail source à réviser : 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 (Source: "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")
53. Détail source à réviser : Cette technique n'est valable que si les sous-problèmes sont dépendants, c'est-à-dire que ces sous-problèmes ont des sous-sous-problèmes communs (Source: "Cette technique n'est valable que si les sous-problèmes sont dépendants, c'est-à-dire que ces sous-problèmes ont des sous-sous-problèmes communs")
54. Détail source à réviser : de mémoïsation (https://fr.wikipedia.org/wiki/Mémoïsation). • Une forme itérative appelée "Bottom Up" (du bas vers le haut): ➢ On résout en premier les problèmes du plus petit niveau, puis ceux du niveau supérieur et au (Source: "de mémoïsation (https://fr.wikipedia.org/wiki/Mémoïsation). • Une forme itérative appelée "Bottom Up" (du bas vers le haut): ➢ On résout en premier les problèmes du plus petit niveau, puis ceux du niveau supérieur et au fur et à mesure, on mémorise ces résultat")
55. Détail source à réviser : n. Il nous faut donc mémoriser les termes d'indice 0,1,2,…,n (Source: "n. Il nous faut donc mémoriser les termes d'indice 0,1,2,…,n")
56. Détail source à réviser : 1. Elle permet le premier appel de la fonction récursive qui effectue les calculs (Source: "1. Elle permet le premier appel de la fonction récursive qui effectue les calculs")
57. Détail source à réviser : 1. • La dernière condition de la deuxième fonction permet de retourner la valeur de la suite de Fibonacci si elle a déjà été calculée et stockée dans le tableau sinon de la calculer puis de la retourner (Source: "1. • La dernière condition de la deuxième fonction permet de retourner la valeur de la suite de Fibonacci si elle a déjà été calculée et stockée dans le tableau sinon de la calculer puis de la retourner")
58. Détail source à réviser : n. On va mémoriser les valeurs de la suite quand n augmente et les stocker au fur et à mesure dans une liste : fonction fiboBU(n): stock = liste de 0 de taille n+1 stock[1] = 1 pour les indices i de 2 à n+1: stock[i] = s (Source: "n. On va mémoriser les valeurs de la suite quand n augmente et les stocker au fur et à mesure dans une liste : fonction fiboBU(n): stock = liste de 0 de taille n+1 stock[1] = 1 pour les indices i de 2 à n+1: stock[i] = stock[i-1] + stock[i-2] retourner stock[n] Précision : Ici, il y a pas d'appel récursif mais la formule de récurrence de la suite est sous...")
59. Détail source à réviser : Reprenons le problème initial : Quel est le nombre minimal de pièces (ou billets) à utiliser pour rendre une somme donnée ? On part d'une liste de pièce ou billet possible dans un système monétaire connu [p1,p2,p3,…,pn]. (Source: "Reprenons le problème initial : Quel est le nombre minimal de pièces (ou billets) à utiliser pour rendre une somme donnée ? On part d'une liste de pièce ou billet possible dans un système monétaire connu [p1,p2,p3,…,pn]. Exemple : Pour notre système monétaire, la liste sera [0.01")
60. Détail source à réviser : Les sommes inférieures à som obtenables à partir de som sont donc som - p1, som – p2, som – p3,…, som – pn (Source: "Les sommes inférieures à som obtenables à partir de som sont donc som - p1, som – p2, som – p3,…, som – pn")
61. Détail source à réviser : in(nbre [som− pi]) si som > 0 avec i ∈ [1,n] et pi < som} On peut proposer la fonction suivante permettant de rendre la somme som avec les pièces ou billets présents dans la liste en exemple ci-dessus : fonction (Source: "in(nbre [som− pi]) si som > 0 avec i ∈ [1,n] et pi < som} On peut proposer la fonction suivante permettant de rendre la somme som avec les pièces ou billets présents dans la liste en exemple ci-dessus : fonction")
62. Détail source à réviser : celles plus petites que la somme à rendre. Cet algorithme fait bien partie de la méthode "diviser pour régner" puisque nous avons divisé le problème initial puis appliqué un traitement récursif. Nous sommes de plus dans (Source: "celles plus petites que la somme à rendre. Cet algorithme fait bien partie de la méthode "diviser pour régner" puisque nous avons divisé le problème initial puis appliqué un traitement récursif. Nous sommes de plus dans une situation où les sous-problèmes ne sont pas in")
63. Détail source à réviser : 5. Les valeurs inscrites sur les liaisons correspondent aux valeurs des pièces ou billets inclues dans la liste suivante : lst= [1,2,5,10,20,50,100,200,500] (Source: "5. Les valeurs inscrites sur les liaisons correspondent aux valeurs des pièces ou billets inclues dans la liste suivante : lst= [1,2,5,10,20,50,100,200,500]")
64. Détail source à réviser : 5) RM(lst,4) RM(lst,3) RM(lst, 0) RM(lst,3) RM(lst,2) RM(lst,2) RM(lst,1) RM(lst,2) RM(lst,1) RM(lst,1) RM(lst,0) RM(lst,1) RM(lst,0) RM(lst,0) RM(lst,1) RM(lst,0) RM(lst,0) RM(lst,0) RM(lst,0) RM(lst,0) Remarques : • To (Source: "5) RM(lst,4) RM(lst,3) RM(lst, 0) RM(lst,3) RM(lst,2) RM(lst,2) RM(lst,1) RM(lst,2) RM(lst,1) RM(lst,1) RM(lst,0) RM(lst,1) RM(lst,0) RM(lst,0) RM(lst,1) RM(lst,0) RM(lst,0) RM(lst,0) RM(lst,0) RM(lst,0) Remarques : • Tous les cas sont traités")
65. Détail source à réviser : Nous allons donc stocker ces résultats intermédiaires dans une liste de (som + 1) éléments initialisés à 0. 1 2 5 1 1 1 1 1 1 111 2 2 22 2 1 1 2 Terminale Spécialité NSI Algorithmes Voici ici la version Top Down (forme r (Source: "Nous allons donc stocker ces résultats intermédiaires dans une liste de (som + 1) éléments initialisés à 0. 1 2 5 1 1 1 1 1 1 111 2 2 22 2 1 1 2 Terminale Spécialité NSI Algorithmes Voici ici la version Top Down (forme récursive). fonction renduM_TD(lst, som): stock = liste de 0 de taille de lst + 1 retourner renduM_TD_Aux(lst, som, stock) fonction renduM...")
66. Détail source à réviser : mini = som + 1 pour tous les indices i de la liste lst: si lst[i] ≤ som: nbre = 1 + renduM_TD_Aux(lst,som-lst[i],stock) si nbre < mini: mini = nbre stock[som] = mini retourner mini Voici l'arbre obtenu avec la version To (Source: "mini = som + 1 pour tous les indices i de la liste lst: si lst[i] ≤ som: nbre = 1 + renduM_TD_Aux(lst,som-lst[i],stock) si nbre < mini: mini = nbre stock[som] = mini retourner mini Voici l'arbre obtenu avec la version Top Down: RMTD* = renduMonnaie RMTD*(lst, 5) RMTD(lst,4) RMTD(lst,3) RM(lst, 0) RMTD(lst,3) RMTD(lst,2) RMTD(lst,2) RMTD(lst,1) RMTD(lst,1)...")
67. Détail source à réviser : 5) RMTD(lst,4) RMTD(lst,3) RM(lst, 0) RMTD(lst,3) RMTD(lst,2) RMTD(lst,2) RMTD(lst,1) RMTD(lst,1) RMTD(lst,0) RMTD(lst,0) A l'issue du programme, nous obtenons une liste de mémoire cache, qui nous donne, pour toutes les (Source: "5) RMTD(lst,4) RMTD(lst,3) RM(lst, 0) RMTD(lst,3) RMTD(lst,2) RMTD(lst,2) RMTD(lst,1) RMTD(lst,1) RMTD(lst,0) RMTD(lst,0) A l'issue du programme, nous obtenons une liste de mémoire cache, qui nous donne, pour toutes les valeurs inférieures ou égales à som, le nombre minimum de pièces")
68. Détail source à réviser : On peut aisément, à partir des arbres vus précédemment voir exemple que : i 0 1 2 3 4 5 garde[i] 0 1 2 1 2 3 Précisions : Cela correspond au minimum de pièces (Source: "On peut aisément, à partir des arbres vus précédemment voir exemple que : i 0 1 2 3 4 5 garde[i] 0 1 2 1 2 3 Précisions : Cela correspond au minimum de pièces")
69. Détail source à réviser : Pour som = 3, le minimum de pièce est de 2 et on passe par le chemin de la pièce de valeur 2, c'est à dire la 2ème pièce (Source: "Pour som = 3, le minimum de pièce est de 2 et on passe par le chemin de la pièce de valeur 2, c'est à dire la 2ème pièce")
70. Détail source à réviser : Si nous prenons som = 3, puisque garde[3]=1, on doit d'abord rendre puisque la 1ère pièce, celle-ci vaut 1, il nous reste à rendre som-1 = 2, puisque garde[2] = 2, on rend ensuite la 2ème pièce de valeur 2 et il ne reste (Source: "Si nous prenons som = 3, puisque garde[3]=1, on doit d'abord rendre puisque la 1ère pièce, celle-ci vaut 1, il nous reste à rendre som-1 = 2, puisque garde[2] = 2, on rend ensuite la 2ème pièce de valeur 2 et il ne reste plus rien à rendre")
71. Détail source à réviser : e): si som == 0: retourner 0,[] sinon: si stock[som] > 0: retourner stock[som],garde[som] sinon: mini = som + 1 pour tous les indices i de la liste lst: si lst[i] ≤ som: nbre = 1 + (Source: "e): si som == 0: retourner 0,[] sinon: si stock[som] > 0: retourner stock[som],garde[som] sinon: mini = som + 1 pour tous les indices i de la liste lst: si lst[i] ≤ som: nbre = 1 +")
72. Détail source à réviser : Il nous faut bien 3 pièces : 2 pièces de 2 et un billet de 5 (Source: "Il nous faut bien 3 pièces : 2 pièces de 2 et un billet de 5")
73. Détail source à réviser : • La profondeur minimale de la feuille 0 est de 1, il y a une seule possibilité avec le rendu d'une pièce de 5. • Dans certains cas, il arrive qu'une feuille ne soit pas nulle, la valeur retournée par la fonction est dan (Source: "• La profondeur minimale de la feuille 0 est de 1, il y a une seule possibilité avec le rendu d'une pièce de 5. • Dans certains cas, il arrive qu'une feuille ne soit pas nulle, la valeur retournée par la fonction est dans notre cas (som + 1) et cette solution ne sera pas retenue. • On remarque également de nombreux appels redondants, ce qui nous oriente v...")
74. Détail source à réviser : 5. • Dans certains cas, il arrive qu'une feuille ne soit pas nulle, la valeur retournée par la fonction est dans notre cas (som + 1) et cette solution ne sera pas retenue (Source: "5. • Dans certains cas, il arrive qu'une feuille ne soit pas nulle, la valeur retournée par la fonction est dans notre cas (som + 1) et cette solution ne sera pas retenue")
75. Détail source à réviser : Par exemple, pour som = 5, puisque garde[5]=3, on doit d'abord rendre la 3ème pièce, celle-ci vaut 5, il ne reste rien à rendre puisque som-5=0 (Source: "Par exemple, pour som = 5, puisque garde[5]=3, on doit d'abord rendre la 3ème pièce, celle-ci vaut 5, il ne reste rien à rendre puisque som-5=0")
76. Détail source à réviser : 0. 1 2 5 1 1 1 1 1 1 111 2 2 22 2 1 1 2 Terminale Spécialité NSI Algorithmes Voici ici la version Top Down (forme récursive) (Source: "0. 1 2 5 1 1 1 1 1 1 111 2 2 22 2 1 1 2 Terminale Spécialité NSI Algorithmes Voici ici la version Top Down (forme récursive)")
77. Détail source à réviser : Par exemple : Pour som = 5, le minimum de pièce est 1 et sa valeur est 5, ce qui correspond à la 3ème place dans notre système (Source: "Par exemple : Pour som = 5, le minimum de pièce est 1 et sa valeur est 5, ce qui correspond à la 3ème place dans notre système")
78. Détail source à réviser : tique, la programmation dynamique peut prendre deux formes: • Une forme récursive appelée "Top Down" (du haut vers le bas): ➢ On appelle directement la formule de récurrence. ➢ Lors d'un appel récursif, avant d'effectuer (Source: "tique, la programmation dynamique peut prendre deux formes: • Une forme récursive appelée "Top Down" (du haut vers le bas): ➢ On appelle directement la formule de récurrence. ➢ Lors d'un appel récursif, avant d'effectuer le calcul, on vérifie dans la liste de")
79. Détail source à réviser : s intéresse. Terminale Spécialité NSI Algorithmes 2-1- Calcul de la suite de Fibonacci en "Top Down" On va appliquer la forme "Top Down" sur la suite de Fibonacci pour le rang n. Il nous faut donc mémoriser les termes d' (Source: "s intéresse. Terminale Spécialité NSI Algorithmes 2-1- Calcul de la suite de Fibonacci en "Top Down" On va appliquer la forme "Top Down" sur la suite de Fibonacci pour le rang n. Il nous faut donc mémoriser les termes d'indice 0,1,2,…,n. Nous allons donc stock")
80. Détail source à réviser : I Algorithmes 2-1- Calcul de la suite de Fibonacci en "Top Down" On va appliquer la forme "Top Down" sur la suite de Fibonacci pour le rang n. Il nous faut donc mémoriser les termes d'indice 0,1,2,…,n. Nous allons donc s (Source: "I Algorithmes 2-1- Calcul de la suite de Fibonacci en "Top Down" On va appliquer la forme "Top Down" sur la suite de Fibonacci pour le rang n. Il nous faut donc mémoriser les termes d'indice 0,1,2,…,n. Nous allons donc stocker ces résultats intermédiaires dans")
81. Détail source à réviser : bleau sinon de la calculer puis de la retourner . 2-2- Calcul de la suite de Fibonacci en "Buttom Up" On va appliquer la forme "Bottom Up" sur la suite de Fibonacci pour le rang n. On va mémoriser les valeurs de la suite (Source: "bleau sinon de la calculer puis de la retourner . 2-2- Calcul de la suite de Fibonacci en "Buttom Up" On va appliquer la forme "Bottom Up" sur la suite de Fibonacci pour le rang n. On va mémoriser les valeurs de la suite quand n augmente et les stocker au fur e")
82. Détail source à réviser : retourner . 2-2- Calcul de la suite de Fibonacci en "Buttom Up" On va appliquer la forme "Bottom Up" sur la suite de Fibonacci pour le rang n. On va mémoriser les valeurs de la suite quand n augmente et les stocker au fu (Source: "retourner . 2-2- Calcul de la suite de Fibonacci en "Buttom Up" On va appliquer la forme "Bottom Up" sur la suite de Fibonacci pour le rang n. On va mémoriser les valeurs de la suite quand n augmente et les stocker au fur et à mesure dans une liste : fonction")
83. Détail source à réviser : ues : • Tous les cas sont traités. Les algorithmes qui traitent tous les cas sont appelés "force brute". • La profondeur minimale de la feuille 0 est de 1, il y a une seule possibilité avec le rendu d'une pièce de 5. • D (Source: "ues : • Tous les cas sont traités. Les algorithmes qui traitent tous les cas sont appelés "force brute". • La profondeur minimale de la feuille 0 est de 1, il y a une seule possibilité avec le rendu d'une pièce de 5. • Dans certains cas, il arrive qu'une feuille")
84. Détail source à réviser : Les fonctions modifiées deviennent alors les suivantes : fonction renduM_TD(lst, som): stock = liste de 0 de taille de lst + 1 garde = liste de 0 de taille de lst + 1 retourner renduM_TD_Aux(lst, som, stock, garde) fonct (Source: "Les fonctions modifiées deviennent alors les suivantes : fonction renduM_TD(lst, som): stock = liste de 0 de taille de lst + 1 garde = liste de 0 de taille de lst + 1 retourner renduM_TD_Aux(lst, som, stock, garde) fonction renduM_TD_Aux(lst, som, stock, garde): si som == 0: retourner 0,[] sinon: si stock[som] > 0: retourner stock[som],garde[som] sinon: m...")
85. Détail source à réviser : ire cache si ce calcul n'a pas déjà été fait. On parle aussi de technique de mémoïsation (https://fr.wikipedia.org/wiki/Mémoïsation). • Une forme itérative appelée "Bottom Up" (du bas vers le haut): ➢ On résout en premie (Source: "ire cache si ce calcul n'a pas déjà été fait. On parle aussi de technique de mémoïsation (https://fr.wikipedia.org/wiki/Mémoïsation). • Une forme itérative appelée "Bottom Up" (du bas vers le haut): ➢ On résout en premier les problèmes du plus petit niv")
86. Détail source à réviser : Terminale Spécialité NSI Algorithmes 2-1- Calcul de la suite de Fibonacci en "Top Down" On va appliquer la forme "Top Down" sur la suite de Fibonacci pour le rang n (Source: "Terminale Spécialité NSI Algorithmes 2-1- Calcul de la suite de Fibonacci en "Top Down" On va appliquer la forme "Top Down" sur la suite de Fibonacci pour le rang n")
87. Détail source à réviser : 2-2- Calcul de la suite de Fibonacci en "Buttom Up" On va appliquer la forme "Bottom Up" sur la suite de Fibonacci pour le rang n (Source: "2-2- Calcul de la suite de Fibonacci en "Buttom Up" On va appliquer la forme "Bottom Up" sur la suite de Fibonacci pour le rang n")
88. Détail source à réviser : On va mémoriser les valeurs de la suite quand n augmente et les stocker au fur et à mesure dans une liste : fonction fiboBU(n): stock = liste de 0 de taille n+1 stock[1] = 1 pour les indices i de 2 à n+1: stock[i] = stoc (Source: "On va mémoriser les valeurs de la suite quand n augmente et les stocker au fur et à mesure dans une liste : fonction fiboBU(n): stock = liste de 0 de taille n+1 stock[1] = 1 pour les indices i de 2 à n+1: stock[i] = stock[i-1] + stock[i-2] retourner stock[n] Précision : Ici, il y a pas d'appel récursif mais la formule de récurrence de la suite est sous la...")
89. Détail source à réviser : Dans notre exemple, on a stock qui correspond au tableau suivant : i 0 1 2 3 4 5 stock[i] 0 1 1 2 2 1 Pour être complet, il nous reste à donner le nombre d'exemplaire de chaque 1 2 5 1 1 1 2 2 2 1 Terminale Spécialité NS (Source: "Dans notre exemple, on a stock qui correspond au tableau suivant : i 0 1 2 3 4 5 stock[i] 0 1 1 2 2 1 Pour être complet, il nous reste à donner le nombre d'exemplaire de chaque 1 2 5 1 1 1 2 2 2 1 Terminale Spécialité NSI Algorithmes pièce ou billet dont il faut se servir pour rendre som")
90. Détail source à réviser : Il nous faut alors modifier les fonctions ci-dessus en faisant intervenir un nouveau tableau qu'on appellera "garde" dont le contenu est égal au numéro de la pièce utilisée (Source: "Il nous faut alors modifier les fonctions ci-dessus en faisant intervenir un nouveau tableau qu'on appellera "garde" dont le contenu est égal au numéro de la pièce utilisée")
91. Détail source à réviser : On peut alors retrouver un même sous-problème dans des appels récursifs différents, et donc être amené à le résoudre plusieurs fois, ce qui ressemble fort à du gaspillage de temps et de mémoire (Source: "On peut alors retrouver un même sous-problème dans des appels récursifs différents, et donc être amené à le résoudre plusieurs fois, ce qui ressemble fort à du gaspillage de temps et de mémoire")
92. Détail source à réviser : La mémorisation des solutions des sous-problèmes est une sorte de mémoire cache implémentée sous forme de tableau ou de liste (Source: "La mémorisation des solutions des sous-problèmes est une sorte de mémoire cache implémentée sous forme de tableau ou de liste")
93. Détail source à réviser : Nous allons donc stocker ces résultats intermédiaires dans une liste de (n+1) éléments initialisés à 0 : fonction fiboTD(n): stock = liste de 0 de taille n+1 stock[1] = 1 retourner fiboTDAux fonction fiboTDAux(n, stock): (Source: "Nous allons donc stocker ces résultats intermédiaires dans une liste de (n+1) éléments initialisés à 0 : fonction fiboTD(n): stock = liste de 0 de taille n+1 stock[1] = 1 retourner fiboTDAux fonction fiboTDAux(n, stock): si n == 0 ou n == 1: retourner n sinon: si stock[n] > 0: retourner stock[n] sinon: stock[n] = fiboTDAux(n-1, stock) + fiboTDAux(n-2, sto...")
94. Détail source à réviser : On peut alors présenter cette formule de récurrence : nbre[som ]={0 si som = 0 1+min(nbre [som− pi]) si som > 0 avec i ∈ [1,n] et pi < som} On peut proposer la fonction suivante permettant de rendre la somme som avec les (Source: "On peut alors présenter cette formule de récurrence : nbre[som ]={0 si som = 0 1+min(nbre [som− pi]) si som > 0 avec i ∈ [1,n] et pi < som} On peut proposer la fonction suivante permettant de rendre la somme som avec les pièces ou billets présents dans la liste en exemple ci-dessus : fonction renduMonnaie(lst, som): si som == 0: retourner 0 sinon: mini =...")
95. Détail source à réviser : fonction renduM_TD(lst, som): stock = liste de 0 de taille de lst + 1 retourner renduM_TD_Aux(lst, som, stock) fonction renduM_TD_Aux(lst, som, stock): si som == 0: retourner 0 sinon: si stock[som] > 0: retourner stock[s (Source: "fonction renduM_TD(lst, som): stock = liste de 0 de taille de lst + 1 retourner renduM_TD_Aux(lst, som, stock) fonction renduM_TD_Aux(lst, som, stock): si som == 0: retourner 0 sinon: si stock[som] > 0: retourner stock[som] sinon: mini = som + 1 pour tous les indices i de la liste lst: si lst[i] ≤ som: nbre = 1 + renduM_TD_Aux(lst,som-ls")
96. Détail source à réviser : Terminale Spécialité NSI Algorithmes Chapitre 15 – La programmation dynamique Introduction : Nous allons aborder la deuxième stratégie d'optimisation de programme : la programmation dynamique qui permet d'éviter de faire (Source: "Terminale Spécialité NSI Algorithmes Chapitre 15 – La programmation dynamique Introduction : Nous allons aborder la deuxième stratégie d'optimisation de programme : la programmation dynamique qui permet d'éviter de faire plusieurs fois les mêmes calculs")

📊 Tableaux de Synthèse

Comparaison des formes de programmation dynamique

Forme	Approche	Avantages
Top Down	Récursive avec mémoïsation	Facile à implémenter, évite la redondance
Bottom Up	Itérative, progresse du plus petit problème au plus grand	Efficace en mémoire, évite la récursion

⚠️ Pièges & Confusions Fréquentes

1. Confusion entre mémoïsation et programmation dynamique
2. Oublier de remplir la mémoire cache, entraînant des recalculs
3. Utiliser la récursion sans mémoïsation, causant une explosion du nombre d'appels
4. Ne pas initialiser correctement la mémoire cache, menant à des résultats incorrects
5. Confondre la forme Top Down et Bottom Up dans leur implémentation

✅ Checklist Examen

1. Comprendre la redondance dans le calcul récursif de Fibonacci
2. Maîtriser le principe de la mémoïsation et la mémoire cache
3. Savoir différencier Top Down et Bottom Up
4. Savoir formuler récursivement le problème du rendu de monnaie
5. Analyser les appels récursifs redondants dans le rendu de monnaie
6. Utiliser la programmation dynamique pour optimiser le rendu de monnaie
7. Construire la mémoire cache pour le rendu de monnaie
8. Déterminer le nombre minimal de pièces et leur composition
9. Implémenter l'algorithme modifié pour retourner la liste des pièces
10. Interpréter un exemple pratique de rendu de monnaie optimal