Correction algorithme non-spé BAC S 2013 (Centres Etrangers)

[critor]

Bonjour,


Aujourd'hui nous allons regarder ensemble l'algorithme qui est tombé dans l'exercice non-Spécialité du BAC S dans les Centres Etrangers en juin 2013, dans le contexte de suites récurrentes comme la plupart du temps:

Question A)1)
Il nous faut donc compléter l'algorithme fourni, qui se doit de calculer par récurrence le 9^ème terme de la suite, et dans lequel deux affectations sont incomplètes. C'est un algorithme type, et les deux affectations correspondent au calcul de récurrence, et à l'incrémentation du rang.

Code: Select all

Variables:
   n est un entier naturel
   u est un réel
Initialisation:
   Affecter à n la valeur 1
   Affecter à u la valeur 1,5
Traitement:
   Tant que n<9
      Affecter à u la valeur (nu+1)/(2(n+1))
      Affecter à n la valeur n+1
   Fin Tant que
Sortie:
   Afficher la variable u

Resterait encore à vérifier à la calculatrice graphique si notre algorithme est juste, en le traduisant en un programme. Remarquons que l'énoncé nous donne gentiment un tableau de valeurs de la suite à la question A)3), mais que le terme u₉ n'y figure pas. Nous allons donc par exemple apporter une toute petite modification au programme en question, en lui faisant demander le rang du terme à calculer, ce qui nous permettra de vérifier la justesse de l'algorithme avec les autres termes du tableau.

Voici par exemple le programme adéquat pour TI-76/82/83/84, et qui nous confirme bien la valeur de u₆ du tableau:

Si vous ne disposez pas de ce type de calculatrice, on réalise tout aussi facilement un programme équivalent pour TI-Nspire, Casio Graph/Prizm/fx-CG, ou HP-39gII/Prime:

Il faut bien faire attention à ne pas utiliser de multiplication implicite sur les modèles formels, dont ici la TI-Nspire et la HP-Prime.

Petit détail sur Casio Classpad/fx-CP, où le résultat est affiché par défaut sous forme fractionnaire exacte, non directement comparable avec les valeurs du tableau:

Il faut faire appel à la fonction approx() afin de bien obtenir une forme décimale approchée:

Question A)2)
On nous demande donc maintenant de modifier l'algorithme obtenu pour qu'il affiche tous les termes de u₂ à u₉. Il nous suffit donc de déplacer l'instruction d'affichage finale dans la boucle, afin qu'elle soit exécutée pour toutes les valeurs de la suite:

Code: Select all

Variables:
   n est un entier naturel
   u est un réel
Initialisation:
   Affecter à n la valeur 1
   Affecter à u la valeur 1,5
Traitement et sorties:
   Tant que n<9
      Affecter à u la valeur (nu+1)/(2(n+1))
      Affecter à n la valeur n+1
      Afficher la variable u
   Fin Tant que

Afin de vérifier avec davantage de confort le bon fonctionnement de notre algorithme sur calculatrice graphique, nous afficherons le rang n en même temps que le terme associé. Il nous suffira alors de comparer avec le tableau de valeurs de la question A)3).

Voici des programmes pour TI-76/82/83/84, TI-Nspire, Casio Graph/Prizm/fx-CG, HP-39gII/Prime et Casio Classpad/fx-CP:

Question A)3)
Au vu du seul tableau de valeurs présenté par l'énoncé, on peut conjecturer que la suite u est strictement décroissante et converge vers 0,01.



Vient ensuite une partie B) où à l'aide d'une suite géométrique auxiliaire v, il est démontré que la suite u est bien strictement décroissante, mais converge en fait vers 0 et non 0,01. Notre conjecture était donc partiellement fausse. Nous retournons ensuite à l'algorithmique avec la partie C):

Partie C)
On nous demande donc de reprendre l'algorithme de la partie A), pour rechercher le rang n du premier terme vérifiant u_n<0,001. L'algorithme de la partie A) affiche la valeur du 9^ème terme u₉. L'instruction d'affichage finale devra donc déjà être modifiée pour afficher un rang et non un terme. D'autre part, pour s'arrêter non pas au 9^ème terme mais au premier terme vérifiant u_n<0,001, il nous faut changer la condition de poursuite de la boucle tant que, en la remplaçant par le contraire logique de la condition d'arrêt recherchée, soit ici u_n≥0,001. Tout sortie de la boucle vérifiera donc forcément u_n<0,001, et comme la suite u converge vers 0 on est sûr que cela se produira.

