Cours / exemples

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 ?⚓︎

La suite de Fibonacci est une suite numérique définie par :
\(u_0 = 1\) et \(u_1=1\) et pour tout entier \(n>1\), \(u_n=u_{n-1}+u_{n-2}\).

Pour calculer le terme de rang \(n\), on peut utiliser cette définition par récurrence, pour concevoir un programme récursif.

Version récursive

Tester dans la console fibonacci(6), puis fibonacci(10). Que constatez-vous ?

Solution

fibonacci(10) est déjà très long à calculer.

Les appels récursifs

Pour calculer le terme de rang 6, il faut calculer celui de rang 5 et celui de rang 4
Pour calculer le terme de rang 5, il faut calculer celui de rang 4 et celui de rang 3
Pour calculer le terme de rang 4, il faut calculer celui de rang 3 et celui de rang 2
Pour calculer le terme de rang 3, il faut calculer celui de rang 2 et celui de rang 1
Pour calculer le terme de rang 2, il faut calculer celui de rang 1 et celui de rang 0.

On remarque que \(u_4\) est calculé deux fois (une fois pour \(u_6\) et une fois pour \(u_5\)) , \(u_3\) est calculé pour chaque calcul de \(u_5\) et \(u_4\) (donc trois fois en tout) et que \(u_2\) est calculé 5 fois en tout. On obtient même 13 appels à \(u_0\) ou \(u_1\). (On remarque d'ailleurs que \(u_6=13\))

On peut représenter cela avec l'arbre des appels :

flowchart TD
A0 --> A1 & A22
A1 --> A2 & A3
A2 --> A4 & A5
A4 --> A6 & A7
A6 --> A8 & A9
A3 --> A10 & A11
A5 --> A14 & A15
A10 --> A12 & A13

A22 --> A24 & A25
A24 --> A26 & A27
A26 --> A28 & A29
A25 --> A214 & A215


A0(("F(6)"))
A1(("F(5)"))
A2(("F(4)"))
A3(("F(3)"))
A4(("F(3)"))
A5(("F(2)"))
A6(("F(2)"))
A7(("F(1)"))
A8(("F(1)"))
A9(("F(0)"))
A10(("F(2)"))
A11(("F(1)"))
A12(("F(1)"))
A13(("F(0)"))
A14(("F(1)"))
A15(("F(0)"))

A22(("F(4)"))
A24(("F(3)"))
A25(("F(2)"))
A26(("F(2)"))
A27(("F(1)"))
A28(("F(1)"))
A29(("F(0)"))
A214(("F(1)"))
A215(("F(0)"))

Plus on augmente le numéro de rang, plus il y a des calculs qui sont répétés et refaits.

3. A vous de jouer⚓︎

A vous de jouer

Après avoir téléchargé le fichier, vous pourrez le lire à partir de Basthon

🌐 TD à télécharger : Fichier fibonacci_sujet.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

⏳ Ne lisez pas trop vite la correction ....

🌐 Correction : Fichier fibonacci_corr.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

III. Crédits⚓︎

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