Fibonacci et temps de calcul

Discussion sur l'enseignement de l'algorithmique avec Xcas au lycee
Répondre
alb
Messages : 1320
Inscription : ven. août 28, 2009 3:34 pm

Fibonacci et temps de calcul

Message par alb » sam. sept. 25, 2010 9:20 am

Bonjour,
parisse a écrit :ça peut d'ailleurs donner lieu à des problèmes de maths intéressants comme le fait qu'une programmation récursive pour calculer la suite de Fibonacci entraine un temps de calcul proportionnel ... à la suite de Fibonacci.
J'ai essayé de regarder ce que donnait le temps de calcul pour ces deux fonctions :

Code : Tout sélectionner

Fiboiter(n):={
local A,B,C,k;
A:=1;B:=1;
si n<2 alors return 1;fsi;
pour k de 1 jusque n-1 faire
  C:=A+B;A:=B;B:=C;
fpour;
return C;
}
:;
et

Code : Tout sélectionner

Fiborecur(n):={
si n<2 alors return(1);fsi;
return(Fiborecur(n-1)+Fiborecur(n-2));
}
:;
Je pense que les résultats dans le cas de Fiboiter sont cohérents :

Code : Tout sélectionner

LTit:=seq(time(Fiboiter(k))[0],k=10..300) ;
(point(k+10,LTit[k]))$(k=0..290) ; 
renvoie un nuage laissant supposer que le temps de calcul du terme de rang n est proportionnel à n.
Je fais la même chose avec Fiborecur :

Code : Tout sélectionner

LT:=seq(time(Fiborecur(k))[0],k=20..30) ;
(point(k+20,LT[k]))$(k=0..10) ; 
renvoie un nuage que je suppose être de type exponentiel (?). Je fais:

Code : Tout sélectionner

Reg:=exponential_regression([k$(k=20..30)],[LT[k]$(k=0..10)]) ;
plot(Reg[1]*Reg[0]^x,x=20..30) ; 
j'obtiens une courbe de régression d'équation y=1.473e-05(1.625)^x

J'aurais aimé savoir si tout cela est bien cohérent (seulement 11 valeurs en récursif par exemple) et mérite d'être présenté à des élèves.

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

Re: Fibonacci et temps de calcul

Message par parisse » sam. sept. 25, 2010 12:14 pm

c'est pas mal du tout comme valeur, puisque en théorie (pour n assez grand) ca devrait etre proportionnel au nombre d'or à la puissance n, soit à 1.618...^n.

alain974
Messages : 104
Inscription : lun. mai 24, 2010 11:15 am

Re: Fibonacci et temps de calcul

Message par alain974 » dim. oct. 03, 2010 5:43 am

alb a écrit :mérite d'être présenté à des élèves.
Quels élèves? En Seconde j'hésite à parler de suites parce que je les réserve pour la Première, mais il doit y avoir des choses très intéressantes à faire avec cette fonction "time" dont je ne connais pas d'équivalent dans les autres outils d'algorithmique. Et là on est dans la vraie algorithmique, celle qu'étudie Donald Knuth.

Du coup je cherche des exemples plus au programme de Seconde (là tout de suite je pense à

1: Évaluation du temps de calcul des images de x par deux fonctions f etg égales entre elles, par exemple un polynôme développé et un polynôme factorisé;

2: Intérêt algorithmique de la méthode de Horner ...)

La constatation expérimentale qu'un algorithme est plus rapide qu'un autre, c'est super, la démonstration, en Seconde, c'est une autre affaire... À défaut les nuages de points ci-dessus sont un excellent sujet d'étude statistique, voire, pour le premier, en Seconde, un exo sur les fonctions affines...

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

Re: Fibonacci et temps de calcul

Message par alb » dim. oct. 03, 2010 3:39 pm

Je pense qu'il faut réserver ce genre d'activité aux élèves de Première ou Terminale S sans l'imposer à tout le groupe (le donner à ceux qui réalisent les exercices standards rapidement).
En seconde on peut peut-être proposer aux élèves qui veulent aller en S de comparer :

Code : Tout sélectionner

Factiter(n):={
local A,k;
A:=1;
pour k de 1 jusque n faire
  A:=A*k;
fpour;
return A;
}
:;
et

Code : Tout sélectionner

