Aller au contenu

Triangle de nombres (Bac 🎯)⚓︎

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

programme

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

  • le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen dont est tiré l'exemple du rendu de monnaie.
  • le livre part 3 : greedy algorithms and dynamic programming de Tim Roughgarden dont est tirée la comparaison entre les méthodes de conception d'algorithme programmation dynamique et Diviser Pour Régner.
  • le cours de mon collègue Pierre Duclosson pour l'exemple du triangle de nombres

🔖 Synthèse de ce qu'il faut retenir pour le bac

Un problème d'optimisation⚓︎

Point de cours 4 : problème de la somme maximale dans un triangle

Source : Pierre Duclosson

Tout d'abord, on spécifie le problème étudié qu'on désignera comme problème de la somme maximale dans un triangle.

Entrée du problème

On suppose donné un triangle dont les éléments sont des nombres entiers positifs arbitraires. On parcourt ce triangle du haut vers le bas en additionnant les nombres rencontrés. À chaque étape, on peut passer à l'élément situé juste en-dessous du précédent ou effectuer un décalage vers la droite : il n'y a que deux mouvements possibles.

Par exemple dans le triangle représenté ci-dessous, on peut calculer la somme \(3+38+31+4+41\) mais pas la somme \(3+38+34+4+42\) car après le \(38\) de la deuxième ligne, on ne peut passer qu'au \(31\) ou au \(33\) de la troisième ligne.

alt

Sortie attendue

On veut déterminer la somme maximale qu'on peut définir de cette façon et un chemin qui la réalise.

Choix d'une méthode de résolution⚓︎

Exercice 4 : méthode force-brute

Source : Pierre Duclosson

Question 1

Recopier et compléter le tableau ci-dessous. \(n\) désigne un entier strictement positif.

Nombre de lignes du triangles Nombre de chemins différents entre le sommet et la dernière ligne
1 1
2 2
3 ...
4 ...
5 ...
\(n\) ...
Nombre de lignes du triangles Nombre de chemins différents entre le sommet et la dernière ligne
1 1
2 2
3 4
4 8
5 16
\(n\) \(2^{n-1}\)

Question 2

Si on écrit une fonction de recherche de la somme maximale qui explore tous les chemins possibles, par force brute, sa complexité par rapport au nombre \(n\) de lignes du triangle, sera (cocher la bonne réponse) :

  • logarithmique
  • linéaire
  • linéarithmique
  • quadratique
  • exponentielle
  • ❌ logarithmique en \(O(\log(n))\)
  • ❌ linéaire en \(O(n)\)
  • ❌ linéarithmique en \(O(n \log(n))\)
  • ❌ quadratique en \(O(n^{2})\)
  • ✅ exponentielle en \(O(2^{n})\)

Question 3

La complexité d'un algorithme force brute est-elle acceptable sachant que le superordinateur américain Frontier a franchi en 2022 la barre des \(10^{18}\) opérations en virgule flottante par seconde (exaflops) ?

a Avec un algorithme force brute, pour déterminer la somme maximale dans une pyramide de \(101\) lignes, on a \(2^{100}=(2^{10})^{10}\approx (10^{3})^{10} \approx 10^{30}\) chemins différents et il faut \(99 \approx 10^{2}\) somme par chemin plus une comparaison par chemin pour déterminer la somme maximale, soit environ \(10^{30} \times 10^{2} = 10^{14} \times 10^{18}\) opérations. Même sur le superordinateur américain Frontier, qui réalise \(10^{18}\) opérations par seconde, le coût serait d'environ \(10^{14}\) secondes soit \(\frac{10^{14}}{365,25 \times 24 \ times 3600} \approx 32\) milliards d'années ! L'explosion combinatoire d'une complexité exponentielle rend un algorithme force brute inutilisable en pratique sauf sur de petits triangles.

Exercice 5 : méthode gloutonne

💻 Saisir ses réponses sur Capytale

Comme on l'a vu avec le problème du rendu de monnaie, dans un problème d'optimisation, un algorithme glouton permet de calculer rapidement une solution en faisant des choix localement optimaux.

Attention

Le plus souvent un algorithme glouton ne permet pas d'obtenir une solution globalement optimale (cf le problème du rendu de monnaie).

Question 1

  1. Proposer un algorithme glouton qui construit rapidement une solution au problème de la somme maximale dans un triangle.

  2. On suppose que le triangle de nombres est représenté en Python par une liste de listes comme ci-dessous pour le triangle 1. Implémenter l'algorithme glouton précédent dans une fonction somme_maxi_glouton qui prend en paramètre le triangle de nombres et renvoie un entier.

    🐍 Script Python
    t1 = [[3], 
     [40, 38], 
     [34, 31, 33], 
     [3, 4, 22, 25], 
     [42, 24, 41,  38 , 5]]

