¡Gracias por visitar Tecno Academy!                     Informática, todos los niveles - Trucos - Apuntes - Diapositivas - Libros - Enlaces - Curiosidades - Descargas - Tecnologías - Opiniones - Podcasting, Byte - Internautas TV - Pizarra Virtual                   

viernes, 28 de septiembre de 2007

¿Qué es la programación dinámica?

A veces me preguntan qué es eso de la Programación Dinámica, suponiendo que se trata en realidad de alguna metodología de programación. Pero no, no es nada relacionado con el desarrollo rápido de aplicaciones. Se trata de un esquema algorítmico o, dicho de otro modo, es una manera de construir algoritmos para resolver problemas. En realidad deriva de la técnica Divide y Vencerás que trata de descomponer el problema en subproblemas más sencillos que se resuelven independientemente para, una vez resueltos y combinados, dar solución al problema original. Es decir, ambos esquemas se basan en el razonamiento inductivo. La diferencia estriba en que los algoritmos Divide y Vencerás suelen implementarse de manera recursiva ya que la recursividad se adapta de forma muy natural a la solución. Pero, ¡como siempre tiene que haber un "pero"...! La gran limitación de los algoritmos Divide y Vencerás implementados como recursivos es que en ocasiones no pueden ser llevados a la práctica porque la pila de ejecución no tiene suficiente capacidad como para dar soporte a todas las llamadas recursivas, debido a que se producen tantas llamadas repetidas que la complejidad algorítmica se dispara y con ella el tiempo de ejecución y el uso de memoria. Veámoslo con un ejemplo sencillo: la función de Fibonacci es archiconocida por matemáticos, informáticos y últimamente por los lectores de "El código da Vinci". Nosotros la vamos a definir como,

Si lo resolvemos con Divide y Vencerás obtendríamos el siguiente pseudocódigo:


El problema de esta implementación es que, si nos fijamos en un árbol de llamadas cualquiera, por ejemplo para n=5, vemos que las repeticiones de invocaciones idénticas son más abundantes a medida que bajamos en nivel. Esto convierte al algoritmo en exponencial, del orden exacto de 1,62^n.



La programación dinámica consiste, básicamente, en guardar los resultados parciales en una tabla en vez de en la pila de ejecución, lo que permite reutilizar cuantas veces se desee dichos resultados. Con lo que ahora conseguimos que la complejidad sea lineal.

La mala noticia es que éste es un ejemplo extremadamente sencillo. La mayoría de problemas son mucho más difíciles de plantear y exigen usar matrices bidimensionales como mínimo. Pero, ¡tiempo al tiempo!, en futuros post os ilustraré con ejemplos "más profesionales".

No hay comentarios: