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

fibonnacci(4)
    fibonnacci(3)
        fibonnacci(2)
            fibonnacci(1)
            fibonnacci(0)
        fibonnacci(1)
    fibonnacci(2)
        fibonnacci(1)
        fibonnacci(0)

Problème

• Énormément d’appels
• La complexité de cet algorithme est exponentielle (en $O(2^n)$). Pour $n = 40$, il faut $10^{12}$ 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

Principe

• La programmation dynamique est une méthode pour résoudre des problèmes récursifs
• On va résoudre le problème en résolvant des sous-problèmes
• On va stocker les résultats des sous-problèmes pour ne pas les recalculer

Le terme “programmation” ne signifie pas “écrire un programme” mais “résoudre un problème”. C’est une méthode algorithmique.

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, …

Exemples

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(s, pieces):
    pieces = sorted(pieces, reverse=True)
    rendu = []
    for p in pieces:
        while s >= p:
            rendu.append(p)
            s -= 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(arendre, pieces):
    if arendre == 0:
        return 0, []
    best_rendu, best_rendu_len = [], float("inf")
    for piece in pieces:
        if piece <= arendre:
            clen, c = rendu_dyn(arendre - piece,
                                pieces)
            if clen < best_rendu_len:
                best_rendu = c + [piece]
                best_rendu_len = clen
    return best_rendu_len, best_rendu

rendu_dyn(11, [ 2, 5, 10, 20, 50, 100])

Implémentation avec mémoïsation

def rendu_dyn_mem(arendre, pieces, mem=None):
    if mem is None:
        mem = {0: (0, [])}
    if arendre in mem:
        return mem[arendre]
    best_rendu, best_rendu_len = [], float("inf")
    for piece in pieces:
        if piece <= arendre:
            clen, c = rendu_dyn_mem(arendre - piece,
                                    pieces, mem)
            if clen < best_rendu_len:
                best_rendu = c + [piece]
                best_rendu_len = clen
    mem[arendre] = best_rendu_len, best_rendu
    return best_rendu_len, best_rendu

rendu_dyn_mem(11,  [2, 5, 10, 20, 50, 100])