###
def sommepy-undmaxipy-undglouton(t):bksl-nl # à compléterbksl-nl ...bksl-nlbksl-nldef testpy-undsommepy-undmaxipy-undglouton():bksl-nl t1 = [[3], [40, 38], [34, 31, 33], [3, 4, 22, 25], [42, 24, 41, 38, 5]]bksl-nl assert sommepy-undmaxipy-undglouton(t1) == 122bksl-nl print("tests réussis")bksl-nlbksl-nl# à décommenterbksl-nl#testpy-undsommepy-undmaxipy-undglouton()bksl-nl

  1. Donner la complexité de cet algorithme par rapport au nombre de lignes \(n\) du triangle.

  1. Lorsqu'on doit choisir le prochain mouvement, un choix glouton naturel consiste à choisir de se déplacer vers le nombre le plus grand. En, partant du sommet et en répétant ce choix glouton jusqu'à la dernière ligne on construit donc rapidement une solution.

  2. Implémentation de l'algorithme glouton :

    🐍 Script Python
    def somme_maxi_glouton(t):
    s = t[0][0]
    j = 0
    for i in range(1, len(t)):
        if t[i][j + 1] > t[i][j]:
            j = j + 1
        s = s + t[i][j]
    return s

t1 = [[3], [40, 38], [34, 31, 33], [3, 4, 22, 25], [42, 24, 41,  38 , 5]]
assert somme_maxi_glouton(t1) == 122

  3. On définit ainsi un algorithme glouton avec \(n-1\) itérations de boucles dont de complexité linéaire en \(O(n)\) puisque l'exécution de chaque itération de boucle est de coût constant (1 comparaison et 1 ou 2 affectations).

Question 2

On considère le triangle 1 donné dans la spécification du problème de la somme maximale dans un triangle.

Déterminer si l'algorithme glouton proposé en question 1, est correct.

On rappelle qu'un algorithme est correct s'il satisfait sa spécification : pour toute entrée possible, il fournit la sortie attendue.

alt

L'algorithme glouton sélectionne le chemin ci-dessous dont la somme est \(3 + 40 + 34 + 4 + 41 = 122\).

alt

Ce n'est pas une solution optimale car il existe plusieurs chemins réalisant des sommes supérieures :

  • \(3 + 38 + 31 + 22 + 41 = 135\)
  • \(3 + 38 + 33 + 22 + 41 = 137\)
  • \(3 + 38 + 33 + 25 + 48 = 137\)

Exercice 6 : méthode par programmation dynamique

💻 Saisir ses réponses sur Capytale

On se donne en entrée un triangle T de nombres entiers positifs de \(n\) lignes.

Imaginons qu'on dispose d'une solution optimale S au problème de la somme maximale dans le triangle T.

En examinant cette solution du haut (le sommet A du triangle) vers le bas (la dernière ligne), il apparaît qu'on connaît le premier terme de la solution : le sommet A du triangle. En effet, on doit optimiser la somme à partir du sommet !

Pour compléter la somme solution S on a deux possibilités correspondants aux deux mouvements autorisés : la valeur B juste en dessous de A ou celle C en bas à droite.

Or chacune de ces valeurs est le sommet d'un triangle de nombres similaire au triangle initial mais avec une ligne de moins comme on le voit dans la figure ci-dessous pour le triangle 1 :

  • B est le sommet du sous-triangle T1
  • C est le sommet du sous-triangle T2

Par définition des deux mouvements autorisés :

  • si B est le second terme de la somme solution S, tous les termes suivants seront dans le sous-triangle T1, notons S1 cette sous-somme : dans ce cas S = A + S1
  • si C est le second terme, tous les termes suivants seront dans le sous-triangle T2, notons S2 cette sous-somme : S = A + S2

On peut écrire la formule de récurrence: S = A + max(S1, S2).

alt

Question 1

Démontrer par l'absurde que si S = A + S1 avec S somme maximale pour le triangle de sommet A et S1 somme du sous-triangle T1 alors S1 est nécessairement une somme maximale pour le sous-triangle de sommet B.

Hypothèse (H) : Supposons que S1 ne soit pas une somme maximale pour le sous-triangle T1 de sommet B, alors il existe une somme S3 pour T1 qui est strictement supérieure à S1.

Si S3 > S1 alors S3 + A > S1 + A = S

On peut alors compléter S3 avec A pour obtenir une somme S' = A + S3 pour le triangle de sommet A qui serait supérieure à S.

On aboutit à une contradiction puisque S est la somme maximale pour le triangle de sommet A.

L'hypothèse (H) est donc fausse : S1 est la somme maximale pour le triangle de sommet B.

