Programación dinámica y la sucesión de Fibonacci

(Wikipediazo)En informática, la programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas.

Decir que un problema tiene subproblemas superpuestos es decir que se usa un mismo subproblema para resolver diferentes problemas mayores. Por ejemplo, en la sucesión de Fibonacci (F3 = F1 + F2 y F4 = F2 + F3) calcular cada término supone calcular F2. Como para calcular F5 hacen falta tanto F3 como F4, una mala implementación para calcular F5 acabará calculando F2 dos o más veces.

Esto se puede evitar guardando las soluciones que ya hemos calculado. Entonces, si necesitamos resolver el mismo problema más tarde, podemos obtener la solución de la lista de soluciones calculadas y reutilizarla. Este acercamiento al problema se llama memoización (no confundir con memorización; en inglés es llamado memoization, véase en). Si estamos seguros de que no volveremos a necesitar una solución en concreto, la podemos descartar para ahorrar espacio.

Comenzando con el pseudocódigo:
FUNC Fibonacci (↓n: NATURAL): NATURAL
   VARIABLES
       tabla: ARRAY [0..n] DE NATURALES
       i: NATURAL
   INICIO
       SI n = 0 ENTONCES
           DEVOLVER 0
       SINOSI n = 1 ENTONCES
           DEVOLVER 1
       SINO
           tabla[0] := 0
           tabla[1] := 1
           PARA i = 2 HASTA n HACER
               tabla[i] := tabla[i-1] + tabla[i-2]
           FINPARA
           DEVOLVER tabla[n]
       FINSI
   FIN

Una implementación en C de este algoritmo es la siguiente (he cambiado los tipos de dato para que se puedan calcular valores más grandes):
long long fibonacciArreglo(int n) {
    long long * lista;
    if(n == 0) return 0;
    if(n == 1) return 1;
    lista = (long long *) malloc(sizeof(long long) * n);
    lista[0] = 0;
    lista[1] = 1;
    int i;
    for (i = 2; i <= n; i++) {
        lista[i] = lista[i-1] + lista[i-2];
    }
    return lista[n];
}
Como podemos ver, se reservan n espacios de memoria para almacenar todos los valores de la sucesión, aunque solamente se emplean dos de estos valores a la hora de cálcular el siguente número. Lo cual deriva en un "desperdicio" de memoria. 

Es por eso que basándome en el enunciado que está más arriba en negritas, pensé que implementar una cola sería una opción para ahorrar espacio, podemos agregar dinámicamente los nuevos valores y quitar los que ya no usaremos, de tal manera solo tendríamos en memoria los valores necesarios para calcular el siguiente número en la sucesión. El código queda como sigue:
long long fibonacciCola(int n) {
    Cola cola;
    if (n == 0) return 0;
    if (n == 1) return 1;
    creaLista(&cola);
    formar(&cola, 0);
    formar(&cola, 1);
    int i;
    for (i = 2; i <= n; i++) {
        // Quitamos el elemento menos reciente
        long long fi1 = atender(&cola);
        // Obtenemos el valor del siguiente más reciente
        long long fi2 = valorPrincipio(&cola);
        // Almacenamos el resultado en la cola
        formar(&cola, fi1 + fi2);
    }
    return valorFinal(&cola);
}
De esta forma aseguramos que para cualquier tamaño de n solo se ocupen a lo más 3 espacios de memoria.

El código está disponible en la sección de extras del proyecto analizando-algo

¡Saludos!
@fferegrino :)

Prácticas de análisis de algoritmos [ESCOM]

A lo largo del semestre, en la materia de Análisis de Algoritmos que llevo con el profesor Edgardo Franco tenemos que realizar varias prácticas. Las prácticas consisten en programar algoritmos conocidos para analizar su comportamiento, tanto en tiempo como en memoria consumida, mientras resuelven problemas de "gran" tamaño.

Muchas (si no es que todas D:) estarán hechas para C, para Linux, esto debido a la librería empleada para medir los tiempos que consume la ejecución del algoritmo. Para facilitar la compilación cada práctica cuenta con un archivo Makefile, el cual contiene todas las instrucciones para compilar y ejecutar las prácticas. Dado que tenemos que analizar los tiempos de ejecución y a veces estos pueden ser muchos, para la ejecución de cada programa redireccionamos la salida estandar para que escribiera directamente a un archivo que podemos manejar sencillamente en una hoja de cálculo. Esto se puede ver en el archivo .sh que acompaña a cada práctica.

Todas las prácticas tienen comentarios, unas más, otras menos, pero los tienen. Aún así si queda alguna duda pues no dudes en preguntar. Otra cosa importante es que estas son solo las propuestas de solución que presentamos, no las copies directamente, basate en ellas o usa porciones del código, eso se vale. El link de descarga está al final del artículo ;).

Hasta el momento hemos realizado 3 prácticas:

Práctica 1: "Pruebas a posteriori (Algoritmos de ordenamiento)"

Con base en el archivo de entrada proporcionado que tiene 200,000 números diferentes. Ordenarlo bajo los siguientes métodos de ordenamiento y comparar experimentalmente las complejidades de estos.
  • Burbuja (Bubble Sort)
  • Burbuja Simple
  • Burbuja Mejorada
  • Inserción (Insertion Sort)
  • Selección (Selection Sort )
  • Shell (Shell Sort)
  • Ordenamiento con árbol binario de busqueda (Binary Search Tree)

Práctica 2: "Análisis temporal y notación de orden (Algoritmos de busqúeda)"

Con base en el ordenamiento obtenido a partir del archivo de entrada de la práctica 01 que tiene 200,000 números diferentes. Realizar la búsqueda de elementos bajo 3 métodos de búsqueda y variantes con procesos ligeros, realizar el análisis teórico y experimental de las complejidades; así como encontrar las cotas de los algoritmos.
  • Búsqueda lineal o secuencial (No recursiva)
  • Búsqueda binaria o dicotómica (No recursiva)
  • Búsqueda en un árbol binario de búsqueda (No recursiva)
  • Modificar los tres algoritmos para trabajar con procesos ligeros (Hilos).

Práctica 3: "Divide y vencerás (Rotación de una imagen)"

Implementar el algoritmo de rotación de imágenes que emplea la técnica divide y vencerás. La imágen a girar es cuadrada, y es un .bmp de 24 bits.

Descargas:
Como desde hace tiempo, puedes seguir el proyecto en GitHub analizando-algo (recomendado)
O descargar cada una de las tres prácticas de manera individual:
Práctica 3
Práctica 2
Práctica 3


¡Saludos!
@fferegrino :)