nombres triangulaires
Publié : 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:
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
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
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
5) Et c'est là que ça devient génial: La "fonction" représentée est affine (et même pas linéaire!) . 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.
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;
}:;
2) Ensuite on entre quelque chose comme
Code : Tout sélectionner
factor(sum(k,k,1,n))
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))
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) ;
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.