nombres triangulaires

Discussion sur l'enseignement de l'algorithmique avec Xcas au lycee
alain974
Messages : 104
Inscription : lun. mai 24, 2010 11:15 am

nombres triangulaires

Message par alain974 » sam. oct. 16, 2010 6:30 pm

Voici ma première idée de mesure de temps de calcul en Seconde:

1) On commence par additionner les n premiers entiers avec la boucle suivante:

Code : Tout sélectionner

som(n):={
local s;
local indice;
pour indice de 0 jusque n faire
s:=s+indice;
fpour;
return s;
}:;
On peut faire découvrir son fonctionnement par le mode pas-à-pas (découverte des boucles, il y en a plein dans les bouquins de Seconde).

2) Ensuite on entre quelque chose comme

Code : Tout sélectionner

factor(sum(k,k,1,n))
pour avoir une manière plus directe (parce que sans boucle) pour calculer la somme.

3) Afin de comparer les deux manières de calculer les nombres triangulaires, on mesure ces temps de calcul pour diverses valeurs de n. Avec

Code : Tout sélectionner

boucle:=seq(time(som(n))[0],n=1..100))
formule:=seq(time(n*(n+1)/2)[0],n=1..100))
on constate que non seulement le temps de calcul avec la formule est constant (indépendant de n) mais même pour n=1, il est inférieur à la version boucle.

4) Enfin, on représente le nuage de points de la version boucle par

Code : Tout sélectionner

(point(k+1,boucle[k]))$(k=0..99) ; 
5) Et c'est là que ça devient génial: La "fonction" représentée est affine :shock: (et même pas linéaire!) :twisted: . Alors on demande aux élèves de déterminer ladite fonction affine puis d'en déduire une estimation du temps de calcul avec la méthode "boucle" pour additionner les 100 000 premiers entiers.

En fait on peut faire le TP en deux séances, une pour les 1-2-3-4 et une (ou un DM) pour la 5.

Par contre, en y regardant de plus près, le nuage est plus en escalier que vraiment affine, il y a des paliers que j'ai également découverts avec Rhino, en utilisant l'objet Date() de JavaScript pour mesurer le temps. :?:

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: nombres triangulaires

Message par parisse » sam. oct. 16, 2010 7:08 pm

Très bonne idée! Une alternative au nuage de points, plotlist(boucle) affiche la ligne polygonale pointée des valeurs.
Pour l'escalier, c'est normal parce qu'au fur et à mesure que le temps de calcul augmente, le nombre d'exécution faite pour déterminer le temps moyen d'exécution diminue, la moyenne est donc moins précise. Il y a aussi surement d'autres phénomènes que je n'entrevois pas.
Le fait que ce ne soit pas linéaire est normal, car pour n=0 il y a un travail à faire (passage d'arguments, initialisation des variables locales, valeur renvoyée...).

alb
Messages : 1320
Inscription : ven. août 28, 2009 3:34 pm

Re: nombres triangulaires

Message par alb » sam. oct. 16, 2010 7:48 pm

Très bon exemple !
Chez moi pour (point(k+1,formule[k]))$(k=0..99) j'obtiens nettement 2 horizontales distinctes:
l'une d'équation y=1.8e-06 contenant 40 points et 10 points légèrement au dessus, ceci pour n impair.
l'autre d'équation y=3.4e-06 contenant 40 points et 10 points de part et d'autre, ceci pour n pair.
Peut-on expliquer ça ?

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: nombres triangulaires

Message par parisse » dim. oct. 17, 2010 6:34 am

C'est en effet assez bizarre. Difficile de se plonger dans les méandres du calcul fait, mon hypothèse est que si n est pair le calcul de (n+1)/2 est plus compliqué que si n est impair (fraction) et ça pourrait peut-etre expliquer. Mais c'est quand même mystérieux parce que je ne vois pas de raison pour laquelle le calcul de n*(n+1) ne serait pas effectué avant la division par 2.

alb
Messages : 1320
Inscription : ven. août 28, 2009 3:34 pm

Re: nombres triangulaires

Message par alb » dim. oct. 17, 2010 7:44 am

effectivement il semble que la priorité des opérations soit en cause.
seq(time(n*(n+1)/2)[0],n=0..100) renvoie à peu près une séquence de période 2, le temps pour n pair étant approximativement deux fois plus grand que pour n impair
seq(time(n/2*(n+1))[0],n=0..100) renvoie à peu près une séquence de période 2, le temps pour n impair étant approximativement deux fois plus grand que pour n pair
seq(time((n*(n+1))/2)[0],n=0..100) renvoie une séquence quasi constante.
Ce serait peut-être intéressant d'analyser avec les élèves l'ordre des opérations et l'usage des parenthèses

Répondre