Modèles de chemins (Prog. dyn): Weighted Interval Scheduling (ordonnancement d'intervalles pondérés)

Cette vidéo explique le modèle de chemin ou programme dynamique pour le problème d'ordonnancement d'intervalles (weighted interval scheduling).

Pour retrouver le contexte de l'application réelle en astronomie:    • Modèles de chemins (Programmation dynamiqu...  

Plan général du chapitre sur la programmation dynamique:    • Programmation dynamique: Plan du chapitre ...  

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

Exercices corrigés:
Alignement de séquences:    • Modèles de chemins (Programmation dynamiqu...  

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

Pré-requis:
Pb de chemins et ordre topologique:    • Graphes orientés sans circuits: ordre topo...  
Bellman-Ford:    • 1- Algorithme de Bellman-Ford: Application...  

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