Une démonstration similaire permet de montrer que si S = A + S2 alors S2 est somme maximale pour le triangle de sommet C.

Point de cours 5 : sous-structure optimale

On a fait apparaître une sous-struture optimale dans une solution au problème de la somme maximale dans un triangle : une solution peut être obtenue à partir de solutions de sous-problèmes similaires et plus petits.

Cette sous-struture optimale est caractéristique de la programmation dynamique (Étape 1).

Il nous reste à exprimer la relation de récurrence (Étape 2) plus formellement.

Fixons les notations :

  • On considère un triangle \(t\) de \(n\) lignes numérotées de \(0\) à \(n-1\) avec le sommet en ligne \(0\).
  • Pour chaque ligne d'index \(i\), on a \(i + 1\) colonnes numérotées de \(0\) à \(i\). Par exemple dans le triangle 1 le nombre \(31\) est en ligne d'index \(i=2\) et colonne d'index \(j=1\) et on note \(t(2, 1)= 31\).
  • De plus on note \(s(i, j)\) la somme solution pour le sous-triangle dont le sommet est en ligne \(i\) et colonne \(j\). La somme solution pour le triangle complet est alors \(s(0 ,0)\).

Question 2

  1. Avec les notations définies ci-dessus, comment s'exprime la formule de récurrence S = A + max(S1, S2) établie en préambule de l'exercice ?
  2. Quels sont les cas de base de cette récurrence ?
  1. La formule de récurrence S = A + max(S1, S2) établie précédemment se traduit par : \(s(i, j) = t(i, j) + max(s(i + 1, j), s(i + 1, j + 1))\)
  2. Les cas de bases sont les valeurs sur la dernière ligne du triangle : \(\forall j \in [0, n - 1], \quad s(n - 1, j) = t(n - 1, j)\).

Question 3

Compléter la fonction s ci-dessous pour qu'elle implémente la fonction récursive de recherche de la somme maximale dans un triangle de nombres t qui est une liste de listes définie comme variable globale.

###
def s(i, j):bksl-nl """Renvoie la somme maximale dans le sous-triangle de sommetbksl-nl en ligne i et colonne j dans un triangle de nombres tbksl-nl qui est une liste de listes défini comme variable globale"""bksl-nl if i == len(t) - 1:bksl-nl return ...bksl-nl return ...bksl-nlbksl-nlt = [[3], [40, 38], [34, 31, 33], [3, 4, 22, 25], [42, 24, 41, 38, 5]]bksl-nlassert s(0, 0) == 137bksl-nl

🐍 Script Python
def s(i, j):
    """Renvoie la somme maximale dans le sous-triangle de sommet
    en ligne i et colonne j dans un triangle de nombres t
    qui est une liste de listes défini comme variable globale"""
    if i == len(t) - 1:
        return t[i][j]
    return t[i][j] + max(s(i + 1, j), s(i + 1, j + 1))

t = [[3], [40, 38], [34, 31, 33], [3, 4, 22, 25], [42, 24, 41, 38, 5]]
assert s(0, 0) == 137

Question 4

Il n'est pas recommandé de manipuler des variables globales dans une fonction : la fonction ne peut être séparée de son programme principal et s'il y a une modification de la variable globale, les effets de bord incontrôlés sont difficiles à identifier dans un gros programme.

Compléter la fonction enveloppe somme_max ci-dessous qui prend en paramètre un triangle de nombres t et fait appel à la fonction récursive auxiliaire s similaire à celle de la question 3.

###
def sommepy-undmax(t):bksl-nl """Renvoie la somme maximale dans un triangle de nombresbksl-nl t qui est une liste de listes"""bksl-nl bksl-nl def s(i, j):bksl-nl """Fonction auxiliaire récursive"""bksl-nl if i == len(t) - 1:bksl-nl return ...bksl-nl return ...bksl-nl bksl-nl return s(0, 0)bksl-nlbksl-nldef testpy-undsommepy-undmax():bksl-nl t = [[3], [40, 38], [34, 31, 33], [3, 4, 22, 25], [42, 24, 41, 38, 5]]bksl-nl assert sommepy-undmax(t) == 137bksl-nl print("tests réussis")bksl-nl bksl-nlbksl-nl

🐍 Script Python
def somme_max(t):
    """Renvoie la somme maximale dans un triangle de nombres
    t qui est une liste de listes"""
    
    def s(i, j):
        """Fonction auxiliaire récursive"""
        if i == len(t) - 1:
            return t[i][j]
        return t[i][j] + max(s(i + 1, j), s(i + 1, j + 1))
    
    return s(0, 0)

def test_somme_max():
    t = [[3], [40, 38], [34, 31, 33], [3, 4, 22, 25], [42, 24, 41, 38, 5]]
    assert somme_max(t) == 137
    print("tests réussis")

