Différences

Ci-dessous, les différences entre deux révisions de la page.

--- nsi:terminales:dynamique:programmation_dynamique [2023/02/03 18:29] – supprimée - modification externe (Unknown date) 127.0.0.1
+++ nsi:terminales:dynamique:programmation_dynamique [2023/02/03 18:29] (Version actuelle) – ↷ Liens modifiés en raison d'un déplacement. goupillwiki
@@ Ligne 1: / Ligne 1: @@
+====== Programmation dynamique ======
+===== Origine du nom =====
+{{ :nsi:terminales:dynamique:bellman.jpeg?nolink&200|Richard Bellman (1920-1984)}}
+Concept créé  au début des années 1950 par [[https://fr.wikipedia.org/wiki/Richard_Bellman|Richard Bellman]]. Il explique lui-même que la société pour laquelle il travaillait dépendait des décisions d'un secrétaire à la défense, donc un représentant de l'armée, qui ne voulait pas entendre parler de recherche ou de mathématiques. Richard Bellman a donc choisi un terme un peu vague, qui pouvait, en forçant un peu, décrire ce qu'il faisait, mais qui surtout faisait plaisir au secrétaire à la défense un peu obtus. C'est de là que vient le nom //programmation dynamique// -- l'idée est que le mot //dynamique// parle bien à un militaire.
+<WRAP important>C'est ce qu'a raconté Bellman des années plus tard. On n'est pas obligé de le croire ;-) Il n'est pas rare qu'on enjolive un peu les choses après coup et qu'on se donne le beau rôle !</WRAP>
+===== Principe =====
+<WRAP box>
+Il s'agit de :
+  * **découper** un problème en sous-problèmes,
+  * puis à résoudre les sous-problèmes **du plus petit au plus grand** en **conservant les résultats** intermédiaires.
+</WRAP>
+<WRAP Important>Dans le cas de [[..:diviser_pour_regner|diviser pour régner]] nous avions déjà cette notion de découper un problème en sous-problèmes mais ici nous insistons sur l'ordre -- //plus petit au plus grand// -- et sur la conservation des résultats intermédiaires.</WRAP>
+===== Exemple de la suite de Fibonacci =====
+La suite de Fibonacci est définie par:
+  * $F(0) = 1$,
+  * $F(1) = 1$,
+  * pour $n \geqslant 2$, $F(n) = F(n-1) + F(n-2)$.
+==== Approche naïve ====
+On pourrait -- comme on l'a fait dans [[..:recursivite:cours|le cours sur la récursivité]] -- programmer en Python :
+<code python linenums>
+# version naïve
+def F(n):
+    if n <= 1:
+        return 1
+    return F(n-1) + F(n-2)
+</code>
+C'est simple et cela suit de près la définition mathématique de la suite.
+Supposons que l'on veuille calculer $F(5)$.
+{{ :nsi:terminales:dynamique:fibo.png?nolink&400 |}}
+Cet arbre représente le calcul et les appels récursifs.
+  * Pour calculer $F(5)$ il faut calculer $F(4)$ et $F(3)$.
+  * $F(4)$ nécessite lui-même le calcul de $F(3)$ et $F(2)$.
+  * Et ainsi de suite...
+On voit que cette façon d'organiser le calcul est peu performante puisque l'on va calculer plusieurs fois la même chose. Par exemple, on calcul 5 fois $F(1)$ et 3 fois $F(2)$ !
+Imaginez la perte de temps pour calculer $F(1\,000)$  ou $F(1\,000\,000)$...
+Il faudrait donc organiser notre suite de calculs pour ne pas faire plusieurs fois le même calcul. C'est tout le principe de la programmation dynamique.
+<WRAP tip>Notre programme naïf peut suffire selon les utilisations que l'on en a. On n'a pas toujours besoin d'optimiser et il n'est pas utile de passer une heure à réfléchir pour économiser 5 minutes d'exécution sur un programme qui ne servira qu'une ou deux fois !</WRAP>
+==== Approche programmation dynamique ====
+On sait que le calcul de $F(n)$ nécessitera de calculer tous les $F(i)$ avec $0 \leqslant i < n$. Le calcul de ces $F(i)$ sont autant de sous-problèmes que l'on va traiter dans le **sens croissant** en **sauvegardant les réponses**.
+<code python linenums>
+# version dynamique
+def F(n):
+    tab_F = [1, 1] # on sait que F(0) = F(1) = 1
+    for i in range(2, n+1):
+        F_i = tab_F[i-1] + tab_F[i-2]
+        tab_F.append(F_i)
+    return tab_F[-1] # renvoie le dernier calculé
+</code>
+Dans cette fonction on augmente la taille du tableau (''append'') à chaque itération de la boucle ''for''. Ce genre d'opération est long. On pourrait améliorer les choses en créant dès le début un tableau avec la bonne taille.
+<code python linenums>
+# version dynamique améliorée
+def F(n):
+    tab_F = [0]*(n+1) # tableau de n+1 éléments, tous à 0
+    tab_F[0] = 1 # on sait que F(0) = 1
+    tab_F[1] = 1 # on sait que F(1) = 1
+    for i in range(2, n+1):
+        tab_F[i] = tab_F[i-1] + tab_F[i-2] # plus besoin de append
+    return tab_F[-1] # renvoie le dernier calculé
+</code>
+L'exécution de cette version est plus rapide.
+<WRAP tip>Dans le cas dynamique, on montre explicitement que l'on mémorise les résultats intermédiaires dans le tableau. Mais cela n'occasionne pas un coût en mémoire supérieur au cas naïf car dans le cas naïf, lors de l'appel récursif, il y a aussi une mémorisation de toute la chaîne d'appels ce qui au final ne vaut pas mieux.</WRAP>
+<WRAP box>**Test :** Essayez les deux approches -- récursif et dynamique -- et constatez que la version récursive est très rapidement dépassée.
+  * avec ''n = 30'', met un temps très long,
+  * avec ''n = 1000'', elle n'aboutit pas -- ''RecursionError'',
+  * la version dynamique n'a pas ce problème.
+</WRAP>
+<WRAP tip>Passé une certaine valeur, $F(n)$ devient très grand et dépasse les capacité d'un ''int'' normal -- 4 octets, jusque 2 millions environ. Alors Python passe dans un mode spécial d'entiers de taille arbitraire -- de façon transparente, c'est à dire que nous n'avons rien à faire. Ce comportement à tout de même deux conséquences :
+  * les calculs deviennent beaucoup plus longs,
+  * dans la version dynamique améliorée, nous avions préparé un tableau pour contenir les valeurs des $F(n)$ intermédiaires avec l'idée qu'il valait mieux réserver tout de suite en mémoire la place utile à nos calculs.\\ Mais quand les entiers deviennent grands, ils prennent plus de place, une place supérieure à celle prévue initialement si bien qu'on finit par devoir agrandir le tableau initialement créé...
+</WRAP>
+==== Comparaison des coûts temporels ====
+== Version récurrente ==
+On va noter $C_{rec}(n)$ on évaluation grossière du nombre d'instructions nécessaires du calcul de $F(n)$ avec la version récurrente.
+  * On peut poser que $F(0)$ et $F(1)$ sont calculés en une instruction, donc $C_{rec}(0) = C_{rec}(1) = 1$.
+  * Pour $n \geqslant 2$, $F(n) = F(n-1) + F(n-2)$, on peut donc estimer que le coût du calcul de $F(n)$ est égal au coût du calcul de $F(n-1)$ plus le coût de calcul de $F(n-2)$ plus l'addition donc $C_{rec}(n) = C_{rec}(n-1) + C_{rec}(n-2) + 1$.
+On peut prouver que, si $a = \frac{1 - \sqrt{5}}{2} \simeq -0,6$ et $b = \frac{1 + \sqrt{5}}{2} \simeq 1,6$ alors $C_{rec}(n) = \frac{2}{\sqrt{5}} \cdot \left(b^{n+1} - a^{n+1}\right) - 1$.
+Donc pour $n \to +\infty$, $C_{req}(n) \simeq 1,4 \times 1,6^n$. C'est une croissance exponentielle.
+<WRAP important>Ces calculs sont extrêmement grossiers. L'important ici est que la dépendance est en $q^n$ avec $q > 1$.</WRAP>
+== Version dynamique ==
+Dans sa version dynamique, on peut dire que le calcule de $F(n)$ nécessite
+  * la lecture de $F(n-1)$ dans le tableau,
+  * la lecture de $F(n-2)$ dans le tableau,
+  * le calcul de la somme,
+  * l'écriture de $F(n)$ dans le tableau.
+Donc $C_{dyn}(n) \simeq 4\,n$.
+<WRAP important>Ces calculs sont extrêmement grossiers. Combien de temps faut-il pour faire une lecture tableau ? Une écriture ? calculer une somme... On pourrait tout aussi bien avoir $C_{dyn}(n) \simeq 10\,n$ ou $C_{dyn}(n) \simeq 20\,n$... L'important ici est que la dépendance est en $n$.</WRAP>
+== Comparaison ==
+Puisque la version récurrente est en $1,6^n$ et la version dynamique en $n$, quels que soient les coefficients, quand $n \nearrow$, le temps nécessaire pour la version récurrente devient beaucoup plus grand. Donc avec des **problèmes de grande taille**, l'approche dynamique sera avantageuse.