Skip to main content Link Search Menu Expand Document (external link)

Billets en français

Différence entre mémoïsation et programmation dynamique

Update : Merci à Marc de Falco qui a trouvé une erreur dans le code initial. J’élabore là-dessus ci-dessous.

L’autre jour, en jury de l’agrégation d’informatique où j’ai eu la chance de participer de 2022 à 2025 en compagnie de collègues et candidats aussi brillants que passionnés, le candidat choisit la leçon sur la programmation dynamique et fait son développement sur le célèbre algorithme de sac à dos. Une collègue pose la question : “Qu’est-ce qui se passe si les capacités des poids sont négatives ?”

Cette question permet d’illustrer une différence entre mémoïsation et programmation dynamique.

On commence par la façon classique de résoudre le problème dans le cas des capacités positives $c_i \geqslant 0$. La relation de récurrence (équation de Bellman) est la suivante.

Si $maxval[i][c]$ est la capacité maximale que l’on peut atteindre avec les $i \geqslant 0$ premiers objets et une capacité limite de $c$, alors $maxval[0][c] = 0$ pour toute capacité $c$ (pas d’objet) et quand $i \geqslant 1$,

\[maxval[i][c] = \max \begin{cases}maxval[i - 1][c] \textrm{ (si on ne prend pas le $i$-ème objet)}\\maxval[i - 1][c - c_i] + v_i \textrm{ si $c \geqslant c_i$ (si on prend le $i$-ème objet)}\end{cases}\]

On peut faire un balayage avec une double boucle pour aller en nombre d’objets croissant et capacité croissante (bottom-up). Complexité temps et mémoire : $O(nC)$ où $n$ est le nombre d’objets et $C$ est la capacité du sac à dos.

capacities = [2, 3, 5]
values = [6, 4, 2]
cmax = 9

def knapsack():
    n = len(capacities)
    max_value = [[0] * (1 + cmax) for _ in range(n + 1)]
    candidates = []
    for i in range(1, n + 1):
        for c in range(0, cmax + 1):
            candidates = [max_value[i - 1][c]]
            if c >= capacities[i - 1]:
                candidates.append(values[i - 1] + max_value[i - 1][c - capacities[i - 1]])
            max_value[i][c] = max(candidates)
    return max_value[n][cmax]

knapsack()

En effet, on peut obtenir une valeur de 10 avec les 2 premiers objets (capacité totale 2 + 3 = 5 en dessous de la limite 9).

Cette méthode nous permet de répondre à toutes les questions possibles : que vaut $maxval$ pour les $i$ premiers objets et une capacité limite $c$ ? On visite tous les états possibles $(i, c)$.

Regardons à présent à quoi ressemblerait une solution qui mémoïserait (i.e. stockerait les appels récursifs pour ne pas recalculer la même quantité plusieurs fois). On peut s’appuyer sur l’astuce Python du décorateur @cache. (On est plusieurs profs à penser que la mémoïsation devrait être enseignée avant la programmation dynamique.) Notez au passage à quel point ce code est similaire au précédent. En particulier, si on faisait du Haskell, on n’aurait pas besoin du décorateur.

from functools import cache

capacities = [2, 3, 5]
values = [6, 4, 2]
cmax = 9

@cache
def max_value(i, c):
    candidates = []
    if i == 0:
        return 0
    candidates.append(max_value(i - 1, c))
    if c >= capacities[i - 1]:
        candidates.append(values[i - 1] + max_value(i - 1, c - capacities[i - 1]))
    return max(candidates)

n = len(capacities)
max_value(n, cmax)

Complexité : autant d’appels que strictement nécessaire, $O(nC)$ au pire. Mais soyons plus précis.

Soit $C_M$ le nombre d’états uniques (cases mémoire) parcourus par l’algorithme. On a d’une part $C_M \leq (n + 1)(C + 1)$ car c’est le nombre total d’états possibles, et d’autre part $C_M \leq 2^n$ car c’est le nombre total de combinaisons possibles (et d’appels récursifs si on ne faisait pas de mémoïsation).

On voit bien que selon le régime, par exemple si $n$ est petit et $C$ grand, il vaut mieux tout tester, même avec l’algorithme naïf, plutôt que de remplir tous les états possibles. Si $C$ est petit on a plutôt envie d’exploiter la redondance. Dans tous les cas, l’algorithme de mémoïsation est optimal en temps (mais pas en mémoire). Le gain par rapport au naïf est $C_M / 2^n$ et par rapport à l’algo de programmation dynamique est $C_M / ((n + 1)(C + 1))$. Faudrait que je fasse un dessin sur une instance avec les cases visitées pour chaque algorithme.

