Pourquoi les nombres de Fibonacci sont-ils significatifs en informatique?

Les nombres de Fibonacci sont devenus une introduction populaire à la récursivité pour les étudiants en informatique et il existe un argument fort en faveur de leur persistance dans la nature. Pour ces raisons, beaucoup d’entre nous les connaissent.

Ils existent aussi dans l’informatique ailleurs aussi; dans des structures de données et des algorithmes étonnamment efficaces basés sur la séquence.

Deux exemples principaux me viennent à l’esprit:

  • Des tas de Fibonacci qui ont mieux amorti le temps de parcours que les tas binomiaux.
  • Recherche Fibonacci qui partage le temps d’exécution O (log N) avec une recherche binary sur un tableau ordonné.

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

Cela me semble étrange car il y a beaucoup de séquences de nombres naturelles qui se produisent dans d’autres problèmes récursifs, mais je n’ai jamais vu de tas catalan .

Les nombres de Fibonacci ont toutes sortes de propriétés mathématiques vraiment intéressantes qui les rendent excellentes en informatique. En voici quelques uns:

  1. Ils grandissent de manière exponentielle rapidement. Une structure de données intéressante dans laquelle la série Fibonacci est présentée est l’arborescence AVL, une forme d’arbre binary auto-équilibré. L’intuition derrière cet arbre est que chaque nœud maintient un facteur d’équilibre de sorte que les hauteurs du sous-arbre gauche et droit diffèrent d’au plus un. De ce fait, vous pouvez penser que le nombre minimum de nœuds nécessaires pour obtenir un arbre AVL de hauteur h est défini par une récurrence qui ressemble à N (h + 2) ~ = N (h) + N (h + 1), qui ressemble beaucoup à la série Fibonacci. Si vous calculez 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. Comme la série Fibonacci croît de manière exponentielle, cela signifie que la hauteur d’une AVL tree est au plus logarithmique dans le nombre de nœuds, ce qui vous donne le temps de recherche O (lg n) que nous connaissons et que nous aimons sur les arbres binarys équilibrés. En fait, si vous pouvez limiter la taille d’une structure à un nombre Fibonacci, vous risquez d’obtenir un runtime O (lg n) sur certaines opérations. C’est la vraie raison pour laquelle les tas de Fibonacci sont appelés tas de Fibonacci – la preuve que le nombre de tas après une file de mise en queue implique de limiter le nombre de nœuds que vous pouvez avoir à une certaine profondeur avec un nombre de Fibonacci.
  2. Tout nombre peut être écrit comme la sum des nombres uniques de Fibonacci. Cette propriété des nombres de Fibonacci est essentielle pour que la recherche de Fibonacci fonctionne; Si vous ne pouviez pas append des nombres uniques de Fibonacci à un nombre quelconque, cette recherche ne fonctionnerait pas. Comparez cela avec beaucoup d’autres séries, comme 3 n ou les numéros catalans. C’est aussi en partie la raison pour laquelle beaucoup d’algorithmes aiment des puissances de deux, je pense.
  3. Les nombres de Fibonacci sont calculables efficacement. Le fait que les séries puissent être générées de manière extrêmement efficace (vous pouvez obtenir les n premiers termes dans O (n) ou tout terme arbitraire dans O (lg n)), alors que beaucoup d’algorithmes qui les utilisent ne seraient pas pratiques. Générer des chiffres en catalan est assez compliqué du sharepoint vue informatique, IIRC. En plus de cela, les nombres de Fibonacci ont une belle propriété où, étant donné deux nombres de Fibonacci consécutifs, disons F (k) et F (k + 1), nous pouvons facilement calculer le nombre suivant ou précédent de Fibonacci en ajoutant les deux valeurs (F (k) + F (k + 1) = F (k + 2)) ou en les soustrayant (F (k + 1) – F (k) = F (k – 1)). Cette propriété est exploitée dans plusieurs algorithmes, conjointement avec la propriété (2), pour séparer les nombres en la sum des nombres de Fibonacci. Par exemple, la recherche Fibonacci utilise ceci pour localiser des valeurs en mémoire, tandis qu’un algorithme similaire peut être utilisé pour calculer rapidement et efficacement des logarithmes.
  4. Ils sont pédagogiquement utiles. Enseigner la récursivité est délicat et la série Fibonacci est un excellent moyen de la présenter. Vous pouvez parler de récursivité directe, de mémorisation ou de programmation dynamic lors de l’introduction de la série. En outre, l’étonnant format fermé des nombres de Fibonacci est souvent enseigné comme exercice d’induction ou d’parsing de séries infinies, et l’ équation masortingcielle associée aux nombres de Fibonacci est couramment utilisée en algèbre linéaire comme motivation des vecteurs propres et des valeurs propres. Je pense que c’est l’une des raisons pour lesquelles ils sont très présents dans les cours d’introduction.

