I1M2019: 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.
La clase se ha dado mediante videoconferencia y el correspondiente vídeo es
Los apuntes correspondientes a la clase son
Una versión interactiva de los apuntes en IHaskell se encuentra aquí.