Programmation dynamique

Pr. A. Mirrane

[email protected]

Décembre 2024

CPGE (SPÉ) Programmation dynamique Décembre 2024 1 / 20

Aperçu général

1 Introduction

2 Stratégie gloutonne vs Programmation dynamique

3 Méthode Top-down

4 Méthode Bottom-up

5 Problèmes
Nombre de façons d’écrire un nombre
Problème de sac à dos

CPGE (SPÉ) Programmation dynamique Décembre 2024 2 / 20

Introduction

■ Problème

Considérons la suite de Fibonacci :

(
1 si n < 2
Fn =
Fn−1 + Fn−2 sinon

Écrire une fonction récursive fibo(n) qui donne la valeur de Fn .

Afficher séparément les valeur de F30 , F37 , F38 .
Qu’avez-vous remarqué ?
C’est qui la complexité de cette fonctions ?

CPGE (SPÉ) Programmation dynamique Décembre 2024 3 / 20

Introduction
➜ Solution naïve

Une solution simple consiste à implémenter la fonction de manière récursive :

1 def fibo ( n ) :
2 if n < 2: return 1
3 return fibo (n -1) + fibo (n -2)

On remarque que fibo(30) s’exécute rapidement, mais fibo(38) prend

beaucoup de temps. On peut déduire que la complexité est assez élevée :

T (n) = O(1) + T (n − 1) + T (n − 2)

O(1) + 2T (n − 2) ≤ T (n) ≤ O(1) + 2T (n − 1)

O(2n ) ≤ T (n) ≤ O(2n )

Donc T (n) = O(2n )

CPGE (SPÉ) Programmation dynamique Décembre 2024 4 / 20
Introduction
➜ Solution naïve

La Complexité est élevée car la fonction répète des calculs.

Soit l’arbre des appels récursive pour fibo(6) :

On remarque que plusieurs appels se répètes. par exemple, le programme

calcule la valeur de fibo(3) trois fois. ce qui est un problème.
CPGE (SPÉ) Programmation dynamique Décembre 2024 5 / 20
Stratégie gloutonne

■ Critères

Pour appliqué une stratégie glouton on a besoin de deux chose :

Un problème d’optimisation (trouver le maximum ou le minimum)
Des choix á faire (la solution utilise seulement un sous-ensemble de
l’ensemble original des données)

■ Caractéristiques

Résoudre un problème le plus rapidement possible en essayant de

trouver la plus petite solution possible.
Les algorithmes gloutons se concentrent sur le meilleur choix local à
chaque point de décision.
Il n’est pas garanti qu’une solution optimale soit obtenue

CPGE (SPÉ) Programmation dynamique Décembre 2024 6 / 20

Programmation dynamique

Definition
La programmation dynamique est une méthode utilisé pour éviter la
répétition des calcul dans une fonction souvent récursive.
Généralement, elle utilise une méthode pour mémoriser les résultats déjà
calculer.

■ Critères

Pour appliqué la programmation dynamique on a besoin de deux chose :

Une fonction récursive.
une répétition des calculs dans les appels récursive.

CPGE (SPÉ) Programmation dynamique Décembre 2024 7 / 20

Méthode Top-down
Revenons à la fonction fibo(n). On peut optimiser la solution précédente en évitant
les calculs redondants, avec l’aide d’un dictionnaire memoire. Où memoire[i] va
contenir la valeur de Fi . Cette méthode est appelé Top-down.

1 memoire = {}
2 def fiboTD ( n ) :
3 if n < 2: return 1
4 if n not in memoire :
5 memoire [ n ] = fiboTD (n -1) + fiboTD (n -2)
6 return memoire
Ici, le dictionnaire memoire est une variable globale. On peut aussi déclarer ce
dictionnaire comme paramètre de la fonction.

1 def fiboTD (n , memoire ={}) :

2 if n < 2: return 1
3 if n not in memoire :
4 memoire [ n ] = fiboTD (n -1 , memoire ) + fiboTD (n -2 , memoire )
5 return memoire

CPGE (SPÉ) Programmation dynamique Décembre 2024 8 / 20

Méthode Top-down

Maintenant l’arbre des appels récursive est comme suit :

La complexité de fiboTD(n) est :

TTD (n) = O(1) + TTD (n − 1) + TTD (n − 2)

= O(1) + TTD (n − 1) + O(1)
= O(n)

la complexité de fiboTD(n-2) est O(1).

Car fiboTD(n-1) va s’exécuter avant
fiboTD(n-2).
Et pour terminer le calcul de Fn−1 On
doit déjà avoir calculer Fn−2 .
Donc a l’instant où fiboTD(n-2) va
s’exécuter la valeur de Fn−2 est déjà
stocker dans la mémoire.
CPGE (SPÉ) Programmation dynamique Décembre 2024 9 / 20
Méthode Top-down
■ Mémoïsation (Top-down)
Résoudre le problème principal récursivement.
Une fois qu’un sous-problème est résolu, il est mis en cache afin que nous
n’ayons pas besoin de le résoudre à nouveau en cas de besoin.
■ Application de la méthode

1 def fonction_naive ( indices ) :

2 cases de base
3 calculs
4 return valeur ( s )

1 memoire = {}
2 def fonction_naive ( indices ) :
3 cases de base
4 if indices not in memoire :
5 calculs
6 memoire [ indices ] = valeur ( s )
7 return memoire [ indices ]
CPGE (SPÉ) Programmation dynamique Décembre 2024 10 / 20
Méthode Bottom-up

■ Tabulation (Bottom-up)

La tabulation est une méthode itérative, à l’opposé de l’approche

Top-Down et évite la récursivité.
Résoudre d’abord tous les sous-problèmes.
Cela se fait généralement en remplissant un tableau à n dimensions. Sur
la base des résultats du tableau, la solution au problème
principal/d’origine est ensuite calculée.

1 def fibonacci ( n ) :
2 Fib = [1 , 1]
3 for i in range (2 , n ) :
4 Fib . append ( Fib [i -1] + Fib [i -2])
5 return Fib [ -1]

CPGE (SPÉ) Programmation dynamique Décembre 2024 11 / 20

Nombre de façons d’écrire un nombre

■ Problème
Étant donné n, trouver le nombre de façons différentes d’écrire n comme la
somme de 1, 3, 4.

➜ Exemple
Pour n = 5, la réponse est 6.

5=1+1+1+1+1
=1+1+3
=1+3+1
=3+1+1
=1+4
=4+1

CPGE (SPÉ) Programmation dynamique Décembre 2024 12 / 20

Nombre de façons d’écrire un nombre

■ Caractériser la structure d’une solution optimale

Soit Fn le nombre de façons d’écrire n comme la somme de 1, 3, 4.

n = x1 + x2 + ... + xm (1)
Soit (1) une des façons décrire n comme somme de 1, 3, 4. Donc les valeur
possible de xm sont soit 1, soit 3, soit 4.

n = x1 + x2 + ... + 1 = (n − 1) + 1
= x1 + x2 + ... + 3 = (n − 3) + 3
= x1 + x2 + ... + 4 = (n − 4) + 4

Si xm = 1, La somme des autres termes doit être égale à n-1.

Ainsi, le nombre de sommes qui se terminent par xm = 1 est égal à Fn−1
Prendre en compte les autres cas (xm = 3, xm = 4)
CPGE (SPÉ) Programmation dynamique Décembre 2024 13 / 20
Nombre de façons d’écrire un nombre

■ Définir la formule récursive

Fn = Fn−1 + Fn−3 + Fn−4

Les cas de bases :
➔ Fn = 0 pour n < 0.
➔ F0 = F1 = F2 = 1
➔ F3 = 3

CPGE (SPÉ) Programmation dynamique Décembre 2024 14 / 20

Nombre de façons d’écrire un nombre

■ Solution récursive naïve

1 def F ( n ) :
2 if n < 0:
3 return 0
4 elif n < 3:
5 return 1
6 elif n == 3:
7 return 2
8 else :
9 return F (n -1) + F (n -3) + F (n -4)

CPGE (SPÉ) Programmation dynamique Décembre 2024 15 / 20

Nombre de façons d’écrire un nombre

■ Solution récursive naïve

on remarque qu’on répète des calcul dans l’arbre des appels récursives. Donc
en peut appliquer les méthodes de programmation dynamique.
CPGE (SPÉ) Programmation dynamique Décembre 2024 16 / 20
Nombre de façons d’écrire un nombre

■ Solution récursive Top-Down

1 memoire = {}
2 def FTD ( n ) :
3 if n < 0:
4 return 0
5 elif n < 3:
6 return 1
7 elif n == 3:
8 return 2
9 if n not in memoire :
10 memoire [ n ] = FTD (n -1) + FTD (n -3) + FTD (n -4)
11 return memoire [ n ]

CPGE (SPÉ) Programmation dynamique Décembre 2024 17 / 20

Nombre de façons d’écrire un nombre

■ Solution itérative Bottom-up

1 def FBU ( n ) :
2 F = [1 , 1 , 1 , 2]
3 for i in range (4 , n ) :
4 F . append ( F [i -1] + F [i -3] + F [i -4])
5 return F [ n ]

CPGE (SPÉ) Programmation dynamique Décembre 2024 18 / 20

Problème de sac à dos

■ Problème

Étant donné plusieurs objets possédant chacun un poids (pi ) et une valeur (vi )
et étant donné un poids maximum pour le sac (T), quels objets faut-il mettre
dans le sac de manière à maximiser la valeur totale sans dépasser le poids
maximal autorisé pour le sac ?

X
Profit = max( vi )

X
T ≥ pi

CPGE (SPÉ) Programmation dynamique Décembre 2024 19 / 20

Problème de sac à dos

■ Caractériser la structure d’une solution optimale

Soit Dij Le profit gagné pour remplir le poids j en considérant les éléments de 1
à i.
Les cas de base :

Si pi > j, Ignorer cet article, donc Dij = Di−1,j .

Sinon, on a deux choix :

➔ prendre l’article i, donc Dij = vi + Di−1,j−pi .
➔ ignorer l’article i, donc Dij = Di−1,j .
On veut prendre le choix qui va maximiser notre profit, donc :

Dij = max{Di−1,j , vi + Di−1,j−pi }

CPGE (SPÉ) Programmation dynamique Décembre 2024 20 / 20