Programme

Capacités attendues et commentaires

Capacités attendues

Utiliser la programmation dynamique pour écrire un algorithme.

Commentaires

Les exemples de l’alignement de séquences ou du rendu de monnaie peuvent être présentés.
La discussion sur le coût en mémoire peut être développée.

Programmation dynamique

Fibonnacci naif

Définition

La suite de Fibonacci est définie par :

$F(0) = 0$
$F(1) = 1$
$F(n) = F(n-1) + F(n-2)$

Implémentation naïve

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

Arbre d’appels

fibonacci(4)
    fibonacci(3)
        fibonacci(2)
            fibonacci(1)
            fibonacci(0)
        fibonacci(1)
    fibonacci(2)
        fibonacci(1)
        fibonacci(0)

Problème

Énormément d’appels
La complexité de cet algorithme est exponentielle (en $O(\varphi^n)$ avec $\varphi \approx 1.618$ ). Pour $n = 40$ , il faut $3^{8}$ appels récursifs
Très lent et coûteux en temps. Comment faire mieux ?

Fibonnacci avec mémoïsation

Mémoïsation

On va stocker les résultats des appels récursifs pour ne pas les recalculer
On va utiliser un dictionnaire pour stocker les résultats
Tant qu’on y est, on inclut les cas de base dans le dictionnaire

def fibm(n, memo=None):
    if memo is None:
        memo = {0: 0, 1: 1}
    if n not in memo:
        memo[n] = fibm(n-1, memo) + fibm(n-2, memo)
    return memo[n]

Complexité avec mémoïsation

La complexité de cet algorithme est linéaire (en $O(n)$ )
Pour $n = 40$ , il faut $40$ appels récursifs
Beaucoup plus rapide que l’implémentation naïve

Programmation dynamique

Concept

Principe

La programmation dynamique s’applique aux problèmes qui vérifient deux propriétés :

Sous-structure optimale : la solution optimale du problème se construit à partir des solutions optimales de ses sous-problèmes.
Sous-problèmes répétés : les mêmes sous-problèmes apparaissent plusieurs fois lors de la résolution (comme on l’a vu avec Fibonacci).

La méthode consiste à résoudre chaque sous-problème une seule fois et à mémoriser son résultat pour ne pas le recalculer.

Deux approches

Descendante (top-down) : on part du problème de taille $n$ , on descend récursivement, et on mémorise les résultats au fur et à mesure — c’est la mémoïsation.
Ascendante (bottom-up) : on part des cas de base, on remplit un tableau dans l’ordre croissant des sous-problèmes, sans récursion — c’est la tabulation.

Les deux approches ont la même complexité temporelle. La tabulation évite les risques liés à la récursion et permet parfois d’optimiser la mémoire.

Le terme programmation ne signifie pas écrire un programme mais planifier une solution. C’est une méthode algorithmique, introduite par Richard Bellman dans les années 1950.

Applications

Optimisation : rendu de monnaie, sac à dos, alignement de séquences ADN, …
Recherche de chemin : plus court chemin (Bellman-Ford), …
Comptage : nombre de chemins dans une grille, nombre de sous-ensembles, …

Applications

Problèmes d’optimisation : rendu de monnaie, sac à dos, alignement de séquences, …
Problèmes de recherche : plus court chemin, plus longue sous-séquence commune, …
Problèmes de comptage : nombre de chemins, nombre de sous-ensembles, …

Approche `top-down`

Rendu de monnaie glouton

Algorithmes gloutons

Rappel : un algorithme glouton est un algorithme qui résout un problème en faisant des choix locaux optimaux. Il ne revient pas sur ses choix.

Rendu de monnaie : on veut rendre une somme $s$ avec un nombre minimal de pièces
On choisit la pièce la plus grande possible à chaque fois

Implémentation

def rendu_monnaie_glouton(sar, pieces):
    pieces = sorted(pieces, reverse=True)
    rendu = []
    for p in pieces:
        while sar >= p:
            rendu.append(p)
            sar -= p
    return rendu

Problème

On veut rendre $s = 11 cts$ avec des pièces de 2, 5, 10 et 50 centimes, et 1 euro (100 centimes).
Première pièce : 10 centimes
Deuxième pièce : on est coincés

