Loading [MathJax]/extensions/Safe.js

Question 1 :

On suppose que le calcul de total_max est effectué grâce à l'implémentation récursive comme indiqué ci-dessus.

Pour un certain calendrier cal_x, on effectue l'appel de fonction total_max(cal_x, 73). Quels sont les deux appels récursifs que cela va entraîner ?

Solution

Cet appel va entraîner les appels récursifs à total_max(cal_x, 72) et à total_max(cal_x, 69).

Solution

Voici maintenant l'arbre des appels récursifs pour n = 14 : on constate que certains appels récursifs identiques sont effectués plusieurs fois. Autrement dit, les problèmes de taille plus petite sont résolus plusieurs fois, ce qui explique le coût exorbitant de cet algorithme. Par exemple le problème du calcul total_max(cal, 6) est résolu sept fois ! On refait donc sept fois la même chose.

Ce qu'on vient de dire serait encore pire si on résolvait total_max(cal, 100). On peut ainsi montrer que l'appel de fonction total_max(cal, 100) nécessite 108 654 474 368 651 appels récursifs en tout, ce qui signifie que ce n'est pas exécutable en pratique (temps de calcul de plusieurs dizaines d'heures).

Question 3 :

En augmentant petit à petit la taille TAILLE CALENDRIER du calendrier aléatoire, déterminer à partir de quelle taille de calendrier l'implémentation récursive de la fonction total_max n'est plus pertinente.

Entrée[ ]:
Entrée[ ]:
Solution

On constate qu'à partir d'une taille de calendrier égale à 48 environ, le temps de calcul est de l'ordre de quelques secondes. Puis si la taille de calendrier augmente encore (par exemple 55), le temps de calcul devient rapidement problématique.

Lorsqu'on cherche à résoudre un problème de taille n :

  • en résolvant récursivement des sous-problèmes de taille inférieure,
  • pour lequel les sous-problèmes sont présents de nombreuses fois dans l'arbre des appels récursifs,

la programmation dynamique consiste à modifier l'algorithme récursif pour ne pas résoudre pusieurs fois un même sous-problème.

On utilise pour cela une structure de données qui mémorise les résultats des sous-problèmes au fur et à mesure : cela évite de résoudre à nouveau un sous-problème déjà rencontré.

Remarque : le problème initial a parfois une taille en deux dimensions, par exemple (nb_lignes, nb_colonnes), voir par exemple l'exercice de la cueillette de fraises ou l'alignement de séquences.

Question 4 :

Si on utilise la programmation dynamique, l'arbre des appels récursifs se transforme en un graphe beaucoup plus petit puisque chaque étiquette n'est alors présente qu'une seule fois. Le graphe associé à total_max(cal, 14) a été commencé ci-dessous. Le recopier puis compléter les arcs manquants.

Solution

II : programmation dynamique – version récursive + mémoïsation

La version récursive avec mémoïsation consiste à résoudre les sous-problèmes à partir de l'algorithme récursif en rajoutant une structure de données (tableau ou dictionnaire) qui va mémoriser les résultats des différents appels au fur et à mesure de leurs calculs.

Plus précisément, lorsqu'on traite un appel récursif :

  • si le résultat est déjà mémorisé :

    • on le lit dans la mémoire,

  • si le résultat n'est pas déjà mémorisé :

    • on le calcule en utilisant la relation de récursivité ou le cas de base,
    • une fois calculé on le sauvegarde dans la mémoire,

  • on renvoie le résultat.

Sur notre exemple, les sous-problèmes sont indexés par le nombre entier n : nous pouvons donc choisir comme structure de données un tableau memoire indexé par n. Ainsi memoire[n] contiendra le total_max(cal, n).

Enfin, pour savoir si un résultat est mémorisé, nous initialiserons ce tableau memoire avec des valeurs égales à None :

  • si memoire[n] is None, on sait que le résultat correspondant à n n'a pas encore été calculé (ni mémorisé).
  • si memoire[n] is not None, on sait que le résultat correspondant à n a déjà été calculé (et mémorisé).

Question 5 :

Compléter le code de la fonction total_max ci-dessous pour qu'elle corresponde à une implémentation récursive avec mémoïsation.

Entrée[ ]:
Entrée[ ]:

Points de vigilance concernant l'implémentation :

  • Le tableau memoire est passé en argument de la fonction récursive pour être accessible depuis chacun des appels récursifs.

  • Le tableau memoire est initialisé à l'extérieur de la fonction récursive, avant l'appel principal, sinon (placée à l'intérieur de la fonction total_prix) elle serait ré-initialisée à chaque appel récursif.

  • Le tableau memoire est complété au fur et à mesure car les tableaux python (type list) sont mutables et une mutation à l'intérieur d'une fonction se répercute à l'extérieur.

Question 6 :

Vérifier qu'on peut désormais appeler la fonction total_max avec de grands calendriers : le temps d'exécution reste rapide.

Entrée[ ]:
Solution

Pour des calendriers de taille 1000 ou 2000, le calcul est quasiment instantané ...

III : programmation dynamique – version itérative (bottom-up)

La version itérative (bottom-up) consiste à d'abord partir des sous-problèmes situés en bas de l'arbre des appels récursifs pour remonter vers le problème situé à la racine. Autrement dit on résout d'abord les sous-problèmes de taille plus petite avant de résoudre ceux de taille plus grande.

Plus précisément on effectue les calculs pour n = 0, puis n = 1, puis n = 2, puis n = 3 etc. Il est donc naturel d'utiliser un algorithme itératif pour remplir le tableau memoire.

On va donc initialiser un tableau memoire avec des None puis on va le parcourir de gauche à droite. Pour chaque indice i, on pourra - grâce aux valeurs déjà mémorisées memoire[i - 1] et memoire[i - 4] - calculer la valeur de total_prix(cal, i) puis la memoriser à son tour dans memoire[i].

Par ailleurs, pour éviter des détails techniques, on se restreint au cas où on cherche à résoudre le problème pour n > 3 (pour n <= 3 le problème est trivial).

Question 7 :

Compléter le code de la fonction total_max ci-dessous pour qu'elle corresponde à une implémentation itérative.

Entrée[ ]:
Entrée[ ]:

Question 8 :

Vérifier qu'avec cette implémentation on peut également appeler la fonction total_max avec de grands calendriers : le temps d'exécution reste rapide.

Entrée[ ]:
Solution

Pour des calendriers de taille 1000 ou 2000, le calcul est quasiment instantané ...

Chargement de Basthon...