Corso: Dynamic Programming in OR

Indice degli argomenti

Dynamic Programming Open Course

Minimizza tutto Espandi tutto
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 ? Pagina
  
  Visualizzare
- Richard Bellman, the theory of dynamic programming, 1954 File
- Richard Bellman, on a routing problem, 1956 File
- 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
  
  Visualizzare
  
  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 Libro
- Programmation dynamique ou l'art de faire des modèles de chemins (vidéos courtes) Pagina
- Transparents de cours de programmation dynamique (en français) File
  
  Visualizzare
- Slides on Dynamic Programming (in english) File
- 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
  
  Ricevere una valutazione
- 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 Quiz
  
  Ricevere una valutazione
- Hotel (exercise with corrections) Pagina
  
  Visualizzare
- Hotels (Java) Virtual programming lab
  
  Ricevere una valutazione
- Hotels (Python3) Virtual programming lab
  
  Ricevere una valutazione
- Giving change (exercise with corrections) Pagina
  
  Visualizzare
- Giving change (Java) Virtual programming lab
  
  Ricevere una valutazione
- Implementation in Java of a slightly different version of the preceding exercise. (with complexity analyser)
- Subset Sum (Python) Virtual programming lab
  
  Ricevere una valutazione
- Similar to Giving Change exercise.
- Work stations (exercise with corrections) Pagina
  
  Visualizzare
- Work stations (Python) Virtual programming lab
- Work stations (Java) Virtual programming lab
- Sac-à-dos multi-objet (exercice avec corrections) Pagina
  
  Visualizzare
  
  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
  
  Ricevere una valutazione
- Similar to Giving Change exercise. (with complexity analyser)
- Kukulkan (Java) Virtual programming lab
  
  Ricevere una valutazione
- Load Balancing (Java) Virtual programming lab
  
  Ricevere una valutazione
- Load Balancing (Python3) Virtual programming lab
  
  Ricevere una valutazione
- 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
  
  Ricevere una valutazione
- Cutting Cloth (One possible answer from Hadrien Cambazard) Pagina
  
  Visualizzare
- Production System*** Virtual programming lab
- Christmas Dynamic Challenge *** Quiz
  
  Visualizzare Ricevere una valutazione

Indice degli argomenti

Dynamic Programming Open Course

Exercises and activities