¿Por qué los números de Fibonacci son significativos en informática?

Question

Fibonacci numbers se han convertido en una introducción popular a la recursividad para estudiantes de Ciencias de la Computación y existe un fuerte argumento de que persisten en la naturaleza. Por estas razones, muchos de nosotros estamos familiarizados con ellos.

También existen dentro de Informática en otros lugares; en estructuras de datos y algoritmos sorprendentemente eficientes basados ​​en la secuencia.

Hay dos ejemplos principales que vienen a la mente:

• Fibonacci heaps que tienen mejor amortizar el tiempo de funcionamiento del binomio montones.
• Fibonacci search que comparte O (log N) tiempo de ejecución con binarios buscando en una matriz ordenada.

¿Hay alguna propiedad especial de estos números que les dé una ventaja sobre otras secuencias numéricas? ¿Es una cualidad espacial? ¿Qué otras aplicaciones posibles podrían tener?

Me parece extraño, ya que hay muchas secuencias de números naturales que ocurren en otros problemas recursivos, pero nunca he visto un montón Catalan.

Answer 1

Los números de Fibonacci tienen todo tipo de propiedades matemáticas realmente agradables que los hacen excelentes en informática. Aquí hay algunos:

1. Crecen exponencialmente rápido. Una estructura de datos interesante en la que surge la serie Fibonacci es el árbol AVL, una forma de árbol binario autoequilibrante. La intuición detrás de este árbol es que cada nodo mantiene un factor de equilibrio, de modo que las alturas del subárbol izquierdo y derecho difieren en como máximo uno. Debido a esto, puede pensar en el número mínimo de nodos necesarios para obtener un árbol AVL de altura h definido por una recurrencia que se ve como N (h + 2) ~ = N (h) + N (h + 1), que se parece mucho a la serie de Fibonacci. Si resuelve los cálculos, puede demostrar que la cantidad de nodos necesarios para obtener un árbol AVL de altura h es F (h + 2) - 1. Debido a que la serie Fibonacci crece exponencialmente rápido, esto significa que la altura de un AVL el árbol es como mucho logarítmico en la cantidad de nodos, lo que le da el tiempo de búsqueda O (lg n) que conocemos y apreciamos sobre los árboles binarios equilibrados. De hecho, si puede vincular el tamaño de alguna estructura con un número de Fibonacci, es probable que obtenga un tiempo de ejecución O (lg n) en alguna operación. Esta es la verdadera razón por la que los montones de Fibonacci se llaman montones de Fibonacci, la prueba de que el número de montones después de un minuto de dequeue implica delimitar la cantidad de nodos que puede tener en una cierta profundidad con un número de Fibonacci.
2. Cualquier número puede escribirse como la suma de números únicos de Fibonacci. Esta propiedad de los números de Fibonacci es fundamental para que funcione la búsqueda de Fibonacci; si no puede agregar números únicos de Fibonacci en un número posible, esta búsqueda no funcionaría. Contraste esto con muchas otras series, como 3 ⁿ o los números catalanes. Esto también es parcialmente la razón por la cual muchos algoritmos como potencias de dos, creo.
3. Los números de Fibonacci son computables de manera eficiente. El hecho de que la serie se puede generar de manera extremadamente eficiente (puede obtener los primeros n términos en O (n) o cualquier término arbitrario en O (lg n)), entonces muchos de los algoritmos que los usan no serían prácticos . Generar números catalanes es bastante complejo desde el punto de vista informático, IIRC. Además de esto, los números de Fibonacci tienen una propiedad agradable donde, dados dos números de Fibonacci consecutivos, digamos F (k) y F (k + 1), podemos calcular fácilmente el número de Fibonacci siguiente o anterior agregando los dos valores (F (k) + F (k + 1) = F (k + 2)) o restándolas (F (k + 1) - F (k) = F (k - 1)). Esta propiedad se explota en varios algoritmos, junto con la propiedad (2), para separar los números en la suma de los números de Fibonacci. Por ejemplo, la búsqueda de Fibonacci usa esto para localizar valores en la memoria, mientras que un algoritmo similar puede usarse para calcular logaritmos de manera rápida y eficiente.
4. Son pedagógicamente útiles. La recursividad de la enseñanza es difícil, y la serie de Fibonacci es una excelente manera de presentarla. Puede hablar de recursión directa, de memorización o de programación dinámica al presentar la serie. Además, el increíble closed-form for the Fibonacci numbers se enseña a menudo como un ejercicio de inducción o en el análisis de series infinitas, y el matrix equation for Fibonacci numbers relacionado se introduce comúnmente en el álgebra lineal como una motivación detrás de los vectores propios y los valores propios. Creo que esta es una de las razones por las que tienen un perfil tan alto en las clases introductorias.

