La programmation dynamique consiste à ramener la résolution d’un problème à celle de sous-problèmes de taille inférieure, mais non indépendants (c’est la différence avec la méthode « diviser pour régner ». La récursivité, qui conduirait à un complexité exponentielle doit donc être évitée. En général, on procède aux étapes suivantes :
- exprimer par récurrence la solution du problème en fonction de celle de sous-problèmes ;
- initialiser un tableau avec les conditions initiales vues à la première étape ;
- remplir progressivement ce tableau par taille croissante de sous-problème, avec la récurrence vue en étape 1.
7.1.1 Deux fonctions pour mesurer le temps qui passe
On écrit la fonction test1 telle que test1 f x renvoie le couple {(f(x),t),} où {f} est une fonction{,x} un argument de {f,} et où
{t} est le temps (exprimé en secondes) nécessaire au calcul de expression {f(x).} De même, l’expression test2 f x y renvoie {(f(x,y),t),} où {f} est une fonction{,x,y} ses deux arguments, et {t} est le temps
(exprimé en secondes) nécessaire au calcul de l’expression {f(x,y).}
|
1 2 3 4 |
let test1 f x = let t = Sys.time() in let y = f x in y, Sys.time() -. t;; test1 : ('a -> 'b) -> 'a -> 'b * float = <fun> |
|
1 2 3 4 |
let test2 f x y = let t = Sys.time() in let z = f x y in z, Sys.time() -. t;; test2 : ('a -> 'b -> 'c) -> 'a -> 'b -> 'c * float = <fun> |
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres