Scheduling anyone ?
Post a priori incomprehensible, c’est pour décompresser
Certains vendredis me permettent de porter la bonne parole sur terre. J’enseigne en effet des rudiments de programmation à des élèves de niveau L2 Comment vous ne maîtrisez pas encore la réforme LMD ? Honte sur vous. Pour mémoire, L2≡Deug 2ème année. Malheureusement ces chères têtes blondes ont choisi de faire des sciences industrielles plutôt que de l’informatique, ce qui explique parfois leur manque de motivation. Les séances se résument donc souvent à Je m’ennuie
.
Ce vendredi ne faisait pas exception, le sujet que je leur avais proposé étant de plus particulièrement facile. Le but était de découvrir a posteriori les dates optimales d’achat et de ventes pour une action dont le cours en bourse A entre deux dates était donné.
La seule question difficile de l’énoncé impliquait de calculer cette valeur en un temps linéaire. Pour cela, il était conseillé d’introduire une valeur gc(n) modélisant le gain courant à la date n, à savoir la somme maximale que l’on peut gagner en vendant au temps n. Bien évidemment, celui-ci vaut A(n) auquel on retranche le cours minimum atteint par la valeur avant la date n. Le gain maximal en n est alors soit le gain courant en n, soit le gain maximum en n-1 (on vend soit à la date n, soit avant). Tout ceci nous donne le superbe système d’équations suivant :
m(n+1) = min(m(n), A(n+1))
gc(n+1) = A(n+1) - m(n+1)
gm(n+1) = max(gc(n+1), gm(n))
Il est facile de se convaincre que l’on peut calculer gm(n) en un temps linéaire. Par contre, une angoissante question se pose : combien faut-il de variables temporaires ? La réponse est obtenue en traçant un diagramme de dépendance entre les variables ; dans notre cas il est acyclique, et on n’a donc besoin d’aucune temporaire ! En effectuant un tri topologique, on peut savoir quelle variable doit être mise à jour en premier (ici m(n)), et obtenir du code optimal.
Je savais bien que mes cours d’optimisations sur des architectures parallèles finiraient par me servir un jour.