Question 5

On suppose que la fonction somme_max est correctement implémentée et on exécute le code ci-dessous :

🐍 Script Python
import time
import random

def generer_triangle(n):
    return  [[random.randint(0, 50) for _ in range(m + 1)] for m in range(n)]

for n in range(15, 21):
    t = generer_triangle(n)
    debut = time.perf_counter()
    res = somme_max(t)
    temps = time.perf_counter() - debut
    print(f"Nombre de lignes : {n}, Temps : {temps}")

On obtient en console l'affichage ci-dessous :

🐍 Console Python
Nombre de lignes : 15, Temps : 0.04660052799954428
Nombre de lignes : 16, Temps : 0.07258554999953049
Nombre de lignes : 17, Temps : 0.12457761499990738
Nombre de lignes : 18, Temps : 0.25739053699999204
Nombre de lignes : 19, Temps : 0.5159810610002751
Nombre de lignes : 20, Temps : 1.086611429000186

Quelle conjecture peut-on faire sur l'ordre de grandeur de la complexité de la fonction somme_max par rapport au nombre de lignes \(n\) du triangle de nombres ?

  • logarithmique
  • linéaire
  • linéarithmique
  • quadratique
  • exponentielle

Le temps d'exécution est environ multiplié par \(2\) lorsque le nombre de lignes \(n\) augmente de 1 donc on peut conjecturer que la complexité de la fonction somme_max est exponentielle, de l'ordre de \(2^{n}\).

Cette implémentation naïve d'une méthode par programmation dynamique a la même complexité qu'une solution construite par force brute par exploration exhaustive de tous les chemins reliant le sommet du triangle à la dernière ligne.

Question 6

  1. Compléter l'arbre d'appels ci-dessous pour la fonction récursive s appelée sur un triangle de \(3\) lignes.
  2. L'arbre confirme-t-il la complexité observée expérimentalement à la question 5 ?

alt

Pour un triangle de \(3\) lignes il faut \(1+2+2^{2}=2^{3}-1\) appels récursifs. La dernière ligne correspond aux cas de base et il n'y a plus d'autres appels récursifs.

alt

De façon similaire, pour un triangle de \(n\) lignes il faudra \(1+2+2^{2}+2^{3}+\ldots +2^{n-1}=2^{n} - 1\) appels récursifs. La complexité de la fonction s est dominée par le nombre total d'appels récursifs car quand on a récupéré les valeurs des appels imbriqués, le traitement se fait en coût constant (comparaison et somme).

La complexité exponentielle observée expérimentalement en question 5 est donc confirmée.

Question 7

  1. Quelle technique a-t-on utilisé dans l'étude du problème du rendu de monnaie pour améliorer la complexité de la première version récursive de la résolution par programmation dynamique ?

  2. Compléter ci-dessous le code de la fonction somme_max_memo qui améliore la complexité de la fonction somme_max.

    ⚠️ On n'exécutera test_doubling_ratio que dans Capytale, l'émulation de Python dans le navigateur est trop lente !

  3. Exécuter dans Capytale, la fonction test_doubling_ratio. Quelle complexité peut-on conjecturer pour somme_max_memo ? Confirmer cette conjecture en exprimant en fonction du nombre de lignes \(n\) le nombre d'appels de la fonction récursive auxiliaire s nécessaires.

###
import timebksl-nlimport randombksl-nlbksl-nldef genererpy-undtriangle2(n):bksl-nl return [[random.randint(0, 50) for py-und in range(m + 1)] for m in range(n)]bksl-nlbksl-nldef sommepy-undmaxpy-undmemo(t):bksl-nl """Renvoie la somme maximale dans un triangle de nombresbksl-nl t qui est une liste de listes"""bksl-nl bksl-nl def s(i, j):bksl-nl """Fonction auxiliaire récursive"""bksl-nl # si memo[i][j] == -1 alors s(i, j) n'a pas été déjà calculéebksl-nl if memo[i][j] == -1: bksl-nl if i == len(t) - 1:bksl-nl memo[i][j] = ...bksl-nl else:bksl-nl memo[i][j] = ...bksl-nl return ...bksl-nl bksl-nl # tableau memo pour mémoiser de mêmes dimensions que tbksl-nl # initialisé avec des -1 qui est une somme impossiblebksl-nl # car t ne contient que des entiers positifsbksl-nl memo = [[-1 for j in range(i + 1)] for i in range(len(t))]bksl-nl return s(0, 0)bksl-nlbksl-nldef testpy-undsommepy-undmaxpy-undmemo():bksl-nl t = [[3], [40, 38], [34, 31, 33], [3, 4, 22, 25], [42, 24, 41, 38, 5]]bksl-nl assert sommepy-undmaxpy-undmemo(t) == 137bksl-nl print("tests réussis")bksl-nl bksl-nldef testpy-unddoublingpy-undratio():bksl-nl """Test de performance :bksl-nl On observe l'évolution du coefficient multiplicateur pourbksl-nl le temps d'exécution lorsque le nombre de lognes double bksl-nl """bksl-nl n = 2 py-strpy-str 6bksl-nl tempspy-undpreced = Nonebksl-nl for py-und in range(5):bksl-nl t = genererpy-undtriangle2(n)bksl-nl debut = time.perfpy-undcounter()bksl-nl res = sommepy-undmaxpy-undmemo(t)bksl-nl temps = time.perfpy-undcounter() - debutbksl-nl if tempspy-undpreced is not None:bksl-nl print(f"Nombre de lignes : {n}, Ratio temps / tempspy-undpreced : {temps / tempspy-undpreced}")bksl-nl tempspy-undpreced = tempsbksl-nl n = n py-str 2bksl-nl bksl-nl#testpy-undsommepy-undmaxpy-undmemo()bksl-nlbksl-nl

  1. Dans l'étude du problème du rendu de monnaie, on a réduit la redondance des calculs en stockant dans une structure (tableau ou dictionnaire) chaque calcul de s(i, j) dès qu'on l'a obtenu. Ainsi on ne calcule pas plusieurs fois la même chose. Cette technique s'appelle la mémoïsation.

  2. Code complété :

    🐍 Script Python
    import time
import random

def generer_triangle2(n):
    return  [[random.randint(0, 50) for _ in range(m + 1)] for m in range(n)]

def somme_max_memo(t):
    """Renvoie la somme maximale dans un triangle de nombres
    t qui est une liste de listes"""
    
    def s(i, j):
        """Fonction auxiliaire récursive"""
        # si memo[i][j] == -1 alors s(i, j) n'a pas été déjà calculée
        if memo[i][j] == -1:            
            if i == len(t) - 1:
                memo[i][j] =  t[i][j]
            else:
                memo[i][j] = t[i][j]  + max(s(i + 1, j), s(i + 1, j + 1))
        return memo[i][j]
    
    # tableau memo pour mémoiser de mêmes dimensions que t
    # initialisé avec des -1 qui est une somme impossible
    # car t ne contient que des entiers positifs
    memo = [[-1 for j in range(i + 1)] for i in range(len(t))]
    return s(0, 0)

def test_somme_max_memo():
    t = [[3], [40, 38], [34, 31, 33], [3, 4, 22, 25], [42, 24, 41, 38, 5]]
    assert somme_max_memo(t) == 137
    print("tests réussis")
    
def test_doubling_ratio():
    """Test de performance :
    On observe l'évolution du coefficient multiplicateur pour
    le temps d'exécution lorsque le nombre de lognes double    
    """
    n = 2 ** 6
    temps_preced = None
    for _ in range(5):
        t = generer_triangle2(n)
        debut = time.perf_counter()
        res = somme_max_memo(t)
        temps = time.perf_counter() - debut
        if temps_preced is not None:
            print(f"Nombre de lignes : {n}, Ratio temps / temps_preced : {temps /  temps_preced}")
        temps_preced = temps
        n = n * 2
    
#test_somme_max_memo()
#test_doubling_ratio()

  3. Expérimentalement, on observe en exécutant test_doubling_ratioque le temps d'exécution est environ multiplié par \(4\) lorsque le nombre de lignes du triangle est multiplié par \(2\). On peut donc conjecturer que la complexité temporelle de somme_maxi_memo est quadratique, en \(O(n^{2})\), par rapport au nombre \(n\) de lignes. Prenons un triangle de nombres t de \(n\) lignes, le calcul de somme_max_memo(t) supprime les appels redondants dans l'arbre d'appels réalisé dans la question 6. Il nous reste alors exactement un appel pour chaque sommet présent dans le triangle. Par la suite on appelle sommet toutes les positions possibles pour un nombre dans le triangle. De plus le traitement effectué par chaque appel, après récupération des appels imbriqués, est en coût constant (comparaison et somme). La complexité de somme_max_memo(t) est donc de l'ordre du nombre de sommets présents dans le triangle. On a \(1\) sommet sur la première ligne, \(2\) sur la seconde, ..., \(n\) sur la dernière soit un total de \(1+2+3+\ldots + n=\frac{n(n+1)}{2}\) sommets. Cela confirme la complexité quadratique en \(O(n^{2})\) observée expérimentalement.

Point de cours 6 : résolution du problème de la somme maximale dans un triangle

Dans le problème de la somme maximale dans un triangle, on a vu que l'algorithme glouton permet de calculer une solution en temps linéaire mais qui n'est pas optimale. En revanche, les méthodes par force brute ou programmation dynamique permettent de constuire une solution optimale.

