Mathématice, intégration des Tice dans l'enseignement des mathématiques  
Sommaire > N°43 - janvier 2015 > Algorithme du sujet du Bac S, Nouvelle-Calédonie,

Algorithme du sujet du Bac S, Nouvelle-Calédonie, mars 2014
(Méthode des rectangles)
Moteur de recherche
Mis en ligne le 12 décembre 2014, par Stéphan Manganelli

Autres articles de Stéphan Manganelli

Cet article peut être librement diffusé et son contenu réutilisé pour une utilisation non commerciale (contacter l’auteur pour une utilisation commerciale) suivant la licence CC-by-nc-sa (http://creativecommons.org/licenses/by-nc-sa/3.0/fr/legalcode)

Auteur : Stéphan Manganelli
LEGTA "Louis GIRAUD"
CARPENTRAS-SERRES (84)

stephan.manganelli@educagri.fr

Cet article est présenté sous la forme de blocs à déplier. Les différentes images représentant les algorithmes peuvent être agrandies en cliquant dessus.



2. Le traitement avec LARP de la version du sujet…


JPEG - 162.6 ko


- Avec la console d’exécution qui affiche les valeurs de U et V renvoyées par l’algorithme (Question 1. b.)

JPEG - 183.9 ko


TRANSITION :
On pourrait penser, dans un premier temps, que pour répondre à la question 2.a., il faille faire des essais successifs en augmentant l’ordre n de la subdivision… pas rendu ! Ou bien alors qu’il faille implanter une boucle TantQue pour sortir le premier entier n qui réponde à la condition… pas si simple… et, ce dont je ne me doutais pas, extrêmement chronophage (voir REMARQUES 1, 2 et 3 plus bas et paragraphe 3 suivant)…
En fait, si l’on a traité un peu en profondeur la méthode des rectangles, on doit savoir que, pour une fonction continue, positive et croissante sur [a ; b], on a $ V_n - U_n$ = $ \frac {f(b) - f(a)} {n}$ ... ce que l’on peut vérifier de suite ici puisque, après simplification on a bien :

$ V_n - U_n$ = $ \frac {f(2) - f(1)} {n}$ = $ \frac {2 \ln 2} {n}$

.
La résolution de l’inéquation $ V_n - U_n$ < 0,1 fournit alors 14 pour valeur du plus petit entier n tel que $V_n -U_n$ < 0,1.

Du coup, la réponse à la question d’après 2.b. devient évidente : changer « n prend la valeur 4 » par « n prend la valeur 14 » !

JPEG - 186.3 ko
n prend la valeur 14


REMARQUE 1 :
Depuis le début, je me dis naturellement (comme me l’ont dit mes élèves qui en ont pris l’habitude aussi) que l’on pourrait insérer une requête au niveau de n (c’est-à-dire demander à l’utilisateur de choisir lui-même l’ordre de la subdivision), ce qui permettrait d’atteindre par essais (de façon empirique) la précision souhaitée… mais comme j’ai l’intention d’implanter la boucle TantQue, je me dis que cela revient un peu au même… voire que c’est même mieux car je viserai juste du premier coup…
Nous allons voir qu’un gros problème apparaît : la boucle TantQue est extrêmement chronophage !!!


3. Une surprise de taille avec la boucle TantQue qui permet de choisir le niveau de précision…


- Il faut initialiser avec $U_1$ et $V_1$ pour que la boucle TantQue commence…

JPEG - 175.9 ko

- Dans la boucle TantQue les calculs de ($U_2$ et $V_2$), ($U_3$ et $V_3$) etc. se font (avec la boucle Pour)… jusqu’à ($V_n$ et $U_n$) pour lesquels $V_n - U_n < p$… et on sort alors de la boucle TantQue.


JPEG


- L’algorithme renvoie alors les deux premières valeurs $U_n$ et $V_n$ qui encadrent A à moins de p (ci-dessous, la valeur 14 trouvée en réponse à la question 2. a.)


JPEG - 203.5 ko


- Pour une précision de $10^{-2}$… on obtient quasi instantanément…

JPEG - 52.5 ko

- Pour une précision de $10^{-3}$… on obtient, au bout d’environ 1 minute…

JPEG - 46.8 ko

- Mais pour notre précision de $10^{-4}$ … on obtient, au bout d’1h26…

JPEG - 137.7 ko


REMARQUE 2 :
Jusque-là, je n’y vois toujours rien… certes c’est long mais bon, qu’y puis-je ? Entre-temps, mon compère Guillaume C. me fait remarquer que cette boucle TantQue n’est vraiment pas à la hauteur des espérances… n’a finalement guère de pertinence, etc.
Ce à quoi je réponds : « Mais, qui dit mieux ? » ; d’autant que je sais, dixit Hubert R., que LARP est un langage compilé, et qu’il va habituellement assez vite… ; « Alors, qui dit mieux ? ».
J’avais la réponse dans un coin de ma tête mais je ne voulais la sortir… et c’est finalement mes élèves qui me la (re)sortent … : « Monsieur, on fait la REQUÊTE pour n ? »…
Moi : « Bien vu, super, comm’ d’hab’, allons-y ! ». Je dois avouer qu’à ce moment de notre travail, je ne me doute absolument pas de ce qui va se passer…


4. Juste une petite REQUÊTE …


- Et nous voici avec notre petite REQUÊTE… : on rentre 10 000 et on obtient INSTANTANÉMENT :


JPEG - 197.3 ko
Notre petite requête


- Pierre : « Monsieur, j’ai essayé 100 000 et en à peine 10 s » :

JPEG - 34.7 ko

- Jullien : « Monsieur, pour 1 000 000, faut 53 s » :

JPEG - 34 ko

- Et Lisa m’achève : « Monsieur, j’ai essayé avec 5 000 000, et ça a mis à peu près 4 min, et j’ai 6 chiffres significatifs ! » :

JPEG - 34 ko


REMARQUE 3 :
Moi le profane, je n’avais pas évalué à quel point la boucle TantQue pouvait ralentir l’algorithme…
Merci à Guillaume C. qui m’a mis une puce à l’oreille, puis à mes élèves, qui l’ont fait sortir !
Alors c’est quoi qui ralentit… ? Au début, on pense au Test en début de boucle… mais bon je ne suis pas des plus convaincus… Il aura fallu le concours d’autres collègues, à qui je raconte l’épopée, pour, ENFIN, repenser à cette fichue boucle TantQue
C’est pourtant moi qui l’aie conçue cette boucle, non sans mal d’ailleurs, et je me souviens comment je l’ai fait tourner dans ma tête... mais j’ai apparemment tout oublié de suite comme le poisson rouge...
En effet, donc, pour un même nombre n $\ge$ 2 de rectangles en sortie, la boucle FOR simple, fait n tours..... quand elle en fait $2 + 3 + ... + n$ = $ \frac {n(n+1)} {2} - 1$  lorsqu’on l’imbrique dans le TantQue !!!


Ce n’est donc pas tant le test en début du TantQue qui coûte, mais bien le nombre de tours "en $n^2$" de la boucle FOR qui se réinitialise à chaque “passage+incrémentation sur n” dans la boucle TantQue.
(Re)Voir, ci-après, l’intérieur de la boucle TantQue pour comprendre le comptage des tours...


JPEG - 33.2 ko
La boucle FOR dans le TantQue
JPEG - 28 ko
La boucle FOR simple du début
$2 + 3 + ... + n$ = $ \frac {n(n+1)} {2} - 1$ tours
n tours (ici 4)


Je me dis maintenant, après coup, qu’on tient là une question intéressante, sur le plan Algorithmique (Analyse), à poser à des élèves : "Comparer les deux algorithmes en comptant, pour un même nombre n de rectangles en sortie, le nombre de tours dans les boucles FOR et justifier ainsi le ralentissement pour l’un d’entre eux deux."


5. Une solution alternative… dans l’esprit du sujet


Certes, la requête est intéressante, mais le sujet incitait tout de même plutôt le calcul de n en fonction d’une précision p souhaitée.
Du côté de la boucle TantQue, comme l’écrit Guillaume C. : “De manière générale, il faut éviter les TantQue avec des flottants pour ne pas succomber aux erreurs d’élimination.”

Une alternative peut être de faire calculer (parce qu’on le peut ici !), le plus petit entier n tel que $V_n - U_n$ < $p$, et qui va correspondre au nombre de tours dans la boucle FOR.

Tant qu’on y est, on peut éviter alors le calcul de V... puisque $V$ = $U + \frac {2 \ln 2} {n}$.


JPEG - 204 ko
JPEG - 7.5 ko
plafond(numerique) renvoie l’entier directement supérieur ou égal à numerique.
Exemples : plafond(2) = 2 ; plafond(11,35) = 12.

REMARQUE 4 :
On peut chercher encore d’autres améliorations dans l’écriture de l’algorithme… réfléchir aussi aux autres méthodes numériques de calcul approché d’une intégrale (rectangles des milieux, trapèzes, etc.)… comparer…


6. Pour me remettre de toutes ces émotions, je pars sur « Monte-Carlo »…


Cette méthode probabiliste, permet d’estimer l’aire du domaine D associé à une fonction, avec la fréquence f des points tirés aléatoirement (dans une figure prédéfinie, contenant D et dont on connaît l’aire), se trouvant dans D.

Ici la figure prédéfinie dans laquelle on tire, est le rectangle construit sur le segment [1 ;2], et de hauteur 2 (d’où x = aleatoire+1 et y = 2*aleatoire).

Ce rectangle ayant pour aire 2, on estime donc l’aire par 2*f.

- Pour n = 1 000 000, on obtient au bout d’environ 26 s, une estimation de l’aire A à 0,636864 :


JPEG - 194.3 ko
JPEG - 49.3 ko


Pour n = 10 000 000, on obtient au bout d’environ 4 min., une estimation de l’aire A à 0,636055 :


JPEG - 191.5 ko


ATTENTION



IL NE S’AGIT PLUS ICI D’UNE CONVERGENCE AU SENS DES RECTANGLES… MAIS D’UNE CONVERGENCE AU SENS DE LA LOI DES GRANDS NOMBRES !!!


ps

Note de la rédaction

L’algorithme est donné dans le sujet même. Si l’on connaît un tant soit peu le principe de la méthode des rectangles, on obtient par différence :
$ v(n)-u(n) = 2 \frac {ln(2)} {n}$. A partir de là, le problème est réglé.
Inutile de calculer v(n) et u(n) pour rendre $v(n)-u(n)$ inférieur à $p$.
On obtient $ n > 2 \frac {ln(2)} {p} $

Mieux vaudrait, dans les sujets d’examen, réserver l’algorithmique et les calculatrices aux cas où cela s’avère vraiment nécessaire, ou au moins utile ...

Réagir à cet article
Vous souhaitez compléter cet article pour un numéro futur, réagir à son contenu, demander des précisions à l'auteur ou au comité de rédaction...
À lire aussi ici
MathémaTICE est un projet
en collaboration avec
Suivre la vie du site Flux RSS 2.0  |  Espace de rédaction  |  Nous contacter  |  Site réalisé avec: SPIP  |  N° ISSN 2109-9197