Ce cours de programmation dynamique pour la RO est un cours participatif, ouvert et partagé.

Compétences
L’objectif est de savoir mettre en œuvre un algorithmes de programmation dynamique pour des problèmes de Recherche Opérationnelle :
  • Décrire le Modèle de chemin
  • Ecrire la formule de récurrence
  • Proposer un algorithme de résolution (itératif)
  • Reconstruire la solution optimale obtenue par backtrack
  • Programmer l'algorithme et le backtrack
  • Connaitre les principaux modèles de résolution pour les problèmes classiques : plus court chemin, Sac-à-dos et extension...
  • Connaitre les grands problèmes de RO qui se résolvent avec de la DP : maintenance, ordonnancement sur machine parallèle, gestion de couts fixes...
Contenu
Il propose en particulier :
  • un cours rédigé qui s'appuie sur des vidéo youtube courtes;
  • des exercices avec corrections détaillées;
  • des activités de programmation auto-évaluées (l'étudiant peut lancer les tests prédéfinis) avec estimation expérimentale de la complexité de la fonction proposée par l'étudiant. Cette fonctionnalité permet de différentier non seulement un algorithme pseudo polynomial d'une énumération complète mais aussi d'identifier des heuristiques, par exemple à base de boucles for imbriquées qui permettent juste de passer les tests sans résoudre le problème en général.

  • Modèle de chemin et application au problème du sac-à-dos
  • Exercices résolus de DP en RO
    • Autour du sac-à-dos : sac-à-dos entier, subset sum, rendu de monnaie, équilibrage de charge
    • ordonnancement d'intervalles
    • Maintenance
    • Investissement
  • Exercices résolus de DP en Informatique pour acquérir de l'aisance de modélisation
    • multiplication de matrices
    • Alignement de séquences
  • Activités du programmation
    • Autour du sac-à-dos
    • Découpe
    • Keeping water
    • Hotels
    • Production systems