Programmation dynamique⚓︎
Intentions⚓︎
Introduction
Il existe de nombreuses approches algorithmiques pour résoudre un problème donné en se basant sur la résolutions de ses sous-problèmes. En Première, nous avons parlé de l'approche gloutonne et nous avons déjà vu cette année l'approche basée sur la méthode « Diviser pour régner ».
Dans ce chapitre, nous abordons une nouvelle approche algorithmique : la programmation dynamique.
Celle-ci consiste en une mémoïsation des résultats déjà calculés afin de ne pas avoir à recalculer plusieurs fois les mêmes données.
Déroulé
On propose le déroulé suivant :
- un notebook pour retravailler les approches gloutonnes et récursives ;
- un notebook traitant du rendu de monnaie pour introduire la programmation dynamique ;
- un point de cours interactif présentant deux applications classiques de la programmation dynamique : l'algorithme de Bellman-Ford et le problème de l'alignement de séquences ADN.
Cours⚓︎
Exercices (Toto le robot)
- Accès via Capytale : dans la zone
Titrede la bibliothèque de Capytale, taper la phrase ci-dessous :
NSI Terminale Partie 2 Chapitre 3 Toto le robot
- Accès sans Capytale : télécharger le notebook dans la rubrique Ressources ci-dessous
Exercices (rendu de monnaie)
- Accès via Capytale : dans la zone
Titrede la bibliothèque de Capytale, taper la phrase ci-dessous :
NSI Terminale Partie 2 Chapitre 3 Rendu monnaie
- Accès sans Capytale : télécharger le notebook dans la rubrique Ressources ci-dessous