¿Por qué los números de Fibonacci son significativos en ciencias de la computación?

Los números de Fibonacci tienen todo tipo de propiedades matemáticas muy buenas que los hacen excelentes en ciencias de la computación. He aquí algunas:

1. crecen exponencialmente rápido. Una estructura de datos interesante en la que surge la serie de Fibonacci es el árbol AVL, una forma de árbol binario auto-equilibrado. La intuición detrás de este árbol es que cada nodo mantiene un factor de equilibrio para que las alturas del subárbol izquierdo y derecho difieran como máximo en uno. Debido a esto, se puede pensar en el número mínimo de nodos necesarios para obtener un árbol AVL de altura h se define por una recurrencia que se parece a N(h + 2) ~= N(h) + N (h + 1), que se parece mucho a la serie de Fibonacci. Si calculas las matemáticas, puedes demostrar que el número de nodos necesarios para obtener un árbol AVL de altura h es F (h + 2) - 1. Debido a que la serie de Fibonacci crece exponencialmente rápido, esto significa que la altura de un árbol AVL es a lo sumo logarítmica en el número de nodos, lo que le da la O (lg n) tiempo de búsqueda que conocemos y amamos sobre á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 el número de nodos que puede tener en una cierta profundidad con un número de Fibonacci.
2. Cualquier número se puede escribir como la suma de Fibonacci único numero. Esta propiedad de los números de Fibonacci es crítica para que la búsqueda de Fibonacci funcione; si no pudiera sumar números únicos de Fibonacci en ningún número posible, esta búsqueda no funcionaría. Contrasta esto con muchas otras series, como 3ⁿ o los números catalanes. Esto también es parcialmente por qué muchos algoritmos como potencias de dos, creo.
3. Los números de Fibonacci son computables eficientemente. El hecho de que la serie se puede generar 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 complicado computacionalmente, IIRC. Además de esto, los números de Fibonacci tienen una buena propiedad donde, dados dos números consecutivos de Fibonacci, 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 restas (F(k + 1) - F(k) = F(k - 1)). Esta propiedad se explota en varios algoritmos, junto con la propiedad (2), para dividir los números en la suma de los números de Fibonacci. Por ejemplo, Fibonacci search utiliza esto para localizar valores en la memoria, mientras que un algoritmo similar se puede utilizar para calcular logaritmos de manera rápida y eficiente.
4. Son pedagógicamente útiles. Enseñar recursión es complicado, y la serie Fibonacci es una gran manera de introducirla. Puedes hablar sobre la recursión recta, sobre la memoización o sobre la programación dinámica al introducir la serie. Además, la sorprendente forma cerrada para los números de Fibonaccia menudo se enseña como un ejercicio de inducción o en el análisis de series infinitas, y la ecuación de matriz relacionada para los números de Fibonacci se introduce comúnmente en el álgebra lineal como una motivación detrás de vectores propios y valores propios. Creo que esta es una de las razones por las que son tan de alto perfil en clases introductorias.

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