Introduction

I. Paradigmes algorithmiques⚓︎

Algorithme glouton : construit une solution de manière incrémentale, en optimisant un critère de manière locale.
Diviser pour régner : divise un problème en sous-problèmes indépendants (qui ne se chevauchent pas), résout chaque sous-problème, et combine les solutions des sous-problèmes pour former une solution du problème initial.
👉 Programmation dynamique : divise un problème en sous-problèmes qui sont non indépendants (qui se chevauchent), et cherche (et stocke) des solutions de sous-problèmes de plus en plus grands

Bref historique⚓︎

Programmation dynamique : paradigme développé par Richard Bellman en 1953 chez RAND Corporation.
« Programmation » = planification
Technique de conception d'algorithme très générale et performante.
Permet de résoudre de nombreux problèmes d'optimisation.

Pourquoi « programmation dynamique » ?

« The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was secretary of Defense, and he actually had a pathological fear and hatred of the word ‘research’. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term ‘research’ in his presence. You can imagine how he felt, then, about the term ‘mathematical’. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? »

Richard Bellman (1984)

II. Revisitons Fibonacci...⚓︎

1. Les nombres de Fibonacci⚓︎

Vous pouvez regarder le début de cet article :

Suite de Fibonacci

Soit \(F_n\) = nombre de lapins au mois n

\(F_1 = 1\)
\(F_2 = 1\)
\(F_n = F_{n-1} + F_{n-2}\)

Ce sont les nombres de Fibonacci : \(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,\dots\)

👉 Ils croissent très vite : \(F_{30} = 832040\)

Le nombre \(\varphi\) est appelé le nombre d'or : \(\varphi = \dfrac{1+ \sqrt{5}}{2}\).

En fait, si \(n\) est grand on a : \(F_n \approx \dfrac {\varphi ^{n}}{\sqrt{5} }\)

😢 Nous avons donc une croissance exponentielle.

2. La suite de Fibonacci : comment calculer les termes (méthode récursive naïve) ?⚓︎

Faire l'exercice suivant.

Ne pas oublier de suivre le lien de visualisation des appels proposé dans la solution.

Suite de Fibonacci - 1

3. La suite de Fibonacci en programmation dynamique⚓︎

Suite de Fibonacci - 2

4. Visualiser les temps d'exécution : programmation récursive naïve / programmation récursive dynamique⚓︎

Le code des fonctions des deux exercices précédents ont été mis en code caché.

Nous allons visualiser les temps de calcul des premiers termes par une fonction récursive naïve, et une fonction récursive avec programmation dynamique.

Votre figure

Votre tracé sera ici

5. La suite de Fibonacci en itératif de bas en haut (approche Bottom-up)⚓︎

Faire l'exercice suivant. Il ne s'agit pas de programmation dynamique, mais il est intéressant d'étudier cette méthode pour comparer son temps d'exécution par rapport à l'approche récursive dynamique.

Suite de Fibonacci en itératif (2)

6. Visualiser les temps d'exécution : programmation dynamique / programmation itérative bottom-up⚓︎

Le code des fonctions par programmation dynamique et par programmation itérative bottom-up ont été mis dans le code caché.

Nous allons visualiser les temps de calcul pour de très grandes valeurs de n. En effet ces méthodes sont très efficaces, et ce n'était pas possible à réaliser avec la programmation récursive naïve.

Votre figure

Votre tracé sera ici

III. Crédits⚓︎

Auteurs : Denis Quenton, Jean-Louis Thirot, Mireille Coilhac