À présent, regardons ce qui se passe dans le cas de capacités négatives. (Veillez à bien exécuter les cellules précédentes avant celle-ci.)

La mémoïsation fonctionne et reste optimale. Update : en fait non, le code ci-dessus est faux. Cherchez un contre-exemple, en voici un.

capacities = [2, -1]
values = [1, 1]
cmax = 1

n = len(capacities)
max_value.cache_clear()  # Sinon les appels sont encore dans la mémoire
max_value(n, cmax)

Ici, la réponse est bonne : 2, on prend tous les objets. Mais si on met les objets dans l’autre ordre :

capacities = [-1, 2]
values = [1, 1]
cmax = 1

n = len(capacities)
max_value.cache_clear()
max_value(n, cmax)

On rate l’objet de poids 2 car on ne s’autorise pas à passer par des états de capacités négatives qu’on pourrait rattraper plus tard. Autorisons donc les capacités négatives tant que l’état final convient. La relation de récurrence est donc :

\[maxval[0][c] = \begin{cases}0 \textrm{ si $c \geqslant 0$ (il reste de la capacité)}\\ -\infty \textrm{ sinon}\end{cases}\\ maxval[i][c] = \max \begin{cases}maxval[i - 1][c] \textrm{ si on ne prend pas le $i$-ème objet}\\maxval[i - 1][c - c_i] + v_i \textrm{ si on prend le $i$-ème objet}\end{cases}\]

Code modifié :

from functools import cache

capacities = [-1, 2]
values = [1, 1]
cmax = 1

@cache
def max_value_neg(i, c):
    candidates = []
    if i == 0:
        return 0 if c >= 0 else float('-inf')  # Valeur admissible s'il reste de la capacité
    return max(
        max_value_neg(i - 1, c),
        values[i - 1] + max_value_neg(i - 1, c - capacities[i - 1])
    )

n = len(capacities)
max_value_neg(n, cmax)

Quelle est sa complexité ? On pourrait l’améliorer en éliminant les branches non prometteuses (s’il ne reste plus d’objets pour aboutir à un état positif). Qu’en est-il de l’algorithme itératif de programmation dynamique au début de ce billet ?

capacities = [-1, 2]
values = [1, 1]
cmax = 1

knapsack()

Exercice au lecteur : comment modifier le code précédent de knapsack pour qu’il fonctionne dans le cas de capacités négatives ? Quel est le nombre d’états maximaux à considérer ? Quelle est la structure de données adaptée ? Faites un dessin sur papier pour voir ce qui se passe.

Une autre solution d’un étudiant est de partir d’un état où on a pris toutes les capacités négatives et considérer des actions “enlever l’objet” afin de se ramener au sac à dos à capacités positives. C’est également une solution correcte.

Méta : si ça vous intéresse de voir comment j’ai chargé pyodide sur ce blog post Jekyll, vous pouvez regarder en bas du source de cette page. Vous pouvez faire une PR pour remplacer le premier bloc par un textarea (avec coloration syntaxique svp) pour modifier le code.

Gamme pythagoricienne

En musique, on change d’octave en doublant la fréquence. On passe à la quinte en multipliant par 3/2.

Aho-Corasick

Étant donnée une liste de chaînes de caractères L, construire une structure de données qui permet en temps linéaire d’identifier toutes les occurrences des mots de L à l’intérieur d’un mot S donné.

Meilleur developpeur de France 2023

Le 9 mars 2023 avait lieu la compétition Meilleur Développeur de France 2023. Les algorithmes nécessaires sont résoudre les problèmes sont assez simples, mais il faut coder rapidement. Après coup, et à tête reposée, voici comment on aurait pu résoudre certains des problèmes.

Six dates importantes en algorithmique

-300
Algorithme d’Euclide (qui date peut-être de l’école de Pythagore 530 av. J.C.)

Parcours en profondeur de Trémaux, parcours main gauche de Pledge

Parcours en profondeur de Trémaux

Comment décomposer un nombre en facteurs premiers ?

Étant donné n on veut produire en temps linéaire deux tableaux factor et primes, tel que primes contienne tous les nombres premiers entre 2 et n, et que factor[x] contienne le plus petit facteur de x, avec facteur[x]==x si x est premier.

