Pourquoi les nombres de Fibonacci sont importantes en informatique ?

Question

Les nombres de Fibonacci sont devenus populaires introduction à la récursivité pour les étudiants en Sciences Informatiques et il y a un argument fort qu'ils persistent au sein de la nature. Pour ces raisons, beaucoup d'entre nous sont familiers avec eux.

Ils existent également au sein de l'Informatique d'ailleurs; étonnamment efficace des structures de données et algorithmes basés sur la séquence.

Il existe deux principaux exemples qui viennent à l'esprit:

• Des tas de Fibonacci qui ont mieux amorti courir de temps que binomiale des tas.
• Fibonacci de recherche qui partage O(log N) temps de fonctionnement avec des binaires recherche sur un tableau ordonné.

Est-il une propriété particulière de ces numéros qui leur donne un avantage sur les autres suites numériques? Est-ce une qualité spatiale? Quelles sont les autres applications possibles pourraient-ils avoir?

Il me semble étrange qu'il y a beaucoup de naturel des séquences de nombres qui se produisent dans d'autres récursive des problèmes, mais je n'ai jamais vu un Catalan tas.

Answer 1

Les nombres de Fibonacci ont toutes sortes de très belles propriétés mathématiques qui font d'eux d'excellents en informatique. Voici quelques-uns:

1. Ils croissent de façon exponentielle rapide. Une intéressante structure de données dans laquelle la suite de Fibonacci est l'arbre AVL, une forme d'auto-équilibrage arbre binaire. L'intuition derrière cet arbre est que chaque nœud maintient un équilibre facteur, de sorte que les hauteurs de la gauche et à droite de la sous-arborescence diffèrent par un seul. De ce fait, vous pouvez considérer que le nombre minimum de nœuds nécessaires pour obtenir un arbre AVL de hauteur h est définie par une récurrence qui ressemble à N(h + 2) ~= N(h) + N(h + 1), qui ressemble beaucoup de la suite de Fibonacci. Si vous faites le calcul, vous pouvez montrer que le nombre de nœuds nécessaires pour obtenir un arbre AVL de hauteur h est F(h + 2) - 1. Parce que la suite de Fibonacci croît de façon exponentielle rapide, ce qui signifie que la hauteur d'un arbre AVL est au plus logarithmique en le nombre de nœuds, vous donnant le temps O(lg n) recherche du temps que nous connaissons et aimons au sujet de la balance des arbres binaires. En fait, si vous pouvez limiter la taille de la structure avec un nombre de Fibonacci, vous êtes susceptible d'obtenir un O(lg n) moteur d'exécution d'une opération. C'est la vraie raison pour laquelle les tas de Fibonacci sont appelés les tas de Fibonacci - la preuve que le nombre de segments après une file d'attente min consiste à évaluer le nombre de nœuds que vous pouvez avoir dans une certaine profondeur, avec un nombre de Fibonacci.
2. N'importe quel nombre peut être écrit comme la somme unique de nombres de Fibonacci. Cette propriété des nombres de Fibonacci est essentiel pour obtenir de Fibonacci de recherche de travail à tous; si vous ne pouvez pas ajouter un ensemble unique de nombres de Fibonacci dans n'importe quel nombre possible, cette recherche ne fonctionne pas. Cela contraste avec beaucoup d'autres séries, comme 3ⁿ ou les nombres de Catalan. C'est aussi en partie pourquoi beaucoup d'algorithmes comme des puissances de deux, je pense.
3. Les nombres de Fibonacci sont efficacement calculable. Le fait que la série peut être généré de manière extrêmement efficace (vous pouvez obtenir les n premiers termes en O(n) ou n'importe quel terme en O(lg n)), alors un grand nombre d'algorithmes qui les utilisent ne serait pas pratique. Générer des nombres de Catalan est assez difficile de calcul, IIRC. En plus de cela, les nombres de Fibonacci ont une belle propriété où, en raison de deux nombres de Fibonacci consécutifs, disons F(k) et F(k + 1), on peut facilement calculer la suivante ou précédente, le nombre de Fibonacci en ajoutant les deux valeurs (F(k) + F(k + 1) = F(k + 2)) ou en soustrayant (F(k + 1) - F(k) = F(k - 1)). Cette propriété est exploitée dans plusieurs algorithmes, en conjonction avec la propriété (2), pour rompre les chiffres dans la somme des nombres de Fibonacci. Par exemple, Fibonacci de recherche utilise pour localiser les valeurs en mémoire, tandis qu'un algorithme similaire peut être utilisé pour rapidement et efficacement calculer des logarithmes.
4. Ils sont pédagogiquement utile. L'enseignement de la récursivité est délicate, et la suite de Fibonacci est une excellente façon de le présenter. Vous pouvez parler de tout droit de récursivité, à propos de memoization, ou sur la programmation dynamique lors de l'introduction de la série. En outre, l'étonnante forme fermée pour les nombres de Fibonacci est souvent enseigné comme un exercice d'induction dans l'analyse des séries infinies, et la matrice de l'équation pour les nombres de Fibonacci est généralement introduit dans l'algèbre linéaire est une motivation derrière les vecteurs propres et les valeurs propres. Je pense que c'est une des raisons pour lesquelles ils sont si haut profil des cours d'introduction.

Je suis sûr qu'il ya plus de raisons que tout simplement cela, mais je suis sûr que certaines de ces raisons sont les principaux facteurs. Espérons que cette aide!

Answer 2

Le plus grand Commun Diviseur est une autre magie; voir ce beaucoup trop de magie. Mais les nombres de Fibonacci sont faciles à calculer; en outre, il a un nom spécifique. Par exemple, les nombres naturels 1,2,3,4,5 ont trop de logique; tous les nombres premiers sont en eux; somme de 1..n est calculable, chacun peut produire avec d'autres, ... mais personne n'en occuper :)

