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