Programmer de manière dynamique
- Fiche de cours
- Quiz et exercices
- Vidéos et podcasts
- Comprendre la notion de programmation dynamique.
- Programmer de manière dynamique.
- La programmation dynamique consiste à diviser le problème à résoudre en sous-problèmes et à stocker les résultats de ces sous-problèmes afin de reconstruire la solution du problème initial.
- En programmation dynamique, le stockage des résultats intermédiaires permet d’optimiser la résolution du problème. Cette démarche s’appelle la mémoïsation.
- Utiliser la récursivité en Python.
- Résoudre un problème avec un algorithme glouton.
- Utiliser la méthode « diviser pour régner ».
La programmation dynamique est un principe algorithmique qui permet d’optimiser la résolution des problèmes.
En pratique, il s’agit de stocker les résultats des sous-problèmes au fur et à mesure pour éviter d’avoir à les résoudre plusieurs fois et les réutiliser facilement. Ce principe de stockage s’appelle la mémoïsation.
L’un des avantages de la programmation dynamique sur la méthode « diviser pour régner » vient de la mémoïsation. Chaque sous-problème n’est traité qu’une seule fois avec la programmation dynamique. Ce n’est pas forcément le cas avec la méthode « diviser pour régner ».
La suite de Fibonacci est la suite de nombres entiers :
1 – 1 – 2 – 3 – 5 – 8 – ...
En pratique, on obtient un élément de la suite en additionnant les deux termes précédents.
Par exemple, après 5 et 8, on obtient le nombre 13 car 5 + 8 = 13.
Cette suite peut naturellement être programmée récursivement. Par exemple, la fonction suivante fibo_rec(n) implémente le calcul du (n+1)-ème terme de la suite de Fibonacci avec la récursivité.
| Python | Explication |
| def fibo_rec(n): | On définit la fonction fibo_rec. |
| if n < 2 | Si n = 0 ou n = 1, alors |
| return 1 | on retourne 1. |
| else: | Sinon |
| return fibo(n–1) + fibo(n–2) | on retourne la somme des deux termes précédents fibo(n). |
Cette fonction est algorithmiquement correcte. En pratique, elle est cependant peu efficace puisque plusieurs valeurs de la suite sont calculées plusieurs fois.
Voici l’appel de cette fonction sur Python Tutor pour n = 10.
L’exécution de ce programme se fait en 710 étapes, ce qui est beaucoup.
Pour optimiser le calcul des termes de la suite de Fibonacci, on peut utiliser la programmation dynamique.
On écrit pour cela la fonction suivante fibo_dyn(n), qui stocke au fur et à mesure les termes de la suite dans le tableau suite.
| Python | Explication |
| def fibo_dyn(n): | On définit la fonction fibo_dyn |
| suite = [1]*(n+1) | On crée un tableau suite de taille n+1 qui ne contient que des 1. |
| for i in range(2, n+1): | Pour i qui va de 2 à n, |
| suite[i] = suite[i–1] + suite[i–2] | On affecte au (i+1)-ème élément du tableau suite la somme des deux termes précédents (i et i–1). |
| return suite[n] | on retourne le dernier élément du tableau suite. |
Voici l’appel de cette fonction sur Python Tutor pour n = 10.
L’exécution de ce programme se fait en 25 étapes. L’approche dynamique avec mémoïsation optimise le calcul des termes de la suite de Fibonacci.
L’approche gloutonne de ce problème (vue en première) consiste à choisir à chaque étape la pièce ou le billet de plus grande valeur qui ne dépasse pas la somme restant à rendre. Cette méthode n’est pas optimale puisque l’on n’est pas certain d’avoir le moins de pièces et de billets possibles.
Si on considère le système monétaire [1, 7, 8] et la somme 21 à rendre, l’approche gloutonne donnerait le rendu suivant avec 7 pièces/billets : 8 – 8 – 1 – 1 – 1 – 1 – 1.
Ce n’est pas une solution optimale puisque l’on pourrait rendre cette somme avec 7 – 7 – 7.
Une première optimisation consiste à tout d’abord s'intéresser uniquement au nombre de pièces/billets pour le rendu.
Cette démarche est récursive :
- Si la somme à rendre vaut 0, alors il faut 0 pièce/billet pour rendre la monnaie.
- Si la somme à rendre est strictement supérieure à 0, alors le nombre de pièces pour le rendu optimal de cette somme est le minimum, pour chaque pièce/billet p du système monétaire, de la somme de 1 (qui correspond à la pièce/billet prise) et du nombre de pièces pour le rendu optimal de somme – p.
Dans le système monétaire [1, 2, 3], on étudie la pièce/billet 2 pour une somme à rendre qui vaut 7. On a ici utilisé 1 pièce de 2, le nombre de pièces/billets à rendre vaut donc 1 + les autres pièces qui permettront de rendre 7 – 2 = 5.
En Python, cela donne la fonction nb_rendu(pieces, somme) qui prend en paramètres le système monétaire utilisé pieces et la somme à rendre somme.
| Python | Explication |
| def nb_rendu(pieces, somme): | On définit la fonction nb_rendu. |
|
if somme == 0: return 0 |
Si la somme est nulle, il faut 0 pièce/billet pour le rendu. |
| else: | Sinon, |
| nb_pieces = somme | on affecte somme à la variable nb_pieces (pire cas où le rendu ne se fait qu’avec des pièces de 1. S’il faut par exemple rendre 7, on aura nb_pieces = 7, ce qui signifie qu’il faut 7 pièces/billets de 1.) |
| for p in pieces: | Pour chaque pièce p dans le système monétaire pieces, |
| if p <= somme: | si p est inférieur à la somme qui est à rendre, |
| n = 1 + nb_rendu(pieces, somme–p) |
on affecte à n (nombre
intermédiaire de pièces) la somme
de 1 et du rendu pour une somme
de somme–p. (on a utilisé 1 pièce/billet, il ne reste donc plus qu’à rendre somme–p.) |
| nb_pieces = min(nb_pieces, n) |
on affecte à la variable nb_pieces le minimum
de n et
de nb_pieces (pire cas
où on ne rend que des pièces
de 1). Ce minimum correspond au minimum de pièces recherchées. |
| return nb_pieces | Enfin, on retourne nb_pieces. |
Voici l’appel de cette fonction sur Python Tutor pour pieces = [1, 2, 5] et pour somme = 7.
L’exécution de ce programme renvoie 2. Ainsi il faut deux pièces pour rendre la monnaie sur une somme de 7. Néanmoins cela se fait en 662 étapes, ce qui est beaucoup, d’autant que le rendu se fait facilement avec 2 et 5.
Pour optimiser la fonction précédente, on peut stocker les rendus des sommes intermédiaires dans un tableau rendu.
En Python, cela donne la fonction nb_rendu_dyn(pieces, somme) qui prend en paramètres le système monétaire utilisé pieces et la somme à rendre somme.
| Python | Explication |
| def nb_rendu_dyn(pieces, somme): | On définit la fonction. |
| rendu = [0]*(somme + 1) |
On crée un tableau rendu de
taille somme+1 qui ne contient que
des 0. (On stocke le rendu d'un montant égale à 0 jusqu'à somme. Il y a donc somme+1 montants.) |
| for s in range(1, somme + 1): | Pour s allant de 1 à somme, |
| rendu[s] = s | on affecte s au (s+1)-ème élément du tableau rendu. |
| for p in pieces: | Pour chaque pièce p dans le système monétaire pièces, |
| if p <= s: | si la pièce/billet p est inférieure à la somme à rendre, |
|
rendu[s] =
min(rendu[s], 1 + rendu[s – p]) |
on affecte au (s+1)-ème
élément du
tableau rendu
le minimum de rendu[s] et de 1 + rendu[s–p]. (on prend 1 pièce et on étudie le rendu sur le reste.) |
| return rendu[somme] | on retourne le dernier élément du tableau rendu (pour s qui vaut somme). |
Voici l’appel de cette fonction sur Python Tutor pour pieces = [1, 2, 5] et pour somme = 7.
On obtient le même résultat qu’avec la fonction précédente (il faut 2 pièces/billets pour rendre la somme 7), mais l’exécution de ce programme se fait en moins d’étapes (88 étapes).
Il reste ensuite à finaliser cette fonction pour obtenir la liste des pièces/billets nécessaires pour faire le rendu optimal.
En Python, on crée la fonction rendu_dyn(pieces, somme) qui prend en paramètres le système monétaire utilisé pieces et la somme à rendre somme.
Cette fonction renvoie le tableau des pièces/billets utilisés pour le rendu.
Dans cette fonction, on stockera :
- le nombre de pièces/billets des rendus intermédiaires dans le tableau rendu ;
- et la liste des pièces/billets nécessaires à ces rendus dans le tableau solution.
| Python | Explication |
| def rendu_dyn(pieces, somme): | On définit la fonction. |
|
rendu = [0]*(somme + 1) solution = [[]]*(somme + 1) |
On crée un tableau rendu de
taille somme+1 qui ne contient que
des 0. On crée également un tableau solution de taille somme+1 qui ne contient que des tableaux vides []. Ce tableau contiendra les pièces/billets nécessaires pour chaque rendu intermédiaire. |
| for s in range(1, somme + 1): | Pour s allant de 1 à somme, |
|
rendu[s] = s solution[s] = [1]*s |
on affecte s au (s+1)-ème élément du tableau rendu et [1]*s au (s+1)-ème élément du tableau solution. |
| for p in pieces: | Pour chaque pièce p dans le système monétaire pieces, |
| if p <= s: | si la pièce/billet p est inférieure à la somme à rendre, |
| if 1 + rendu[s–p] < rendu[s]: | si 1+rendu[s-p] est inférieur à rendu[s], alors |
|
rendu[s] = 1 + rendu[s–p] solution[s] = solution[s–p]+[p] |
On affecte 1+rendu[s–p] au (s+1)-ème élément du tableau rendu et on affecte solution[s–p]+[p] au (s+1)-ème élément du tableau solution. (si on prend la pièce p, on ajoute 1 à rendu et [p] aux pièces rendues) |
| return solution[somme] | on retourne le dernier élément du tableau rendu (pour s qui vaut somme) |
Voici l’appel de cette fonction sur Python Tutor pour pieces = [1, 2, 5] et pour somme = 7.
Le rendu optimal de 7 avec le système monétaire [1, 2, 5] est donc 7 = 5 + 2.
Évalue ce cours !
Des quiz et exercices pour mieux assimiler sa leçon
La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.
Des exercices variés pour ne pas s’ennuyer
Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !
Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.
Des quiz pour une évaluation en direct
Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.
myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.
Des vidéos et des podcasts pour apprendre différemment
Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.
Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !
Des podcasts pour les révisions
La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.
Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.
Des vidéos de cours pour comprendre en image
Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !
Fiches de cours les plus recherchées
NSI
Étudier la complexité mémorielle
NSI
Rechercher un motif dans un texte : l'algorithme de Boyer-Moore
NSI
Comprendre les requêtes HTTP et la réponse serveur
NSI
Comprendre la notion de réseau et de protocole
NSI
Comprendre les protocoles de la couche physique
NSI
Comprendre les protocoles de la couche liaison dans un réseau local
NSI
Comprendre les protocoles de la couche réseau
NSI
Comprendre les protocoles de la couche transport
NSI
Décrire des protocoles de récupération de paquets
NSI
Affecter une valeur, utiliser une séquence d'actions
NSI
Utiliser des structures conditionnelles
NSI
Utiliser des boucles
Fermer
Accédez gratuitement à
