Схема на раздела

  •    


    • Dynamic Programming

    • Parcours à distance : Programmation dynamique (lien) URL

    • Skills

      L’objectif est de savoir mettre en œuvre un algorithmes de programmation dynamique pour des problèmes de Recherche Opérationnelle en particulier le sac-à-dos et ses extensions.

      • Be able to write a recurrence formula and the basis cases in dynamic programming
      • Know the algorithm for the knapsack and its extensions (larger subset of coins, integer knapsack)

    • Course ressources

    • Chapter 6, Dynamic Programming URL
      Обучаваните трябва
      Преглеждане

      From the book Algorithms by Dasgupta, Papadimitriou and Vazirani

      Si vous n’avez jamais vu les principes de la Programmation Dynamique (DP),  lisez ce document.

    • Transparents du cours de programmation dynamique Файл
      Обучаваните трябва
      Преглеждане
    • [SHARED] Des vidéos courtes reprennent les notions du cours en détail. Shared Activity
    • One idea, one story: why is dynamic programming dynamic ? Страница
      Обучаваните трябва
      Преглеждане
    • Richard Bellman, on a routing problem, 1956 Файл
    • Richard Bellman, the theory of dynamic programming, 1954 Файл

    • 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

    • Giving change (exercise with corrections) Страница
      Обучаваните трябва
      Преглеждане

      Ce premier exercice d’application est présenté avec un corrigé détaillé (vidéo, présentation ou description textuelle).

    • Giving change Virtual programming lab
      Обучаваните трябва
      Получаване на оценка

    • Implementation in Java of a slightly different version of the preceeding exercice. Videos help you if needed.

    • Similar to giving change.

    • Sac-à-dos multi-objet Страница
      Обучаваните трябва
      Преглеждане

      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

    • Corrigé détaillé du Sac-à-dos multi-objet (en français) Файл
      Обучаваните трябва
      Преглеждане
    • Investments Страница
      Обучаваните трябва
      Преглеждане
    • Investments MIP video Файл
      Обучаваните трябва
      Преглеждане
    • Investments DP Video Файл
      Обучаваните трябва
      Преглеждане
    • Maintenance Страница
      Обучаваните трябва
      Преглеждане
    • Apply the dynamic programming algorithm for the knapsack Тест
      Обучаваните трябва
      Получаване на оценка
    • Knapsack Virtual programming lab
      Обучаваните трябва
      Получаване на оценка

    • 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.

    • Kukulkan - Java Virtual programming lab
      Обучаваните трябва
      Получаване на оценка

    • Exercice simple pour mettre en oeuvre le modèle proposé dans le lab Knapsack

    • Load Balancing - Java Virtual programming lab
      Обучаваните трябва
      Получаване на оценка

    • Variation sur le sac-à-dos avec implémentation du backtrack

    • Hotels - Java Virtual programming lab
      Обучаваните трябва
      Получаване на оценка
    • Christmas Dynamic Challenge Тест
      Обучаваните трябва
      Получаване на оценка
    • Keeping Water- Java Virtual programming lab
      Обучаваните трябва
      Получаване на оценка
    • Cutting Cloth - Java Virtual programming lab
      Обучаваните трябва
      Получаване на оценка
    • Cutting Cloth (One possible answer from Hadrien Cambazard) Страница
      Обучаваните трябва
      Преглеждане