Idées d’apprentissage actif
La programmation dynamique est une technique d'optimisation avancée qui permet de résoudre des problèmes complexes en évitant de recalculer plusieurs fois les mêmes sous-problèmes. Ce chapitre introduit des concepts clés comme la mémoïsation (stockage des résultats intermédiaires) et la construction de solutions de bas en haut. C'est une étape cruciale pour les élèves qui souhaitent approfondir l'algorithmique.
Activité 01
Les élèves doivent trouver le nombre minimal de pièces pour rendre une somme donnée. Ils essaient d'abord avec une méthode gourmande (qui échoue parfois) avant de construire un tableau de programmation dynamique.
Qu'est-ce que la mémoïsation ?
Activité 02
Sur une pyramide de nombres, les élèves doivent trouver le chemin de somme maximale. Ils découvrent qu'en partant du bas et en stockant les meilleurs scores, le problème devient très simple à résoudre.
Comment la programmation dynamique améliore-t-elle les performances ?
Activité 03
On présente le calcul de Fibonacci. Les élèves comparent l'arbre d'appels récursifs classique (avec ses nombreux doublons) et la version avec un dictionnaire de mémoire. Ils discutent du gain de performance.
Dans quels cas utiliser la programmation dynamique ?
Quelques notes pour enseigner cette unité
Attention à ces idées reçues
Confondre programmation dynamique et algorithme glouton.
L'algorithme glouton fait le meilleur choix immédiat sans revenir en arrière, ce qui n'est pas toujours optimal. La programmation dynamique explore toutes les possibilités de manière intelligente. Faire comparer les deux sur un système de monnaie non-canonique est très efficace.
Penser que la programmation dynamique est toujours nécessaire.
Elle n'est utile que si les sous-problèmes se recoupent. Si chaque sous-problème est unique, une simple récursion suffit. Analyser l'arbre des appels permet aux élèves de décider si la mémoïsation est pertinente.
Méthodes utilisées dans ce dossier
Algorithmes sur les arbres
Parcours d'arbres (préfixe, infixe, suffixe, en largeur). Recherche, insertion et suppression dans un arbre binaire de recherche.
8 methodologies
Algorithmes sur les graphes
Parcours de graphes en largeur et en profondeur. Recherche de chemins, détection de cycles et applications pratiques.
8 methodologies
Méthode "Diviser pour régner"
Principe de la méthode diviser pour régner. Application au tri fusion et analyse de la complexité algorithmique.
8 methodologies