Pour trouver un algorithme de résolution par programmation dynamique on a procédé par étapes :

  • Étape 1 : On a fait apparaître une sous-structure optimale en exprimant la solution en fonction de solutions de sous-problèmes similaires et plus petits.
  • Étape 2 : On a calculé la solution en fonction de celles des sous-problèmes à l'aide d'une formule de récurrence et on a amélioré la complexité temporelle de l'algorithme en mémorisant les résultats déjà calculés, c'est la technique de mémoïsation.

Par rapport au nombre \(n\) de lignes du triangle de nombres en entrée, on obtient les complexités suivantes. Pour la complexité en espace on mesure l'espace supplémentaire utilisé (ici pour stocker les résultats intermédiaires).

Méthode Complexité en temps Complexité en espace
Force brute \(O(2^{n})\) \(O(1)\)
Programmation dynamique récursive sans mémoïsation \(O(2^{n})\) \(O(n)\) (taille maximale de la pile d'appels)
Programmation dynamique récursive avec mémoïsation \(O(n^{2})\) \(O(n^{2})\)

Dans la section suivante, on va voir comment améliorer la complexité en espace à l'aide d'une méthode par programmation dynamique itérative qui calcule la solution en procédant du bas (la dernière ligne) vers le haut (le sommet du triangle).

Résolution itérative par programmation dynamique⚓︎

Exercice 7

Question 1

On reprend les notations de l'exercice 6 et le triangle 1 :

alt

s(i,j) désigne la somme maximale pour le sous-triangle dont le sommet est en ligne i et colonne j dans le triangle complet.

Recopier et compléter le tableau ci-dessous qui permet de calculer s(i, j) en appliquant la relation de récurrence \(s(i, j) = t(i, j) + max(s(i + 1, j), s(i + 1, j + 1))\) à rebours. On progresse du bas (la dernière ligne) vers le haut (le sommet du triangle complet) en mémorisant les résultats intermédiaires dans le tableau.

i / j 0 1 2 3 4
4 42 24 41 38 5
3 3 + max(42, 24)=45 4+max(24, 42)=45 22+max(41,35)=63 25+max(38, 5)=63
2 ... ... ...
1 ... ...
0 ...
i / j 0 1 2 3 4
4 42 24 41 38 5
3 3 + max(42, 24)=45 4+max(24, 42)=45 22+max(41,35)=63 25+max(38, 5)=63
2 34=max(45, 45)=79 31+max(45, 63)=94 33+max(63, 63) = 96
1 40+max(79, 94) = 134 38+max(94, 96)=134
0 3+max(134, 134)=137

Question 2

Implémenter l'algorithme précédent qui calcule la somme maximale d'un triangle tde nombres par programmation dynamique, de façon itérative depuis la dernière ligne (cas de base de la version récursive) jusqu'au sommet, en mémorisant les résultats intermédiaires dans une structure s qui est une liste de listes de mêmes dimensions que t.

Quelles sont les complexités en temps et en espace (supplémentaire utilisé) de cet algorithme par rapport au nombre \(n\) de lignes du triangle de nombres ?

###
def sommepy-undmaxpy-unditer(t):bksl-nl """Renvoie la somme maximale dans un triangle de nombresbksl-nl t qui est une liste de listes""" bksl-nl n = len(t)bksl-nl s = [[0 for py-und in range(len(t[i]))] for i in range(n)]bksl-nl # initialisation de la dernière lignebksl-nl for j in range(n):bksl-nl s[n - 1][j] = ...bksl-nl # on remonte de la dernière ligne jusqu'au sommet du trianglebksl-nl ...bksl-nl # on renvoie la somme maximale du triangle complet s(0,0)bksl-nl return s[0][0]bksl-nlbksl-nldef testpy-undsommepy-undmaxpy-unditer():bksl-nl t = [[3], [40, 38], [34, 31, 33], [3, 4, 22, 25], [42, 24, 41, 38, 5]]bksl-nl assert sommepy-undmaxpy-unditer(t) == 137bksl-nl print("tests réussis")bksl-nl

Cet algorithme est constitué de deux boucles imbriquées qui parcourent les \(\frac{n(n+1)}{2}\) positions dans le triangle qui sont tous les sous-problèmes à résoudre pour résoudre le problème global.

La complexité en temps de cet algorithme est donc quadratique, en \(O(n^{2})\), par rapport au nombre \(n\) de lignes du triangle de nombres.

Cet algorithme utilise une liste de listes s de mêmes dimensions que tdonc consomme \(\frac{n(n+1)}{2}\) cellules de listes supplémentaires soit une complexité quadratique en espace.

🐍 Script Python
def somme_max_iter(t):
    """Renvoie la somme maximale dans un triangle de nombres
    t qui est une liste de listes"""    
    n = len(t)
    s = [[0 for _ in range(len(t[i]))] for i in range(n)]
    # initialisation de la dernière ligne
    for j in range(n):
        s[n - 1][j] = t[n - 1][j]
    # on remonte de la dernière ligne jusqu'au sommet du triangle
    for i in range(n - 2, -1, -1):
        for j in range(len(s[i])):
            s[i][j] = t[i][j] + max(s[i + 1][j], s[i + 1][j + 1])
    return s[0][0]

def test_somme_max_iter():
    t = [[3], [40, 38], [34, 31, 33], [3, 4, 22, 25], [42, 24, 41, 38, 5]]
    assert somme_max_iter(t) == 137
    print("tests réussis")

Question 3

En complétant le tableau de la question 1, on peut remarquer que pour compléter une ligne on n'a besoin que de la ligne précédente et même uniquement des deux valeurs juste au-dessus et au-dessus à droite.

Par conséquent on a juste besoin de mémoriser la ligne précédente et même on modifier directement la ligne pour calculer la suivante si on la remplit dans le bon sens, de gauche à droite en changeant uniquement des valeurs qui ne seront pas réutilisées.

Compléter la fonction somme_max_iter2 qui n'utilise plus qu'une liste de taille \(n\) comme espace supplémentaire, ce qui améliore la complexité en espace.

###
def sommepy-undmaxpy-unditer2(t):bksl-nl """Renvoie la somme maximale dans un triangle de nombresbksl-nl t qui est une liste de listes""" bksl-nl n = len(t)bksl-nl s = [t[n - 1][j] for j in range(n)]bksl-nl # à compléterbksl-nl ...bksl-nl return s[0]bksl-nlbksl-nldef testpy-undsommepy-undmaxpy-unditer2():bksl-nl t = [[3], [40, 38], [34, 31, 33], [3, 4, 22, 25], [42, 24, 41, 38, 5]]bksl-nl assert sommepy-undmaxpy-unditer2(t) == 137bksl-nl print("tests réussis")bksl-nl bksl-nlbksl-nl

🐍 Script Python
def somme_max_iter2(t):
    """Renvoie la somme maximale dans un triangle de nombres
    t qui est une liste de listes"""    
    n = len(t)
    s = [t[n - 1][j] for j in range(n)]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1):
            s[j] = t[i][j] + max(s[j], s[j + 1])
    return s[0]

