B. Programmation dynamique

• Cours :
  • Programmation dynamique
• Vidéos explicatives :
  • Motivations de la programmation dynamique : de la limite des approches gloutonnes et diviser pour régner
  • Chevauchement de sous-problèmes : exemple
  • Problème à sous-structure optimale
• Activités exploratoires :
  • Le retour du sac à dos
• TP :
  • Problèmes classiques en programmation dynamique solution (à ne pas ouvrir en TP mais chez soi !)
• Objectifs d'apprentissage :
  • cerner les limitations des algorithmes gloutons dans certaines situations
  • justifier l'optimalité d'une sous-structure d'un problème en programmation dynamique
  • coder la résolution par tableau (approche récursive)
  • coder la résolution par la mémoïsation (approche récursive)