Code: Select all

Variables:
   n est un entier naturel
   u est un réel
Initialisation:
   Affecter à n la valeur 1
   Affecter à u la valeur 1,5
Traitement:
   Tant que u≥0,001
      Affecter à u la valeur (nu+1)/(2(n+1))
      Affecter à n la valeur n+1
   Fin Tant que
Sortie:
   Afficher la variable n

Voici par exemple un programme traduisant cet algorithme pour TI-76/82/83/84, et qui nous répond 1001.

Mais comment savoir si 1001 est bien la bonne réponse? La suite u étant strictement décroissante, réutilisons donc simplement notre programme de la question A)1) afin de vérifier les valeurs des termes u₁₀₀₀ et u₁₀₀₁:

u₁₀₀₁ est donc bien le premier terme strictement inférieur à 0,001.

Si vous ne disposez pas de ces calculatrices, voici maintenant les programmes équivalents pour TI-Nspire, Casio Graph/Prizm/fx-CG et HP-39gII/Prime:

Et les Casio Classpad/fx-CP diront certains d'entre vous? Voici le programme, mais...

... mais il n'y a pas de résultat?
... en fait la calculatrice est encore en train de réfléchir, comme l'indique l'icône en bas à droite...
... aurais-je fait une erreur? toutes les autres calculatrices ci-dessus ont à peine mis plus d'une seconde, juste le temps de lâcher la touche entrée...
... ça commence à faire long, déjà plusieurs minutes...

Et ben non, tout est normal, il faut attendre... 6 MINUTES ET 40 SECONDES!!!
Non, ce n'est pas une blague...
Bref, comme toute personne normale, et qui plus est pendant un examen, vous alliez sûrement douter de vous, vous interroger, et interrompre le programme pour en vérifier le code bien avant ce délai...
Bon certes, nous savons que, si on met l'écran de côté, le matériel des Casio fx-CP400 est très inférieur à celui des TI-Nspire ou HP-Prime... Certes, j'ai toujours lu sur les forums Casio que le langage Basic des Casio Classpad était lent...
Mais 400 fois plus lent que toutes les autres calculatrices du marché il y a peut être exagération là, non?...

La calculatrice met donc de l'ordre de la demi-seconde pour chacune des itérations de la boucle, ce qui est tout simplement énorme pour un processeur. Tentons de comprendre ce qu'elle peut bien fabriquer pendant tout ce temps, en affichant le terme de la suite à chaque itération:

Ah voilà... Cela rejoint le problème que nous avions déjà évoqué à la question A)1). La calculatrice utilise en interne une forme fractionnaire exacte pour le terme u, forme qui devient au fur et à mesure des itérations de plus en plus complexe avec énormément de chiffres aux numérateur et dénominateur. Nous allons donc encore une fois corriger le problème avec la fonction approx(), pour forcer le mode décimal approché:

Ah voilà c'est beaucoup mieux, et j'ai déjà le résultat. Il m'a juste fallu attendre 50 SECONDES cette fois-ci...

Non en fait c'est nul, ça reste beaucoup trop long, et dans les 50 fois plus lent que toutes les autres calculatrices ci-dessus. Et de plus pour un algorithme type de BAC relativement simple (pas de boucles imbriquées ou ce genre de chose). Devant l'importance qu'a pris l'algorithmique dans l'enseignement secondaire français ces dernières années, thème qui tombe désormais au BAC dans toutes les séries, y compris littéraires et technologiques, je ne peux conseiller l'achat de cette calculatrice qui est tout simplement inadaptée au lycée et au BAC. Comme de plus l'aventure algorithmique se poursuit depuis cette rentrée au delà du lycée, notamment avec les nouveaux programmes de BTS et de prépa, on peut également émettre des réserves sur son adéquation à l'enseignement supérieur scientifique. N'importe lequel des autres modèles évoqués ci-dessus sera moins cher et surtout beaucoup plus rapide.



Téléchargement:
BAC S: sujets toutes matières et corrigés 2012-2013

[Lionel Debroux]

