<aside> ℹ️

Le cours s’est déroulé entièrement de manière théorique avec présentation à l’écran et codage commun à l’écran étant donné que les comptes informatiques étaient désactivés.

</aside>

Principes de la programmation dynamique

moodle.epfl.ch

• [x] 1. Introduction à la programmation dynamique
• [x] 2. Le problème avec les nombres de Fibonacci récursifs
  • 2.1. Nombres de fibonacci récursifs
  • 2.2. Complexité de Fibonacci récursif
  • 2.3. Complexité de Fibonacci récursif
  • 2.4. Complexité de la récursion naïve
• [x] 3. Programmation dynamique “top-down” : la mémoïsation
  • 3.1. Mémoïsation avec un dictionnaire
  • 3.2. Arbre des appels récursifs avec la mémoïsation
  • 3.3. Analyse de complexité de la récursion avec la mémoïsation
  • 3.4. Limites de l’approche récursive descendante
• [x] 4. Intermède : le graphe de dépendances
  • 4.1. Graphe de dépendances
  • 4.2. Tri topologique
• [x] 5. Approche itérative ascendante
  • 5.1. De la version récursive à la version itérative
  • 5.2. Analyse de complexité de la version itérative
  • 5.3. BONUS : Améliorer la complexité spatiale
• [ ] 6. Le problème du sac à dos avec la programmation dynamique
  • [x] 6.1. Instance toy-instance
  • [x] 6.2. Résolution par la force brute
  • [ ] 6.3. Approche récursive avec mémoïsation (Top-Down) ⇒ on a fait la fonction récursive, mais sans la mémoïsation
  • [ ] 6.4. Approche itérative tabulaire (Bottom-Up)
  • [ ] 6.5. Complexité de l’approche par la programmation dynamique
  • [ ] 6.6. Représentation des instances
  • [ ] 6.7. Test sur des instances plus grandes