Discuter:Suite de Fibonacci

Un article de Wikipédia, l'encyclopédie libre.

WikiProjet Mathématiques
 Suite de Fibonacci fait partie du projet Mathématiques, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés aux mathématiques. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet, où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail Mathématiques pourrait aussi vous intéresser.
À évaluer Cet article a été classé comme d'Avancement ? selon le Tableau d'évaluation du projet. (Voir les statistiques)
Élevée Cet article a été classé comme d'Importance élevée selon le Tableau d'évaluation du projet.

Sommaire

[modifier] aka

Bonjour,

Est ce que quelqu'un sait ce que signifie en anglais aka et ca dans :

Leonardo de Pisa aka. Fibonacci (ca. 1200) ?

aka=alias ?

COLETTE 7 avr 2003 à 11:45 (CEST)

Bonjour,
aka = "also known as", aussi connu sous le nom de...
Yendred 7 avr 2003 à 11:49 (CEST)
AKA = Alias Rinaldum...
Merci bien
Lillejul 31 jan 2005 à 11:27 (CEST)
"ca." en anglais, ainsi que dans plusieurs autres langues (en tous cas Allemand, Suédois et Italien) est l'abréviation pour "circa" qui veut dire "environ"

[modifier] Démonstrations

Personnellement, je trouve que les démonstrations alourdissent l'article. De plus, elles ne sont que partiellement justes (récurrence forte, récurrence limitée). Je tente des mises en boites et des corrections, mais cela va prendre du temps.HB 25 juillet 2005 à 12:13 (CEST)

ca y est (ouf!). J'ai corrigé les démonstrations fausses (récurrence simple au lieu d'une récurrence d'ordre 2) Modifié certaines, déplacé quelques propriétés, en ai supprimé une (mal écrite et sans intérêt) et tout mis dans des boites (ce qui hélas empêche la jolie présentation en tableau). Le tout est à relire par quelqu'un de courageux. Personnellement je pense que toutes ces propriétés (et leurs démonstrations) n'ont pas vraiment leur place dans l'article (on n'écrit pas un traité sur la suite de Fibonacci, seulement un article) mais j'attends d'autres avis. HB 25 juillet 2005 à 19:41 (CEST)
j'intervient ici juste pour dire qu'en tant que non connaisseur je trouve les démontration utiles car expliquant le pourquoi du comment de la Suite de Fibonacci --PierreB49 12 janvier 2006 à 18:37 (CET)
Je trouve l'apport des démonstrations très adapté. De plus les boites permettent le "non alourdissement" de l'article. Vraiment un article de toute beauté ;) Feeder Fan 21 mai 2006 à 03:34 (CEST)

[modifier] La lettre Φ

Je trouve juste étrange que dans cet article la lettre grèque φ soit en majuscule pour désigner le nombre d'or alors que l'article sur le Nombre d'or il est écrit en minuscule. Est-ce une erreur ou y arrait-il une raison ? --PierreB49 12 janvier 2006 à 18:37 (CET)

Entièrement d'accord avec PierreB49 pour passer dans cet article Φ en φ --Claudius 13 janvier 2006 à 23:37 (CET)
Modification effectuée mais en remplaçant Φ en \varphi comme dans l'article du nombre d'or. HB 14 janvier 2006 à 11:50 (CET)

Knuth dans Mathématiques concrètes utilise un phi minuscule \ \phi en écriture droite. Et plutôt qu'un phi' il utilise un phi chapeau.--OPi 3 septembre 2006 à 00:48 (CEST)

[modifier] Programmes

Je ne vois pas l'intérêt de donner plusieurs programmes identiques pour le calcul de la suite de Fibonacci, sachant de plus, que ces programmes sont totalement inefficaces en temps de calcul. Le programme en Caml présente quant à lui l'inconvénient d'user d'un calcul approché en flottant alors que le calcul peut être mené de façon exacte sur les entiers. Il convient donc de les enlever et ne proposer qu'un seul algorithme efficace : celui utilisant une simple boucle itérative sur des entiers. Theon 29 janvier 2006 à 21:25 (CET)

Plusieurs des programmes indiqués sont récursifs terminaux et sont strictement équivalents à une boucle. YBM 21 avril 2006 à 11:08 (CEST)
Je confirme, l'exemple Scheme est bien terminal donc de complexité equivalente à la boucle du code en C. Maintenant, l'algo présenté dans l'article n'est pas performant du tout et peut être facilement optimisé, mais ici ce n'est pas le but recherché, tout du moins je n'en vois pas l'intérêt. Feeder Fan 21 mai 2006 à 03:50 (CEST)
De plus certains programmes sont écrits dans des langages peu intuitifs si on ne les connait pas. Voilà un exemple assez parlant en Caml pour la version efficace en temps linéaire (à la Kleene). Je la trouve plus évidente que la version Scheme avec notament des notations préfixes pour les opérateurs binaires usuels. Tom 14 septembre 2006 à 15:54 (CEST)
let fibo n =
  let rec f a b = function
  | 0 -> a, b
  | n -> f b (a + b) (n - 1)
in fst (f 1 1 n);;
Pour la version « naïve » c'est encore plus intuitif en Caml :
let rec fibo = function
| 0 | 1 -> 1
| n -> fibo(n - 1) + fibo(n - 2);;
Ainsi celui qui comprend les équations récursives mathématiques comprend le programme, et vice versa. Tom 14 septembre 2006 à 15:56 (CEST)

[modifier] Algorithmes de calcul des nombres de Fibonacci

je cite :

"Calculer exactement les nombres de Fibonacci à partir des puissances du nombre d'or n'est pas pratique du tout, sauf pour les petites valeurs de n, puisque les erreurs d'arrondis s'accroissent et les nombres réels flottants n'ont habituellement pas assez de précision."

JE trouve cette remarque vraiment trop peu nuancée.

Déjà, le calcul de la puissance du nombre d'or est pratique justement ! puisqu'on obtient le nombre de Fibonacci uniquement par un calcul direct, sans passer par un calcul itératif (ou programmation d'une boucle) forcément long (surtout à la main). C'est à dire, qu'avec une calculatrice de poche on peut connaître directement les valeurs que prend les nombres de Fibonacci. Si cela n'est pas pratique ! alors...?

Ensuite, la deuxième partie de l'argumentation sur la précision dû aux erreurs d'arrondis, est juste, mais... il faut tout même préciser, qu'avec les 16 décimales et le système de notations scientifiques (un peu près identique pour tout PC, ou calculette) ; l'erreur commise commence qu'à partir de F(71) et "fini" à F(79) en ne dépassant jamais une différence de 2. JE dis que l'erreur fini à F(79) car ensuite le nombre de Fibonacci est trop grand, et est donc tronqué quelle que soit la méthode utilisée.

En conclusion, je pense qu'il faudrait être plus informatif (et objectif) sur le calcul avec le nombre d'or. Et préciser sa limite dû aux erreurs d'arrondis. Car évacuer ce principe de calcul "d'un revers de main" qu'alors il représente le calcul le plus simple... je trouve que cela est gênant.

Je proposerai peut-être la prochaine fois une reformulation sur ce point. En attendant d'avoir des réactions polémiques ou approbatives...

Amicalement, Us.

Pour corriger les erreurs d'arrondis il peut être intéressant d'utiliser le fait que F(n) est pair ssi n est multiple de 3.

Je cite : L'implémentation récursive naïve de la relation de définition de la suite de Fibonacci n'est pas non plus judicieuse, puisque l'on calculerait de nombreuses fois les mêmes valeurs, ce qui conduit à un temps de calcul exponentiel.
Il suffit que la fonction renvoie F(n) et F(n+1). Par exemple en Scheme :

 (define (fibo n)
   (if (= n 0)
       (cons 0 1)
       (let ((fn-1 (fibo (- n 1)))
             (fn 0))
         (set! fn (cdar fn-1))
         (set! fn-1 (car fn-1))
         (cons fn (+ fn fn-1)))))

Je ne ne suis pas sur ma machine là, je le testerai plus tard, mais l'idée y est, l'agorithme est linéaire (si on ne tient pas compte des opérations faites sur les entiers bien sûr).

Je cite : \mathcal F_{2k} = \mathcal F_k^2 + 2\mathcal F_k \mathcal F_{k-1}
\mathcal F_{2k+1} = \mathcal F_k^2 + \mathcal F_{k+1}^2
Le temps de calcul est alors proportionnel au logarithme de n. Voici un exemple de programme en Maple.
Il faut appliquer la même idée, ainsi on obtient un algorithme de complexité logarithmique. --OPi 3 septembre 2006 à 01:17 (CEST)


Les programmes en Maple et Python qui prétendent effectuer un calcul en temps logarithmique sont en réalité de linéraires (et donc pas meilleurs que les programmes Java/Scheme/PHP qui précèdent). Pour obtenir une complexité logarithmique, il faut vraiment exploiter l'idée d'exponentiation efficace et non pas simplement les deux équations qui en sont dérivées juste après. Je peux proposer un code (ou pseudo-code correct) si les auteurs des codes Maple et Python sont d'accord avec moi. --Backtracking 15 mars 2007 à 22:04 (CET)

[modifier] Primalité des nombres de Fibonacci

Attention aux cas limites ! "Si F(n) est premier alors n est premier" comporte une exception. En effet si F(n) = 3 alors n = 4. --OPi 3 septembre 2006 à 01:29 (CEST)

En effet, si n = 4 = 2 × 2 alors F(4) est divisible par F(2) mais comme F(2) = 1, être divisible par 1, c'est relativement facile... En revanche, pour n > 4, n non premier ==> n possède un diviseur strict d supérieur à 2. Comme F(d) divise F(n) et que 1< F(d) <F(n), on peut affirmer que F(n) est non premier. Par contraposée : pour tout n > 4, si F(n) est premier alors n est premier.
Article corrigé en conséquence. Merci. HB 2 octobre 2006 à 19:25 (CEST)

[modifier] Généralisations

En conservant la relation de récurrence la suite s'étend naturellement aux entiers négatifs. On a alors F(-n) = -(-1)n F(n). --OPi 3 septembre 2006 à 01:29 (CEST)


C'est bien dit (mieux que moi), mais... JE tiens à faire une remarque sur la présentation de la suite concernant le niveau de lecture !

  • On part d'un problème concret de Lapins, et en moins deux, on écrit des formules de matheux... Sans compter qu'à la fin de "Expression fonctionnelle" on reprend la présentation générale de la suite... c'est méli-mélo. Pour rajouter, je vois (entre autre), que dans "Bases et espaces vectoriels" on tombe sur "suite de Fibonacci généralisée" qui fait écho à la fin de l'article "Fibonacci généralisée".
  • En somme, je dénonce un problème d'organisation.
  • Je propose une réorganisation, suivant un plan plus progressif. Partons du problème concret, vers une présentation simple (je veux dire par là, avec un niveau de lecture et de généralité assez faible, compréhensible pour un large public), avant de passer vers les premières formules...

Je pense le faire, un peu plus tard, si personne de le fait d'ici là. En attendant des remarques polémiques ou pas...

Amicalement, Us.

pas de remarque polémique de ma part mais un franc encouragement. Réorganise, si tu vois comment faire (moi, j'en ai abandonné l'idée depuis longtemps) tant que cette réorganisation ne fait pas perdre du contenu. Bon courage --HB 26 novembre 2006 à 22:19 (CET)

[modifier] Article de qualité

Pensez-vous que l'article est mûr pour passer en article de qualité? Moi je pense que oui. Valvino 1 octobre 2006 à 11:38 (CEST)

vu le caractère très sélectif des passages en article de qualité, je pense qu'il a peu de chance de jamais passer. Probablement trop technique avec de trop nombreuses formules ou démonstrations, des algorithmes qui soulèvent quelques doutes. Tout en ne sachant pas comment l'améliorer, je ne voterais surement pas pour lui. HB 1 octobre 2006 à 13:25 (CEST)
PS : L'article, très long, est incomplètement vérifié (voir dernière correction de l'erreur pourtant signalée depuis près d'un mois). HB 2 octobre 2006 à 19:27 (CEST)


Concernant:

int fibo(int n){

  if(n < 2) return n;
  return fibo(n-1) + fibo(n-2);
}

Ne serait-il pas plus judicieux d'utiliser des unsigned int? Un terme négatif n'étant pas défini...


PS: Excuser moi pour la mise en forme du code (je n'ai pas trouvé le moyen de la mettre en forme)

[modifier] Exemples d'implémentation..

Bonjour, Je vois dans l'article qu'il y a des exemples dans différents langages mais ça n'apporte rien à part alourdir la page ! Exemple du PHP... Sachant qu'il y a juste au dessus un exemple en C/C++/Java, c'est presque identique, sauf qu'on a des variables $a à la place de a... Je suis pour qu'on le supprime. On va pas s'amuser à donner des exemples dans tous les langages... Dans le cas de la page Hello World, ça se comprend mais là...

Ensuite, il y avait un exemple en tcl, je l'ai commenté car il était recursif (non terminal) et il était dans la partie Algo Linéaire. Si vous n'êtes pas d'accord, libre à vous de le décommenter (mais j'aimerais en connaitre la raison). --Max81 (d) 1 mai 2008 à 15:20 (CEST)

Il faut supprimer tous les exemples, sauf un. Cette collection de programmes dans divers langages tourne au ridicule. Theon (d) 1 mai 2008 à 18:34 (CEST)
Je pense qu'une telle collectiion de programme a plutôt sa place dans un livre d'algorithimque dans wikilivre, mais pas dans wikipedia. Oxyde (d) 1 mai 2008 à 20:45 (CEST)
On est d'accord. J'ai donc supprimé les exemples en php et tcl. J'ai hésité pour Scheme. Je vous laisse le soins de prendre la décision (j'ai rien compris au code donc je sais pas si ça apporte quelque chose ou non). --Max81 (d) 2 mai 2008 à 17:47 (CEST)

[modifier] Qualité du code

Je trouve que ce code pourrait servir d'exemple d'un code pas propre :

int F(int n) {
  int a;
  int b;
  int c;
  int i;
 
  a = 0;
  b = 1;
 
  if (n <= 1) {
    return n;
  } else {
    i = 1;
    while (i < n) {
      c = a + b;
      a = b;
      b = c;
      i = i + 1;
    }
  }
  return c;
}

Les noms de variables ne sont absolument pas explicites et il n'y a aucun commentaire. Si quelqu'un se sent inspiré pour donner des noms plus sympas... Qu'il ne se gène pas ! Personnellement, j'avoue que ce n'est pas mon point fort donc je passe mon tour :). --Max81 (d) 2 mai 2008 à 19:45 (CEST)