Une chose importante que j'ai oublié c'est le nombre d'Or, qui a impact très important dans la vie réelle (par exemple, vous aimez les grands écrans :)

Answer 3

Si vous avez un algorithme qui peut s’expliquer avec succès dans un mannor simple et concis avec des exemples compréhensibles dans CS et de la nature, quel meilleur outil d’enseignement pourrait quelqu'un arriver à ?

Answer 4

Fibonacci séquences sont en effet retrouvés partout dans la nature/vie. Ils sont utiles à la modélisation de la croissance des populations animales, la croissance des cellules végétales, flocon de neige, forme, plante de la forme, de la cryptographie, et bien sûr l'informatique. J'ai entendu qu'il appelle le modèle de l'ADN de la nature.

Fibonacci tas ont déjà été mentionnés; le nombre d'enfants de chaque nœud dans le tas est au plus log(n). Aussi le sous-arbre de départ d'un nœud avec m enfants est au moins (m+2)ème nombre de fibonacci.

Torrent comme les protocoles qui utilisent un système de nœuds et de supernœuds utiliser un de fibonacci, afin de décider quand un nouveau super-nœud est nécessaire et combien de sous-nœuds, il va gérer. Ils ne nœud de gestion basé sur la spirale de fibonacci (nombre d'or). Voir la photo ci-dessous comment les nœuds sont scission/fusion (partitionné d'une grande place dans les plus petits et vice versa). Voir la photo: http://smartpei.typepad.com/.a/6a00d83451db7969e20115704556bd970b-pi

Certains de ces phénomènes dans la nature

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/sneezewort.GIF

http://img.blogster.com/view/anacoana/post-uploads/finger.gif

http://jwilson.coe.uga.edu/EMAT6680/Simmons/6690Pictures/pinecone3yellow.gif

http://2.bp.blogspot.com/-X5II-IhjXuU/TVbHrpmRnLI/AAAAAAAAABU/nv73Y9Ylkkw/s320/amazing_fun_featured_2561778790105101600S600x600Q85_200907231856306879.jpg

Answer 5

Je ne pense pas qu’il y a une réponse définitive, mais une possibilité est que l’opération de diviser un ensemble S en deux partitions S1 et S2 dont est alors divisée en partitions secondaires S11 et S12, dont a la même taille que S2 - est une approche susceptible de nombreux algorith MS et qui peut être parfois numériquement décrit comme une suite de Fibonacci.