Il existe des cas où l’algorithme glouton ne donne pas la solution optimale, ou ne donne pas de solution du tout, alors qu’une solution existe (ici : 1 pièce de 5 cts, et 3 pièces de 2 cts).

Rendu de monnaie programmation dynamique

Principe

Soit $s$ la somme à rendre. On note $R(s)$ la liste optimale de pièces pour rendre $s$ .
Cette somme peut être rendue en ajoutant une pièce $p$ à une somme $s-p$ qui a déjà été rendue de façon optimale, et si plusieures pièces sont possibles, on choisit la solution qui minimise le nombre de pièces.

On peut donc écrire un algorithme récursif pour résoudre ce problème.

si $s = 0$ , $R(s) = []$
sinon, $R(s) = \min _{p_i \in \text{pieces}} \left( \left[p_i\right] \cup R(s-p_i) \right)$

Attention : il faut prévoir le cas où on ne peut pas rendre la somme. CF code après.

Implémentation sans mémoïsation

def rendu_dyn(sar, pieces): # renvoie bool, liste = trouvé ? et liste pces
    # Cas de base, on a trouvé youpi
    if sar == 0:
        return True, []
    # On recherche la meilleure (= la plus courte) liste de pieces
    best_liste, best_size = None, None
    # On parcours toutes les pieces disponibles
    for p in pieces:
        # Si la piece est > a la somme a rendre = piece inutile, next
        if p > sar:
            continue
        # On demande a rendu_dyn de renvoyer la solution optimale 
        # pour sar-p
        # Il renvoie une liste `liste` de pieces si il a trouvé `trouve`
        trouve, liste = rendu_dyn(sar-p, pieces)
        # Si rendu_dyn n'a pas trouvé, on passe a la piéce suivante
        if not trouve:
            continue
        # Sinon on check si la solution avec cette piece est 
        # la meilleure (plus courte)
        if (best_size is None            # c le premier, on prend de ttes façons
            or len(liste) < best_size):  # c une meilleure solution
            best_size = len(liste) + 1   # on enregistre la taille (= la liste + la piece)
            best_liste = [p] + liste     # on enregistre la liste (+ la piece)
    # si on a pas trouvé, on renvoie False
    if best_size is None:
        return False, []
    # On a trouvé, on renvoie la liste
    return True, best_liste

rendu_dyn(11, [10,2,5])

Implémentation avec mémoïsation

def rendu_dyn_mem(sar, pieces, memo=None): # renvoie bool, liste = trouvé ? et liste pces
    if memo is None:
        memo = {0: (True,[])}
    if sar in memo:
        return memo[sar]
    # On recherche la meilleure (= la plus courte) liste de pieces
    best_liste, best_size = None, None
    # On parcours toutes les pieces disponibles
    for p in pieces:
        # Si la piece est > a la somme a rendre = piece inutile, next
        if p > sar:
            continue
        # On demande a rendu_dyn_mem de renvoyer la solution optimale 
        # pour sar-p
        # Il renvoie une liste `liste` de pieces si il a trouvé `trouve`
        trouve, liste = rendu_dyn_mem(sar-p, pieces, memo)
        # Si rendu_dyn_mem n'a pas trouvé, on passe a la piéce suivante
        if not trouve:
            continue
        # Sinon on check si la solution avec cette piece est 
        # la meilleure (plus courte)
        if (best_size is None            # c le premier, on prend de ttes façons
            or len(liste) < best_size):  # c une meilleure solution
            best_size = len(liste) + 1   # on enregistre la taille (= la liste + la piece)
            best_liste = [p] + liste     # on enregistre la liste (+ la piece)
    # si on a pas trouvé, on renvoie False
    if best_size is None:
        # On enregistre la solution dans le memo
        memo[sar] = False, []
        return False, []
    # On enregistre la solution dans le memo
    memo[sar] = True, best_liste
    # On a trouvé, on renvoie la liste
    return True, best_liste

rendu_dyn_mem(11, [10,2,5])

Approche `bottom-up`

Limites de la mémoïsation

Rappel

