I1M2010: Programación dinámica en Haskell y el problema del producto de cadenas de matrices
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos estudiado el patrón de programación dinámica en Haskell.
Comenzamos la clase analizando los inconvenientes de la técnica del divide y vencerás en el cálculo de la sucesión de Fibonacci y cómo la corregirlos mediante programación dinámica.
A continuación, se vió la implementación del patrón de programación dinámica en Haskell y se aplicó el patrón a la sucesión de Fibonacci lo que permitió comprobar experimentalmente la ganancia en eficiencia respecto de la solución mediante divide y vencerás.
Finalmente, se aplicó el patrón de programación dinámica a la resolución del problema del producto de cadenas de matrices (en inglés, “matrix chain multiplication”) que consiste en dada una sucesión de matrices encontrar la manera de multiplicarlas usando el menor número de productos de elementos.
Las transparencias usadas en la clase son las páginas 1-39 del tema 24:
El código se encuentra en
- Dinamica: Patrón de la programación dinámica.
- Fibonacci: Fibonacci como ejemplo de programación dinámica.
- ProductoDeCadenaDeMatrices: Producto de cadenas de matrices.
y las librerías auxiliares están en el directorio de códigos.