Cette vidéo présente le plan de la séquence sur la programmation dynamique en dévoilant les choix pédagogiques. Elle peut servir d'introduction mais aussi, et surtout, de prise de recul.

Pré-requis:
Chemins et ordre topologique:    • Graphes orientés sans circuits: ordre...  
Bellman-Ford:    • 1- Algorithme de Bellman-Ford: Applic...  

A) Modèles de chemins:
Un problème illustratif, le sac à dos (vidéo 1 - 8 min) :    • 1- Modèles de chemins (Programmation ...  
Un modèle de chemin pour le sac à dos (vidéo 2 - 11 min) :    • 2- Modèles de chemins (Programmation ...  
Équation de récurrence ou équation de Bellman et algorithme (vidéo 3 - 15 min) :    • 3- Modèles de chemins (Programmation ...  

Exercices corrigés:
Alignement de séquences:    • Modèles de chemins (Programmation dyn...  
Ordonnancement d'intervalles pondérés:    • Modèles de chemins (Prog. dyn): Weigh...  

B) Au-delà des chemins
Multiplication de matrices:    • Programmation dynamique: multiplicati...  

Liens:
Notre plateforme : https://moodle.caseine.org/
Le cours sous caseine: https://moodle.caseine.org/course/vie...
Algorithms by Dasgupta, Papadimitriou and Vazirani : https://www.cs.berkeley.edu/~vazirani...