Introduction à la programmation dynamique

« Introduction à la programmation dynamique Introduction à la programmation dynamique 1 Introduction Définition 1.1 (Prémices) — Un problème d’optimisation est un problème dans lequel on souhaite minimiser ou maximiser une fonction sur un ensemble. — La programmation dynamique est une technique permettant de résoudre des problèmes d’optimisation ou combinatoires (problèmes de "comptage"...). — Anecdote : La programmation dynamique a été crée par Richard Bellman dans les années 1950.

Le nom a été choisi pour plaire à l’armée américaine. Exercice 1.2 (Le sécheur de cours) Hugo assiste à n jours de cours.

Le i-ème jour de cours possède un niveau d’ennui ai (a est une liste de n entiers, 0-indexée).

Il souhaite sécher des cours de telle manière à ce qu’il minimise la somme des niveaux d’ennui des cours auxquels il est présent.

Malheureusement, il est impossible de sécher deux jours consécutifs. Déterminer la somme minimale des niveaux d’ennui des cours auxquels Hugo devra assister. Démonstration On peut d’abord chercher à formaliser ce problème mathématiquement. On note ui,j la réponse au problème si l’on ne considère que les i premiers jours de cours et que j représente si l’on sèche le i-ème cours ou non (j vaudra donc 1 ou 0, ce type de variable qui ne peut prendre que deux valeurs distinctes est appelé booléen).

Remarquons que : — u0,1 = 0 et u0,0 = a[0] — uk+1,1 = uk,0 (si Hugo sèche les cours il est obligé de ne pas sécher le jour précédent) — uk+1,0 = min(uk,0 , uk,1 ) + a[k + 1] (si Hugo ne sèche pas les cours, il est libre.... »