Programmation dynamique

Ce quiz de révision porte sur la programmation dynamique, technique algorithmique avancée du programme de spécialité NSI en Terminale. Il présente le principe général de cette approche, qui décompose un problème complexe en une série de sous-problèmes plus simples, et la technique de mémoïsation, qui consiste à stocker les résultats des sous-problèmes déjà résolus pour éviter de les recalculer inutilement. Le quiz détaille la différence entre programmation dynamique et algorithmique gloutonne, cette dernière effectuant des choix localement optimaux sans jamais revenir en arrière, contrairement à la programmation dynamique qui explore méthodiquement l'ensemble des possibilités pertinentes. Des exemples classiques comme le problème du rendu de monnaie ou le problème du sac à dos illustrent concrètement ces concepts, tandis que le gain de complexité spectaculaire obtenu par rapport à une approche récursive naïve, qui recalculerait inutilement les mêmes sous-problèmes, complète cette étude. En neuf questions à choix multiples autonomes, avec explications détaillées, cette ressource aide à comprendre une technique d'optimisation algorithmique puissante.

• Décrire le principe de la programmation dynamique
• Expliquer la technique de mémoïsation
• Distinguer programmation dynamique et algorithmique gloutonne
• Analyser des exemples classiques (rendu de monnaie, sac à dos)
• Comprendre le gain de complexité par rapport à une approche récursive naïve

Contenu généré à partir du programme officiel de spécialité NSI (Terminale) sur la programmation dynamique : décomposition en sous-problèmes, mémoïsation, algorithmique gloutonne, rendu de monnaie, sac à dos.