I1M2018: Programación dinámica en Haskell
En la clase hoy de Informática de 1º del Grado en Matemáticas se ha explicado cómo transformar definiciones recursivas en otras con programación dinámica y la mejora en eficiencia obtenida con la transformación.
Para la explicación se han elegido 6 ejemplos:
- Los números de Fibonacci
- Coeficientes binomiales
- Longitud de la subsecuencia común máxima
- Subsecuencia común máxima
- Distancia de Levenshtein
El estudio de cada uno de los ejemplos ha consistido en
- Enunciar el problema
- Definir una solución por recursión.
- Transformar la definición recursiva en otra con programación dinámica.
- Comparar experimentalmente la eficencia de las dos definiciones.
Los apuntes correspondientes a la clase son