Programmation dynamique : nombres de Fibonacci

Cette séance de cours couvre les concepts de programmation dynamique appliqués au calcul des nombres de Fibonacci. Il traite de la définition récursive des nombres de Fibonacci, de l'inefficacité de l'algorithme récursif, et de l'optimisation par la mémorisation et les approches itératives. En outre, il explore l'algorithme gourmand pour les problèmes de changement de pièce et son optimisation. La séance de cours se penche également sur les problèmes de coloration des graphiques, en analysant les algorithmes pour déterminer si un graphique peut être coloré avec deux couleurs et la complexité impliquée. Enfin, il présente une variante du problème de knapsack, en se concentrant sur la recherche du nombre maximum d'objets qui peuvent s'intégrer dans un knapsack de capacité limitée.