Comment planifier une todo-list ?

Introduction

Dessiner sans lever le crayon !

Introduction

Utiliser Paint pour les sudokus

Introduction

Trier un tableau en un nombre minimal d'étapes d'insertion

Le problème

Comment marche l'outil "Seau" de Paint ?

Contexte

Des ballons et des plafonds

Jouons à Google Flights avec Bellman-Ford !

Contexte

PyParis : 12–13 juin à La Défense

Le logo de PyParis

Nos conseils pour l'option ICN : idées à coder

Voici des idées d’activités pour l’option ICN au lycée, ou plus généralement toute activité de programmation pour lycéens.

Google Codejam 2017 - 1B

Nous décrivons ici des solutions pour la ronde 1B du concours Google Codejam 2017.

Le Compte est bon ?

Pourrez-vous résoudre cette énigme du jeu Le Compte est bon ?

Solutions du Google Hash Code 2017 - Streaming Videos

Nous décrivons ici notre petite expérience avec le concours Google Hashcode 2017 : Optimize Cache Servers for YouTube.

Trouver un plus court chemin grâce à Google Ma... Dijkstra

Contexte

Casser RSA avec des réseaux euclidiens

Bonjour.

Google Hashcode - Pizza Régina

Le concours annuel Google Hashcode consiste à résoudre en équipe une instance d’un problème NP-complet. Résoudre veut dire ici produire une solution faisable. La valeur objectif atteinte est le score de la solution. Les problèmes présentés sont assez purs, comparés à ceux du concours annuel Roadef challenge, qui contiennent beaucoup plus de contraintes et sont plus proches d’un problème réel.

Qualifications Facebook Hacker Cup 2017

Pour commencer l’année, ce week-end de l’épiphanie ont eu lieu les qualifications de Facebook Hacker Cup.

Rendu de monnaie, bases de programmation dynamique

Contexte

Mariages stables, ou comment marier le Prix Nobel d'économie aux sites de rencontres

Note : Une partie de cet article a été reprise d’ici, mais pas de panique, je suis une co-auteure.

Rechercher des mots dans un texte par l'algorithme de Knuth-Morris-Pratt

Contexte

Arbres de Merkle : la structure de données à l'origine de git, BitTorrent, Bitcoin, Ethereum, The DAO et autres blockchains

Merkle trees (1979)

Le principe est simple : calculer le hash d’un nœud à partir d’un hash de ses fils. Dans un arbre binaire, pour un nœud ayant pour fils $h_1$ et $h_2$ : \(h(noeud) = h(h1, h2)\).

SWERC 2016 à Porto

Le logo du concours ICPC

Le saviez-vous ? Du 19 au 20 novembre 2016 ont eu lieu les épreuves régionales SWERC du concours de programmation ICPC à Porto, au Portugal.

  • 11 problèmes
  • 5 heures
  • 3 personnes et 1 clavier par équipe

SWERC 2015

Et voici les photos de SWERC 2015.

Arbres de Merkle, P2P, Bitcoin et Git

Par JJV.

Sous-modularité

Par Guillaume Aubian.

Réduction de réseaux par l'algorithme LLL

Par Thomas Espitau.

Classement Elo, algorithme EM

Classement Elo

Une projection des joueurs d’échecs sur $\mathbf{R}_+$ (leur score). Ça a été proposé par Arpad Elo il y a assez longtemps.

Aujourd’hui, c’est utilisé par des plateformes comme Codeforces ou HackerRank.

128 algorithmes

Voici les slides de notre conférence du 29 mars 2016 au NUMA.

Structures de données

Voici une structure de données des structures de données.

Résolution de problèmes algorithmiques

On peut distinguer trois types de problèmes.

Arbre de Fenwick

C’est une structure de données dynamique : elle permet de stocker un tableau de $n$ valeurs et de réaliser efficacement les opérations suivantes :

  • mettre à jour une valeur du tableau ;
  • calculer la somme d’une plage du tableau.

Compte rendu du workshop algo n° 1

Présents :

  • Guillaume Aubian
  • Clément Beauseigneur
  • Maxim Berman
  • Thomas Espitau
  • Thomas Domingues
  • Jill-Jênn Vie
  • X

Debuggue mon flot max (si t'es cap)

Pourquoi sur le graphe de capacités suivantes :

J’obtiens un flot max à 13 :

o

Compte rendu de l'atelier n° 1

Table des matières

Généralités

Activités