Hmm... alors comme ça, la fx-CP400
* a (pour l'instant, mais vu le faible rythme et le faible gain des mises à jour pour Prizm, on peut craindre que ce soit la même chose pour fx-CP400...) un OS qui n'est qu'une pâle amélioration de celui des Classpad 300/330 (faible prise en compte du gain de la couleur, comme le montrait le test il y a quelques semaines);
* garde le défaut de lenteur des Classpad 300/330 (et là, c'est le code qui est merdique, puisque les Prizm se débrouillent bien, malgré un matériel inférieur au matériel pourtant déjà dépassé des fx-CP400);
* est hors de prix pour le grand public, comme si ça ne suffisait pas ?

C'est difficilement admissible en 2013, 2 ans après la sortie de la Nspire CX CAS et la même année que la sortie de la Prime. En 2003, les ClassPad 300/330 avaient un aspect innovant... mais dix ans plus tard, sur la fx-CP400, qu'est-ce qui est innovant ?

Les 84+CSE, autre nouveau modèle de 2013, sont elles aussi lentes, chères et dépourvues d'innovation - mais TI a fait des efforts pour adapter l'OS à la résolution bien supérieure et à la couleur. Sans la Prime (qui a notamment un grapher intéressant) pour relever un peu le niveau, le cru 2013 serait bien mauvais...

[Bisam]

Critor, pour le Classpad :
N'y a-t-il pas un mode "APPROX" qui force tous les calculs à être faits en mode approché ?
C'est quand même la première fois que je vois une calculatrice qui transforme DE FORCE une expression approchée en expression exacte !

[critor]

J'ai cherché en ce sens oui.
Il y en a bien un mode approché dans la barre des tâches de l'application calculs (Main), mais il n'apparaît pas dans celle de l'application d'édition-exécution de programmes.

J'ai également relancé l'application programmes après avoir passé l'application calculs en mode approché.
Aucun changement dans les performances.

Reste à voir si il y a une commande spéciale à mettre au début de programme ou option à régler quelque part dans l'application pour que tous les calculs soient en mode approché... Je n'ai pas trouvé jusqu'à présent.

En passant, j'ai tenté de mettre des approx() à toutes les lignes sur toutes les variables et tous les calculs intermédiaires, mais je ne descends pas en dessous des 50 secondes.

[Laurae]

Reste à voir si il y a une commande spéciale à mettre au début ou option à régler quelque part pour que tous les calculs soient en mode approché... Je n'ai pas trouvé jusqu'à présent.

Sur les Casio Graph c'est possible (le réglage est même global que vous le faites via les menu de paramètres ou via un programme qui modifie directement ces paramètres), pour les Classpad je ne sais pas.

[critor]

Trouvé dans les menus comment lancer un programme en mode décimal sur fx-CP400, pour ne pas avoir à mettre des approx() partout:


J'ai vérifié avec une instruction de sortie dans la boucle, la variable u contient bien une forme décimale et non une forme fractionnaire.

On supposait que dans l'instruction approx((nu+1)/(2(n+1)) avec laquelle j'avais terminé mon 1er post il y avait une perte de temps, avec un calcul exact du paramètre suivi d'un arrondi.

Et ben non - les nouvelles performances du programme ci-dessus restent de 50 SECONDES, et là c'est sûr il n'y a plus de perte de temps en calcul exact.

Il faut donc apparemment en déduire que c'est hélas représentatif des performances visiblement désastreuses de l'interpréteur de programmes de la fx-CP400, de loin la calculatrice la plus lente dans ce domaine, même en incluant les modèles du siècle dernier.

[Bisam]

Je dirais même plus : c'est de l'ordre des tous premiers ordinateurs ! L'IBM 1620, datant de 1959, était capable d'opérer jusqu'à 60 multiplications par seconde.

On compte ici 3 additions, 2 multiplications, 1 division et 1 comparaison par boucle, soit un total de 7000 opérations en 50 secondes.
A l'heure où les ordinateurs personnels (ainsi que les consoles de jeu, les portables, les tablettes, etc...) atteignent sans problème le Gigaflop (soit 1 milliard d'opérations en virgule flottante par seconde) et où les superordinateurs dépassent le Pétaflop (soit 1 million de milliards d'opérations par seconde) ici nous avons une calculatrice qui péniblement atteint 140 opérations par seconde (1.4 hectoflop )