Chapitre 16 : Programmation dynamique.

Introduction :

La programmation dynamique repose sur une idée simple mais puissante : pourquoi recalculer un résultat si on l'a déjà trouvé ?

En décomposant un problème complexe en sous-problèmes plus simples, on peut mémoriser les solutions déjà obtenues et les réutiliser. Cela permet d'éviter des calculs redondants et d'améliorer l'efficacité des algorithmes.

1. Définition:

En informatique, la programmation dynamique est une méthode algorithmique pour résoudre des problèmes d'optimisation. Le concept a été introduit au début des années 1950 par Richard Bellman.

La programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires

La programmation dynamique est souvent associée à une programmation récursive stockant les résultats précédents dans une mémoire.

Lien wikipedia

2. Activité:

On considère la suite de Fibonacci définie à l'aide d'une suite \(F\) définie ainsi :

\(F(0)=0\)
\(F(1)=1\)
Pour tout \(n\) entier supérieur ou égal à deux : \(F(n)=F(n-1)+F(n-2)\)

Programmer la fonction fibo_itera qui prend en paramètre un integer n et qui renvoie la valeur de \(F(n)\) à l'aide d'une programmation itérative.
Programmer la fonction fibo_recur qui prend en paramètre un integer n et qui renvoie la valeur de \(F(n)\) à l'aide d'une programmation récursive.
Programmer la fonction fibo_recur_dyna qui prend en paramètre un integer n et qui renvoie la valeur de \(F(n)\) à l'aide d'une programmation récursive et dynamique.
Programmer la fonction fibo_itera_dyna qui prend en paramètre un integer n et qui renvoie la valeur de \(F(n)\) à l'aide d'une programmation itérative et dynamique.

3. Problème du rendu de monnaie:

Le problème du rendu de monnaie est un exercice "classique et populaire" en informatique car il permet de voir différentes programmations (comme l'est la suite de Fibonacci...).

On considère un système de monnaie.

La question est la suivante : quel est le nombre minimum de pièces à rendre pour un montant donné?

4. Activité:

On considère un tuple P=(200,100,50,20,10,5,2,1) contenant les pièces disponibles.

Programmer rendu qui prend en paramètre un integer n et qui renvoie le nombre de pièce minimal à l'aide d'un algorithme glouton itératif.
Programmer rendu_recur qui prend en paramètre un integer n et qui renvoie le nombre de pièce minimal à l'aide d'un algorithme récursif.
Programmer rendu_recur_dyna qui prend en paramètre un integer n et qui renvoie le nombre de pièce minimal à l'aide d'un algorithme récursif et dynamique.