Chapitre 12 : La programmation dynamique

Objectifs :

• Comprendre la méthode de programmation dynamique

•  Utiliser la programmation dynamique pour écrire un algorithme

•  Découvrir la mise en œuvre à partir des exemples de l’alignement de séquences et du rendu de monnaie.

Activité 1 – L’alignement de séquences

1. Regarder la capsule vidéo sur la programmation dynamique :

2. Donner le principe de base de la programmation dynamique.
3. Dans quel domaine scientifique l’utilisation de la programmation dynamique a connu un grand essor ?
4. Quel type de fonction utilise régulièrement la programmation dynamique ?
5. Détailler le principe de la recherche de l’alignement de séquences.
6. Reprendre l’algorithme de calcul de la distance de Levenshtein et le tester avec les séquences « information » et « informatique ».
7. Relancer le calcul en modifiant la matrice de Levenshtein en prenant un poids de 4 pour un bon alignement et -2 pour une insertion, suppression, modification.

Activité 2 – Le rendu de monnaie

1. Regarder la capsule vidéo sur la programmation dynamique :

2. Écrire l’algorithme en Python du rendue de monnaie force brute (et fonction récursive).
3. Dessiner le début de l’arbre des possibilités de rendue de monnaie pour 76 cts. Montrer sur cet arbre qu’il y a des redondances.
4. Écrire l’algorithme en Python du rendue de monnaie en programmation dynamique.
5. A l’aide de la fonction time() de la bibliothèque time de Python, évaluer le temps nécessaire pour votre ordinateur pour calculer le nombre minimal de pièces à rendre pour la somme de 76 cts à l’aide des deux algorithmes (questions 2 et 4)
6. Même chose avec 177 cts. Commenter.