Técnica de búsqueda de Fibonacci

República Bolivariana de Venezuela.

Ministerio del Poder Popular para la Defensa.

Universidad Nacional Experimental Politécnica de la Fuerza Armada Nacional Bolivariana.

Núcleo Falcón – Sede Coro.

VI Semestre de Ingeniería de Sistemas “A”.

[pic 1]

Bachilleres:[pic 2]

Julio Adam V-26.436.231.

Mairelys González V-26.874.249.

Santa Ana de Coro; Mayo del 2019.

Técnica de búsqueda de Fibonacci:

Así se le llama en Ciencias de la Computación a una técnica que utiliza los llamados números de Fibonacci (los arrojados por la sucesión homónima), los cuales permiten disminuir las ubicaciones posibles de un elemento a buscar dentro de un arreglo de datos ya ordenado (los valores de las abscisas de una función). Tiene la ventaja de disminuir ligeramente el tiempo promedio para acceder a la ubicación de almacenamiento. Pero hay que tener en cuenta que este método no sirve al tener un coeficiente de error alto. El método dice así:

“Dado un arreglo ordenado ‘A’ y un elemento ‘t’, verificar si ‘t’ se encuentra en ‘A’: Sea ‘F’ el arreglo que contiene los números de Fibonacci. Fm es el m-ésimo elemento dentro de ‘F’. ‘n’ es el tamaño del arreglo ‘A’. Sea m tal que Fm es el número más pequeño de ‘F’ mayor o menor que ‘n’. F es definido como F0 = 1, F1 = 1, Fk = Fk-1 + Fk-2”

Dicho esto, si queremos comprobar que el elemento ‘t’ se encuentra en el arreglo ‘A’, necesitamos realizar los siguientes seis (6) pasos:

1. Igualar un valor ‘K’ (valor cualquiera) a ‘m’.
2. Si ‘K’ es igual a cero, se detiene el ciclo. Si no coinciden, entonces ‘t’ no se encuentra en el arreglo.
3. Comparamos el elemento ‘t’ con el elemento de ‘A’ en la posición Fk-1.
4. Si éstos son iguales, entonces ‘t’ se encuentra en el arreglo ‘A’.
5. Si ‘t’ es menor, entonces descartamos los valores que se encuentran desde Fk-1 hasta ‘n’. Hacemos que K sea igual a k-1 y regresamos al paso 2.
6. Si ‘t’ es mayor, descartamos los valores desde 1 hasta Fk-1. Reenumeramos los valores restantes en el arreglo e igualamos K a k-2, posteriormente regresamos al paso 2.

Como pudimos ver, es un proceso iterativo, se va a repetir tantas veces como elementos posea el arreglo hasta encontrar el valor buscado.

V.g. Imaginemos que en determinada función queremos encontrar el valor 5. Graficamos nuestra función cualquiera que sea, y en el eje de las abscisas colocamos los límites de dicha función, a los cuales llamaremos ‘a’ para el inferior y ‘b’ para el superior. Debajo de esta gráfica colocaremos una línea que indicará la longitud horizontal demarcada por los límites. A la cual dividiremos según el valor arrojado por Fm siendo m un valor arbitrario K.

[pic 3]

 Una vez realizada la división de la recta, empezamos con las iteraciones.

¿K es igual a cero? No. Si fuese así, y el valor a buscar (t) fuese cero, entonces el valor se encontraría automáticamente, sino, no se encontraría y terminaría el ciclo.

¿Es t (5) igual a k-1(3)? No. Pasamos al siguiente.

¿Es t (5) menor a k-1(3)? No.  

¿Es t (5) mayor a k-1 (3)? Sí. Por tanto, descartamos todos los valores desde el inicio de la recta hasta k-1. Posteriormente K pasa a ser el nuevo k-2, k-1 será un valor arbitrario que en este caso graficaremos en la mitad del segmento sobrante, K será el final del mismo.

Luego de esto, iniciamos una nueva iteración.[pic 4]

¿K es igual a cero? No. ¿T es igual k-1? No. ¿T es menor que k-1? Sí. Entonces, K pasa a ser k-1 y éste se vuelve un número aleatorio que colocaríamos a la mitad (5.25).

De esta forma vamos eliminando espacio sobrante hasta dar con que ‘t’ sea igual a k-1 y que éste a su vez sea igual a k-2, es decir t= k-1=k-2=5 ∴ t = 5, o al menos el más aproximado. Estas iteraciones generalmente se tabulan para llevar un control de la operación.

Método de Interpolación Cuadrática:

Por interpolación cuadrática entendemos a una función aproximada que permite optimizar nuestra función polinómica, la cual es de orden 2, proporcionando una aproximación a un máximo descrito por dicha función. [pic 5]

Aquí tenemos una función polinómica de la cual encontramos cuatro puntos. X0 que representa el inicio del intervalo (Así como a, en el método de Fibonacci), X1 un punto intermedio, X2 como final del intervalo a estudiar (Como b en Fibonacci) y X3 que representaría en este caso el punto máximo de la función cuadrática.

Se dice que, si para dos puntos existe una sola línea recta para conectarlos, existe una parábola para conectar tres. La cual se ajusta según los puntos para contener un máximo (X3). Para encontrarlo hacemos uso de la siguiente ecuación recursiva:[pic 6]

Al igual que con el método de Fibonacci, aquí se buscará eliminar los diferentes espacios sobrantes hasta alcanzar el punto máximo o mínimo de la función.

Se parte teniendo la función, los valores y un coeficiente de error, que será el que nos indique el fin del ciclo, a través de la siguiente ecuación:[pic 7]

El algoritmo consiste en los siguientes pasos:

1. Graficar la función.
2. Identificar los puntos en dicha función y expresarlos en la ecuación recursiva.
3. Pasamos a evaluar qué sección será descartada para ir acercándonos al punto máximo o mínimo. En esto se nos presentarían dos casos:

1. Si, por ejemplo, estamos buscando un mínimo, y descubrimos que F(X1) es menor a F(X2) entonces, nos da a entender que el óptimo en cuestión se encuentra en el intervalo [X0, X2], por tanto, descartamos la sección [X2, X3]. Aquí X3 pasará a tomar el puesto de X2.

[pic 8]

1. En caso contrario, si seguimos buscando un mínimo y descubrimos que F(X1) es mayor a F(X2), Entonces nos damos cuenta de que el óptimo no se encuentra en el intervalo [X0, X1], por tanto, éste es descartado y X0 pasa a ser X1.

[pic 9]

1. Luego de descartar, repetimos el ciclo.

V.g. Tenemos los siguientes valores iniciales:

Los graficamos:[pic 10]

Iremos iterando e iterando, descartando y descartando, hasta que el valor absoluto de la diferencia entre X0 y X2 sea menor al coeficiente de error dado en los valores iniciales. Dando como resultado la siguiente gráfica:

...