Menu Close

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í.

I1M2019