(Durée : 2 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.
On attachera une grande importance à la clarté, à la précision, à la concision de la rédaction.

On cherche à calculer le gain maximum possible à la Bourse sur une action pendant une période de

jours, en ne faisant qu'une opération d'achat et de vente d'une seule action. On suppose que les cours quotidiens de cette action sont enregistrés dans un tableau d'entiers naturels (

) de

éléments

On définit l'amplitude de la variation du cours comme la valeur absolue du maximum de la variation de ce cours pendant la période observée, c'est-à-dire la quantité suivante :

Le temps d'exécution

d'une fonction

de la variable

est le nombre d'opérations élémentaires (addition, soustraction, multiplication, division, affectation) nécessaire au calcul de

. Lorsque ce temps d'exécution dépend d'un paramètre

, il sera noté

. On dit que la fonction

s'exécute :

en temps linéaire par rapport au paramètre , s'il existe tel que pour tout ,
en temps quadratique par rapport au paramètre , s'il existe tel que pour tout , .

Question 1 Écrire une fonction amplitude(a) qui retourne comme résultat l'amplitude de la variation du cours représenté par le tableau

. Donner un ordre de grandeur du temps d'exécution de cette fonction en fonction de

Le gain maximum est le gain maximum possible sur la période observée, c'est-à-dire la quantité suivante :

Question 2 Donner un exemple où l'amplitude est différente du gain maximum. Que représente l'amplitude en terme de gain ou de perte?

Question 3 En suivant textuellement la définition du gain, écrire une fonction gain(a) qui retourne, en temps quadratique (par rapport à

), le gain maximal possible sur le cours représenté par le tableau

Question 4 Modifier la fonction précédente pour aussi imprimer les deux dates

d'achat et de vente de l'action permettant d'obtenir le gain maximum sur le tableau

(avec

minimum).

Pour tout

définissons le gain courant maximum gainCourant

comme le gain maximum possible obtenu en vendant son action au temps

, c'est-à-dire :

Question 5 En calculant progressivement le gain courant maximum, écrire une fonction gain1(a) qui retourne, en temps linéaire (par rapport à

), le gain maximum possible sur le cours représenté par le tableau

Question 6 Modifier la fonction précédente pour aussi imprimer les deux dates

d'achat et de vente de l'action permettant d'obtenir le gain maximum sur le tableau

(avec

minimum).

On considère maintenant la possibilité de faire séquentiellement deux transactions pendant la période observée, c'est-à-dire de considérer deux dates d'achat

, et deux dates de vente

telles que

Question 7 Écrire la fonction gain2(a) qui retourne, en temps quadratique (par rapport à

), le gain maximum possible en faisant deux transactions sur le cours de l'action représenté par le tableau

Question 8 Modifier la fonction précédente pour aussi imprimer les quatres dates

, et

d'achats et de ventes de l'action permettant d'obtenir le gain maximum sur le tableau

(avec

minimum).

Polytechnique Informatique Commune MP PC 2002

ÉCOLE POLYTECHNIQUE

ÉCOLE SUPÉRIEURE DE PHYSIQUE ET CHIMIE INDUSTRIELLES

filière MP - option sciences industrielles filière PC

ÉPREUVE FACULTATIVE D'INFORMATIQUE

filière MP - option sciences industrielles
filière PC