La mémoïsation est une approche descendante (top-down) :

On part du problème de taille $n$
On descend récursivement vers les cas de base
On stocke les résultats au fur et à mesure

Problème

Chaque appel récursif empile un contexte d’exécution sur la pile d’appels
Pour $n$ grand, on risque un dépassement de pile (stack overflow)
En Python, la limite par défaut est ~1000 appels récursifs imbriqués

import sys
sys.setrecursionlimit(10000)  # contournement, pas une vraie solution

La récursion a un coût en mémoire caché : chaque appel occupe de l’espace sur la pile, en plus du dictionnaire de mémoïsation.

Solution

L’approche ascendante (bottom-up) résout d’abord les petits sous-problèmes, puis construit la solution au problème de taille $n$ à partir de ceux-ci. Elle n’utilise pas de récursion.

Fibonacci ascendant

Principe

Au lieu de partir de $F(n)$ et de descendre, on part des cas de base et on remonte :

On crée un tableau dp de taille $n+1$
On initialise dp[0] = 0 et dp[1] = 1
On remplit le tableau de gauche à droite : dp[i] = dp[i-1] + dp[i-2]
On retourne dp[n]

Implémentation

def fibt(n):
    if n == 0:
        return 0
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Tableau de calcul pour $n = 6$

i	0	1	2	3	4	5	6
dp	0	1	1	2	3	5	8

On remplit le tableau de gauche à droite. Chaque valeur ne dépend que des deux cases précédentes.

Complexité

Temps : $O(n)$ — comme la version mémoïsée
Mémoire : $O(n)$ — on stocke toutes les valeurs dans le tableau

Optimisation mémoire

Observation

Pour calculer dp[i], on n’a besoin que de dp[i-1] et dp[i-2]. Inutile de conserver tout le tableau.

Implémentation avec $O(1)$ en mémoire

def fibt_opt(n):
    if n == 0:
        return 0
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

On ne garde que les deux dernières valeurs
La mémoire utilisée est constante, quelle que soit la valeur de $n$

Cette optimisation est caractéristique de l’approche ascendante : elle n’est pas possible avec la mémoïsation, qui doit conserver tous les appels en attente sur la pile.

Rendu de monnaie ascendant

Principe

On construit la solution pour toutes les sommes de $0$ à $s$ , dans l’ordre croissant.

On crée un tableau dp de taille $s+1$
dp[0] = (True, []) : rendre 0 est toujours possible, avec une liste vide
Pour chaque somme mm de 11 à ss :
- On essaie chaque pièce $p \leq m$
- On vérifie si dp[m - p] a été trouvé (trouve)
- Si oui, et si len(liste) + 1 < best_size, on met à jour la meilleure solution
- Si aucune pièce ne fonctionne, dp[m] = (False, [])

Implémentation

def rendu_topdown(sar, pieces):
    # dp[m] = (trouvé, liste) : solution optimale pour rendre la somme m
    # Cas de base : rendre 0 est toujours possible, avec une liste vide
    dp = {0: (True, [])}

    # On remplit dp pour toutes les sommes de 1 à sar (ordre croissant)
    for m in range(1, sar + 1):
        best_liste, best_size = None, None
        # On parcourt toutes les pièces disponibles
        for p in pieces:
            # Si la pièce est > à la somme courante = pièce inutile, next
            if p > m:
                continue
            # dp[m-p] est forcément déjà calculé (m-p < m)
            # On récupère la solution optimale pour m-p
            trouve, liste = dp[m - p]
            # Si on n'a pas pu rendre m-p, cette pièce ne mène à rien
            if not trouve:
                continue
            # Sinon on vérifie si la solution avec cette pièce est
            # la meilleure (= la plus courte) trouvée jusqu'ici
            if (best_size is None           # c'est la première, on prend de toutes façons
                or len(liste) + 1 < best_size): # c'est une strictement meilleure solution
                best_size = len(liste) + 1  # on enregistre la taille (liste + la pièce)
                best_liste = [p] + liste    # on enregistre la liste (+ la pièce)
        # Si aucune pièce n'a fonctionné, m est impossible à rendre
        if best_size is None:
            dp[m] = False, []
        else:
            dp[m] = True, best_liste

    return dp[sar]

rendu_topdown(11, [10, 2, 5])

Tableau de calcul pour $s = 11$ , pièces $= [10, 2, 5]$

$m$	trouvé	liste optimale
0	Oui	`[]`
1	Non	—
2	Oui	`[2]`
3	Non	—
4	Oui	`[2, 2]`
5	Oui	`[5]`
6	Oui	`[2, 2, 2]`
7	Oui	`[2, 5]`
8	Oui	`[2, 2, 2, 2]`
9	Oui	`[2, 2, 5]`
10	Oui	`[10]`
11	Oui	`[2, 2, 2, 5]`

Les cases à Non correspondent à des sommes impossibles à rendre avec les pièces disponibles (ici : 1 et 3).

Cas impossible

Si dp[s] vaut (False, []) à la fin, c’est qu’il n’existe aucune façon de rendre la somme $s$ avec les pièces disponibles.

trouve, lst = rendu_bas(3, [2, 5, 10])
if not trouve:
    print("Impossible de rendre cette somme.")
else:
    print(f"{len(lst)} pièce(s) : {lst}")

Complexité

Temps : $O(s \times |\text{pieces}|)$ — on remplit $s$ cases, chacune en $O(|\text{pieces}|)$
Mémoire : $O(s)$ — le dictionnaire dp

Comparaison des trois approches

Sur Fibonacci

Approche	Direction	Récursion	Temps	Mémoire
Naïve	Top-down	Oui	$O(\varphi^n)$	$O(n)$ (pile)
Mémoïsation	Top-down	Oui	$O(n)$	$O(n)$ (pile + dict)
Tabulaire	Bottom-up	Non	$O(n)$	$O(n)$ (tableau)
Tabulaire opt.	Bottom-up	Non	$O(n)$	$O(1)$

Sur le rendu de monnaie

Approche	Direction	Récursion	Temps	Mémoire
Glouton	—	Non	$O(s \log \|\text{p}\|)$	$O(1)$
Dynamique naïf	Top-down	Oui	$O(s^{\|\text{p}\|})$ exponentiel	$O(s)$ (pile)
Mémoïsation	Top-down	Oui	$O(s \times \|\text{p}\|)$	$O(s)$ (pile + dict)
Tabulaire	Bottom-up	Non	$O(s \times \|\text{p}\|)$	$O(s)$

Bilan

Les approches mémoïsée et tabulaire ont la même complexité temporelle
L’approche tabulaire évite la récursion : pas de risque de dépassement de pile
L’approche tabulaire peut être optimisée en mémoire quand les sous-problèmes n’ont besoin que de quelques valeurs précédentes
L’approche mémoïsée est souvent plus naturelle à écrire (proche de la définition mathématique du problème)

Programme

Capacités attendues et commentaires

Capacités attendues

Commentaires

Programmation dynamique

Fibonnacci naif

Définition

Implémentation naïve

Arbre d’appels

Problème

Fibonnacci avec mémoïsation

Mémoïsation

Complexité avec mémoïsation

Programmation dynamique

Concept

Principe

Deux approches

Applications

Applications

Approche top-down

Rendu de monnaie glouton

Algorithmes gloutons

Implémentation

Problème

Rendu de monnaie programmation dynamique

Principe

Implémentation sans mémoïsation

Implémentation avec mémoïsation

Approche bottom-up

Limites de la mémoïsation

Rappel

Problème

Solution

Fibonacci ascendant

Principe

Implémentation

Tableau de calcul pour n=6n = 6

Complexité

Optimisation mémoire

Observation

Implémentation avec O(1)O(1) en mémoire

Rendu de monnaie ascendant

Principe

Implémentation

Tableau de calcul pour s=11s = 11, pièces =[10,2,5]= [10, 2, 5]

Cas impossible

Complexité

Comparaison des trois approches

Sur Fibonacci

Sur le rendu de monnaie

Bilan

Approche `top-down`

Approche `bottom-up`

Tableau de calcul pour $n = 6$

Implémentation avec $O(1)$ en mémoire

Tableau de calcul pour $s = 11$ , pièces $= [10, 2, 5]$