def test_somme_max_iter2():
    t = [[3], [40, 38], [34, 31, 33], [3, 4, 22, 25], [42, 24, 41, 38, 5]]
    assert somme_max_iter2(t) == 137
    print("tests réussis")

Reconstruction d'une solution⚓︎

Exercice 8

Dans cet exercice, on met en oeuvre l'étape 3 caractéristique de la programmation dynamique : la construction d'une somme réalisant la somme maximale dans le problème de la somme maximale dans un triangle.

Comme pour le problème du rendu de monnaie, on remplit d'abord le tableau (ici une liste de listes) des sommes maximales \(s(i, j)\) pour tous les sous-problèmes. Pour cela, on procède par programmation dynamique itérativement ou récursivement avec mémoïsation, comme dans les exercices 6 et 7. Une fois le tableau rempli on le parcourt du haut (le sommet du triangle) vers le bas (la dernière ligne). On initialise la somme maximale avec le sommet du triangle et à chaque changement de ligne on sélectionne la sous-somme maximale entre celle du sous-problème de sommet juste en dessous et celle du sous-problème de sommet en bas à droite.

Question 1

On reprend l'exemple du triangle 1.

alt

On donne ci-dessous un tableau avec dans chaque case correspondant à une position (ligne \(i\), colonne \(j\)) dans le triangle 1, un couple constitué de :

  • \(t(i,j)\) le nombre à cette position
  • puis \(s(i,j)\) la sous-somme maximale du sous-triangle dont \(t(i,j)\) est le sommet.
i / j 0 1 2 3 4
0 (3, 137)
1 (40, 134) (38, 134)
2 (34,79) (31,94) (33,96)
3 (3,45) (4,45) (22,63) (25,63)
4 (42,42) (24,24) (41,41) (38,38) (5,5)

  1. Reconstituer une somme réalisant le maximum \(137\).

  2. Existe-t-il plusieurs façons d'écrire la somme maximale ?

En suivant l'algorithme décrit en préambule, on peut déterminer plusieurs sommes réalisant le maximum \(137\) :

  • \(137 = 3 + 40 + 31 + 22 + 41\)
  • \(137 = 3 + 38 + 33 + 22 + 41\)
  • \(137 = 3 + 38 + 33 + 25 + 38\)