Je suis sûr qu’il y a plus de raisons que cela, mais je suis sûr que certaines de ces raisons sont les principaux facteurs. J’espère que cela t’aides!

Le plus grand diviseur commun est une autre magie; voyez cela pour trop de magie. Mais les nombres de Fibonacci sont faciles à calculer; il a aussi un nom spécifique. Par exemple, les nombres naturels 1,2,3,4,5 ont trop de logique; tous les nombres premiers sont en leur sein; sum de 1..n est calculable, chacun peut produire avec d’autres, … mais personne ne s’occupe d’eux 🙂

Une chose importante que j’ai oubliée est Golden Ratio , qui a un impact très important dans la vie réelle (par exemple, vous aimez les moniteurs larges 🙂

Si vous avez un algorithme qui peut être expliqué avec succès dans un manuel simple et concis avec des exemples compréhensibles de CS et de la nature, quel meilleur outil pédagogique quelqu’un pourrait-il trouver?

Les séquences de Fibonacci sont en effet présentes partout dans la nature / la vie. Ils sont utiles pour modéliser la croissance des populations animales, la croissance des cellules végétales, la forme des flocons de neige, la forme des plantes, la cryptographie et, bien sûr, l’informatique. J’ai entendu parler de la structure de l’ADN.

Les tas de Fibonacci ont déjà été mentionnés; le nombre d’enfants de chaque nœud dans le tas est au plus log (n). De même, le sous-arbre commençant par un nœud avec m enfants est au moins (m + 2) ième nombre de fibonacci.

Les protocoles de type Torrent qui utilisent un système de nœuds et de super-nœuds utilisent un fibonacci pour décider quand un nouveau super-nœud est nécessaire et combien de sous-nœuds il va gérer. Ils gèrent les nœuds en fonction de la spirale de fibonacci (nombre d’or). Voir la photo ci-dessous comment les nœuds sont divisés / fusionnés (partitionnés d’un grand carré en plus petits et vice versa). Voir photo: http://smartpei.typepad.com/.a/6a00d83451db7969e20115704556bd970b-pi

Quelques événements dans la nature

http://soffr.miximages.com/algorithm/sneezewort.GIF

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

http://soffr.miximages.com/algorithm/pinecone3yellow.gif

http://soffr.miximages.com/algorithm/amazing_fun_featured_2561778790105101600S600x600Q85_200907231856306879.jpg

Je ne pense pas qu’il y ait 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 l’une est alors divisée en sous-partitions S11 et S12, dont l’une a la même taille que S2 – est une approche probable de nombreux algorithmes et peut parfois être décrite numériquement comme une séquence de Fibonacci.

Permettez-moi d’append une autre structure de données à la vôtre: les arbres Fibonacci. Ils sont intéressants car le calcul de la prochaine position dans l’arbre peut se faire par simple addition des nœuds précédents:

http://xw2k.nist.gov/dads/html/fibonacciTree.html

Cela s’accorde bien avec la discussion par templatetypedef sur les arbres AVL (un arbre AVL peut au pire avoir une structure fibonacci). J’ai également vu des tampons étendus dans des étapes de fibonacci plutôt que des puissances de deux dans certains cas.

Juste pour append une anecdote à ce sujet, les chiffres de Fibonacci décrivent la panure des lapins. Vous commencez avec (1, 1), deux lapins, puis leur population augmente de façon exponentielle.

Leur calcul comme puissance de masortingce [[0,1], [1,1]] peut être considéré comme le problème le plus primitif de la recherche opérationnelle (un peu comme le dilemme du prisonnier est le problème le plus primitif de la théorie des jeux).