Cours : Dynamic Programming in OR

Aperçu des sections

Dynamic Programming Open Course

Tout replier Tout déplier
Contributors : Nadia Brauner (Université Grenoble Alpes), Hadrien Cambazard (Grenoble INP), Nicolas Catusse (Grenoble INP)

Contact : Hadrien Cambazard
- It all began...
- One idea, one story: why is dynamic programming dynamic ? Page
  
  Consulter
- Richard Bellman, the theory of dynamic programming, 1954 Fichier
- Richard Bellman, on a routing problem, 1956 Fichier
- Vous devez être inscrit dans le cours pour avoir accès à l'éditeur des exercices de programmation (une fois connecté, si vous voyez encore ce message, utilisez la roue dentée en haut à droite).
- Course supports
- Chapter 6, Dynamic programming URL
  
  Consulter
  
  In the book Algorithms by Dasgupta, Papadimitriou and Vazirani
  If you never studied the principles of Dynamic Programming (DP) before, you can read this document.
- Cours rédigé de la partie Modèle de chemins Livre
- Programmation dynamique ou l'art de faire des modèles de chemins (vidéos courtes) Page
- Transparents de cours de programmation dynamique (en français) Fichier
  
  Consulter
- Slides on Dynamic Programming (in english) Fichier
- Annonces Forum
Exercises and activities
- Pour programmer sur caseine, il est recommandé d'installer le plugin caseine pour Eclipse pour travailler depuis l’IDE Eclipse ou d'installer l'extension VPL de VSCode ou Codium. Il vous permettront de travailler dans votre IDE : récupérer le code et la description de l'exercice de programmation, lancer des évaluations depuis votre IDE ou pousser votre code sur caseine.
- Self training, le forgeron
- Knapsack (Java) Virtual programming lab
  
  Recevoir une note
- The lab Knapsack is a complete example so students can get familiar with the framework for implementing dynamic programs. It matches the notations and example of the Dasgupta, Papadimitriou, Vazirani book. A simple object model is introduced for the representation of the data (usually two classes) as well as a class PdynSolver.java representing the dynamic program by its states (i.e the DP tables are stored as attributes). The purpose is to get the students familiar with object models that are required for more complex subjects where a model for the data becomes necessary. This framework is also used in the labs Kukulkan and Load Balancing.
- Knapsack (Python) Virtual programming lab
- Apply the dynamic programming algorithm for the knapsack Test
  
  Recevoir une note
- Hôtel (exercice avec corrections) Page
  
  Consulter
- Hotels (Java) Virtual programming lab
  
  Recevoir une note
- Hotels (Python3) Virtual programming lab
  
  Recevoir une note
- Rendu de monnaie (exercice avec corrections) Page
  
  Consulter
- Giving change (Java) Virtual programming lab
  
  Recevoir une note
- Implementation in Java of a slightly different version of the preceding exercise. (with complexity analyser)
- Subset Sum (Python) Virtual programming lab
  
  Recevoir une note
- Similar to Giving Change exercise.
- Poste de travail (exercice avec corrections) Page
  
  Consulter
- Work stations (Python) Virtual programming lab
- Work stations (Java) Virtual programming lab
- Sac-à-dos multi-objet (exercice avec corrections) Page
  
  Consulter
  
  Extension du problème de sac-à-dos. Si vous avez bien compris l’exercice de rendu de monnaie, celui-ci ne devrait pas poser de problème
  Extension of the knapsack problem. If you understood well the exercise Giving Change, this one should not be difficult.
- Minimum sum (Java) Virtual programming lab
  
  Recevoir une note
- Similar to Giving Change exercise. (with complexity analyser)
- Kukulkan (Java) Virtual programming lab
  
  Recevoir une note
- Load Balancing (Java) Virtual programming lab
  
  Recevoir une note
- Load Balancing (Python3) Virtual programming lab
  
  Recevoir une note
- Variation sur le problème du sac-à-dos avec implémentation du backtrack.
- Keeping Water**** Virtual programming lab
- Cutting Cloth** (Java) Virtual programming lab
- Cutting Cloth (Python3) Virtual programming lab
  
  Recevoir une note
- Cutting Cloth (One possible answer from Hadrien Cambazard) Page
  
  Consulter
- Production System*** Virtual programming lab
- Christmas Dynamic Challenge *** Test
  
  Consulter Recevoir une note

Aperçu des sections

Dynamic Programming Open Course

Exercises and activities