Factrecur(n):={
si n<2 alors 1 sinon 
  n*Factrecur(n-1);
fsi;
}:;
puis par exemple leur faire chercher la somme des 1/(2^k) ou des 1/(k^2) et graphiquement parler de limite.
Pendant que ce groupe cherche, on peut revoir les factorisations avec les autres.
Mon sentiment est qu'il faut persuader nos chefs d'établissements (et nos collègues) que l'aide personnalisée passe nécessairement par l'utilisation des salles info (il faut mettre l'AP math sur des créneaux horaires différents selon les enseignants) seule façon de proposer des activités adaptées à chaque élève. Et comme l'algorithmique est explicitement au programme, c'est le bon moyen de récupérer ½ ou 1 h de maths. Ensuite convaincre les enseignants qu'on ne peut pas se passer d'un logiciel de calcul formel multifonctions, les élèves pouvant vérifier leurs réponses sans intervention du prof. De toute évidence ces séances développent l'autonomie et l'entraide, termes qui ne sont pas contradictoires (les plus rapides corrigent les erreurs de leurs camarades).

alain974
Messages : 104
Inscription : lun. mai 24, 2010 11:15 am

Re: Fibonacci et temps de calcul

Message par alain974 » lun. nov. 01, 2010 8:14 am

alb a écrit :En seconde on peut peut-être proposer aux élèves qui veulent aller en S
On ne doit pas avoir le même genre d'élèves de Seconde qui veulent aller en S... :shock:

Le programme évite soigneusement de parler de récursivité et les factorielles, j'attendrais plutôt la Terminale pour en parler algorithmiquement, faut bien leur laisser quelque chose!

Sinon il y a un algorithme récursif rapide pour Fibonacci, basé sur deux formules visibles ici (et démontrables par récurrence mais peut-être pas en Terminale S):

Code : Tout sélectionner

FastFibo(n):={
  if(n<3) then return 1; end_if;
  if(est_pair(n)) then return (2*FastFibo(n/2+1)-FastFibo(n/2))*FastFibo(n/2);
    else return FastFibo((n+1)/2)^2+FastFibo((n-1)/2)^2;
    end_if;
};
Avec ça

Code : Tout sélectionner

fast:=seq(time(FastFibo(k))[0],k=1..64)

(point(k,fast[k]))$(k=1..63) ;
donne un nuage de points accidenté mais pas exponentiel (c'est censé être logarithmique en fait).


Enfin la formule de Binet (elle par contre démontrable par récurrence en S), on a

Code : Tout sélectionner

Binet(n):={
  local P;
  local p;
  P:=(1+sqrt(5))/2;
  p:=(1-sqrt(5))/2;
  return simplify((P^n-p^n)/sqrt(5));
};
Alors

Code : Tout sélectionner

fast:=seq(time(Binet(k))[0],k=1..100)

(point(k,fast[k]))$(k=1..99) ;
donne encore des paliers (fonction vaguement linéaire mais par paliers chaotiques). Ce qui doit s'expliquer par l'utilisation du calcul formel (déjà c'est pas forcément très intelligent de considérer P et p comme des variables locales alors qu'elles resservent tout le temps; quoique en les prenant globales ça ne change pas grand-chose).

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

Re: Fibonacci et temps de calcul

Message par alb » lun. nov. 01, 2010 9:33 am

J'enseigne dans un lycée agricole public et je pense avoir des élèves de seconde comparables à ceux de l'EN.
Parmi ceux qui veulent faire S, il y aura certainement des ingénieurs. Rien d'exceptionnel donc.
Qu'une notion ne soit pas au programme de seconde n'empêche pas de l'évoquer avec un vocabulaire simple.
Il m'est arrivé avec des élèves de seconde de leur faire développer à la main (a+b)^n pour n=1,2,3,4,5 puis après avoir rempli le tableau des coefficients de leur faire deviner le développement de (a+b)^10.
Avec Xcas on peut vérifier les conjectures et il y a toujours quelques élèves qui découvrent le principe du triangle de Pascal en moins d'une heure.
A ce sujet j'ai une question que je crois avoir déjà posée sur l'ordre des arguments d'une somme:
le développement de (a+b)^10 commence par 10*a^9*b et a^10 se retrouve à la fin, c'est juste un peu bizarre pour un élève.

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

Re: Fibonacci et temps de calcul

Message par parisse » lun. nov. 01, 2010 10:02 am

alb a écrit : A ce sujet j'ai une question que je crois avoir déjà posée sur l'ordre des arguments d'une somme:
le développement de (a+b)^10 commence par 10*a^9*b et a^10 se retrouve à la fin, c'est juste un peu bizarre pour un élève.
Si on utilise expand, par contre avec normal (ou avec reorder) ca écrit dans l'ordre.
Sinon, je ne connaissais pas la formule donnée par alain974 de type puissance rapide. Par contre, je ne vois pas pourquoi ce serait logarithmique, puisqu'il faut évaluer 2 fois la suite en n/2, il me semble que ça devrait être linéaire, à moins qu'il n'y ait une autre astuce?

alain974
Messages : 104
Inscription : lun. mai 24, 2010 11:15 am

Re: Fibonacci et temps de calcul

Message par alain974 » lun. nov. 01, 2010 10:35 am

parisse a écrit :je ne vois pas pourquoi ce serait logarithmique, puisqu'il faut évaluer 2 fois la suite en n/2, il me semble que ça devrait être linéaire

Autant pour moi :oops: c'est la méthode matricielle qui est logarithmique...

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

Re: Fibonacci et temps de calcul

Message par parisse » mar. nov. 02, 2010 9:16 am

en effet, le nombre d'etapes est logarithmique, mais en calcul exact, il manque l'analyse du temps de calcul du a la taille croissante des coefficients. Si on fait une multiplication naive, la taille de F_n est proportionnelle a n (a cause de l'equivalent), donc le temps necessaire pour faire la derniere multiplication est proportionnel a n^2! Bien entendu, il faut faire la meme analyse pour l'algo iteratif, mais la on n'a que des additions a faire, le temps total est proportionnel a n^2. Ce n'est qu'en faisant une multiplication rapide des entiers qu'on doit pouvoir gagner avec le produit matriciel. Une analyse sans doute beaucoup trop difficile au lycee, mais pertinente pour l'agreg option C!

alain974
Messages : 104
Inscription : lun. mai 24, 2010 11:15 am

Re: Fibonacci et temps de calcul

Message par alain974 » mer. nov. 03, 2010 9:43 am

parisse a écrit :en effet, le nombre d'etapes est logarithmique,
...

Une analyse sans doute beaucoup trop difficile au lycee
L'équation récurrente en bas de l'article d'Eppstein u(n)=O(1)+u(n/2) pourrait être intéressante à résoudre algorithmiquement (genre calculer quelques dizaines de termes d'une suite u telle que u(2n+1) et u(2n) sont égaux à A+u(n)...) voire démontrer par récurrence qu'une telle suite est majorée par log(n) :?:

Évidemment le problème c'est d'expliquer aux élèves en quoi ça s'applique à l'algorithmique...

N'ayant pas de Terminale S, ce n'est pas moi qui m'y colle :P

Répondre