Question 2

  1. On suppose qu'on a déjà calculé les valeurs des sommes maximales pour tous les sous-problèmes. Quelle est la complexité en temps de la reconstruction d'une somme maximale ? Et la complexité du calcul de la valeur somme maximale puis de la reconstruction d'une somme maximale ?
  2. Quelle est la complexité de l'espace supplémentaire nécessaire pour reconstruire une somme maximale ?
  1. Si on a déjà calculé les valeurs des sommes maximales pour tous les sous-problèmes alors on peut reconstruire une somme maximale avec un choix par ligne en redescendant dans le tableau mémorisant toutes les solutions \(s(i,j)\) des sous-problèmes depuis le sommet jusqu'à la dernière ligne. La complexité en temps de la reconstruction est donc linéaire, en \(O(n)\) par rapport au nombre \(n\) de lignes. Comme le calcul de la valeur de la somme maximale est en \(O(n^{2})\), il domine celui de la reconstruction et donc la complexité en temps du calcul puis de la reconstruction de la somme maximale est quadratique, en \(O(n^{2})\).
  2. Pour reconstruire une somme maximale, on a besoin des résultats de tous les sous-problèmes donc d'une complexité en espace supplémentaire en \(O(n^{2})\).

Question 3

Compléter le code de la fonction somme_max_iter_solution qui prend en paramètre un triangle de nombres et qui renvoie un couple constitué de la valeur de la somme maximale et d'une liste de nombres du triangle réalisant ce maximum.

###
def sommepy-undmaxpy-unditerpy-undsolution(t):bksl-nl """Renvoie un couple constitué de :bksl-nl - la somme maximale dans un triangle de nombres t qui est une liste de listesbksl-nl - une liste de nombres réalisant cette somme maximale""" bksl-nl n = len(t)bksl-nl s = [[0 for py-und in range(len(t[i]))] for i in range(n)]bksl-nl # initialisation de la dernière lignebksl-nl for j in range(n):bksl-nl s[n - 1][j] = t[n - 1][j]bksl-nl # on remonte de la dernière ligne jusqu'au sommet du trianglebksl-nl for i in range(n - 2, -1, -1):bksl-nl for j in range(len(s[i])):bksl-nl s[i][j] = t[i][j] + max(s[i + 1][j], s[i + 1][j + 1])bksl-nl # ici s contient les solutions de tous les sous-problèmesbksl-nl # on stocke chaque terme d'une somme maximale dans la liste solbksl-nl # on initialise sol avec le sommet du trianglebksl-nl sol = [t[0][0]]bksl-nl # on redescend du sommet du triangle jusqu'à la dernière lignebksl-nl j = 0bksl-nl # à compléterbksl-nl ...bksl-nl return (s[0][0], sol)bksl-nlbksl-nldef testpy-undsommepy-undmaxpy-unditerpy-undsolution():bksl-nl t = [[3], [40, 38], [34, 31, 33], [3, 4, 22, 25], [42, 24, 41, 38, 5]]bksl-nl assert sommepy-undmaxpy-unditerpy-undsolution(t) == (137, [3, 40, 31, 22, 41])bksl-nl print("tests réussis")bksl-nl bksl-nlbksl-nl

🐍 Script Python
def somme_max_iter_solution(t):
    """Renvoie un couple constitué de :
    - la somme maximale dans un triangle de nombres t qui est une liste de listes
    - une liste de nombres réalisant cette somme maximale"""    
    n = len(t)
    s = [[0 for _ in range(len(t[i]))] for i in range(n)]
    # initialisation de la dernière ligne
    for j in range(n):
        s[n - 1][j] = t[n - 1][j]
    # on remonte de la dernière ligne jusqu'au sommet du triangle
    for i in range(n - 2, -1, -1):
        for j in range(len(s[i])):
            s[i][j] = t[i][j] + max(s[i + 1][j], s[i + 1][j + 1])
    # ici s contient les solutions de tous les sous-problèmes
    # on stocke chaque terme d'une somme maximale dans la liste sol
    # on initialise sol avec le sommet du triangle
    sol = [t[0][0]]
    # on redescend du sommet du triangle jusqu'à la dernière ligne
    j = 0
    for i in range(n - 1):
        if s[i + 1][j + 1] > s[i + 1][j]:            
            sol.append(t[i + 1][j + 1])
            j = j + 1
        else:
            sol.append(t[i + 1][j])
    return (s[0][0], sol)

def test_somme_max_iter_solution():
    t = [[3], [40, 38], [34, 31, 33], [3, 4, 22, 25], [42, 24, 41, 38, 5]]
    assert somme_max_iter_solution(t) == (137, [3, 40, 31, 22, 41])
    print("tests réussis")