Estoy seguro de que hay más razones que solo esto, pero estoy seguro de que algunas de estas razones son los factores principales. ¡Espero que esto ayude!

Answer 2

No creo que haya una respuesta definitiva, pero una posibilidad es la operación de dividir un conjunto S en dos particiones S1 y S2, una de las cuales se divide en las subparticiones S11 y S12, una de las cuales tiene el mismo tamaño que S2 - es un enfoque probable para muchos algoritmos y que a veces se puede describir numéricamente como una secuencia de Fibonacci.

Answer 3

Greatest Common Divisor es otra magia; ver this para demasiadas magias. Pero los números de Fibonacci son fáciles de calcular; también tiene un nombre específico. Por ejemplo, los números naturales 1,2,3,4,5 tienen demasiada lógica; todos los números primos están dentro de ellos; suma de 1..n es computable, cada uno puede producir con otros, ... pero nadie se ocupa de ellos :)

Una cosa importante que olvidé es Golden Ratio, que tiene un impacto muy importante en la realidad vida (por ejemplo, te gustan los monitores anchos :)

Answer 4

Déjame agregar otra estructura de datos a la tuya: árboles Fibonacci. Son interesantes porque el cálculo de la posición siguiente en el árbol puede hacerse mediante la mera adición de los nodos anteriores:

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

Ata bien en la discusión por templatetypedef en AVL-árboles (un árbol AVL en el peor de los casos puede tener estructura de fibonacci). También he visto buffers extendidos en pasos de fibonacci en lugar de potencias de dos en algunos casos.

Answer 5

Si tiene un algoritmo que se puede explicar con éxito de una manera simple y concisa con ejemplos comprensibles en CS y naturaleza, ¿qué mejor herramienta de enseñanza podría encontrar alguien?

Answer 6

Las secuencias de Fibonacci se encuentran en todas partes en la naturaleza/vida. Son útiles para modelar el crecimiento de las poblaciones de animales, el crecimiento de células vegetales, la forma del copo de nieve, la forma de la planta, la criptografía y, por supuesto, la informática. He oído que se lo conoce como el patrón de ADN de la naturaleza.

Fibonacci heap ya se han mencionado; el número de hijos de cada nodo en el montón es a lo sumo log (n). También el subárbol que comienza un nodo con m hijos es al menos (m + 2) el número de fibonacci.

Los protocolos tipo Torrent que usan un sistema de nodos y supernodos usan un fibonacci para decidir cuándo se necesita un nuevo supernodo y cuántos subnodos gestionará.Hacen gestión de nodo basada en la espiral de fibonacci (proporción áurea). Vea la foto a continuación sobre cómo se dividen/fusionan los nodos (particionados de un cuadrado grande en los más pequeños y viceversa). Ver la foto: http://smartpei.typepad.com/.a/6a00d83451db7969e20115704556bd970b-pi

Algunos sucesos en la naturaleza

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 7

sólo para añadir una trivia acerca de esto, los números de Fibonacci describen el empanado de conejos. Empiezas con (1, 1), dos conejos, y luego su población crece exponencialmente.

Answer 8

Su cálculo como una matriz de potencia de [[0,1], [1,1]] se puede considerar como el problema más primitivo de la Investigación operativa (algo así como el dilema del prisionero es el problema más primitivo de la teoría de juegos) .