I1M2017

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 ejempos 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

En la primera parte de la clase hoy de Informática de 1º del Grado en Matemáticas se ha explicado el tema de análisis de la complejidad de los algoritmos.

Se empezó explicando la notación de Landau y los órdenes de complejidad. A continuación se presentaron varios ejemplos de definiciones de distintos órdenes. En cada ejemplo, se especificó el problema, se definió la función, se hizo una tabla sobre la variación de los tiempos y su correspondiente gráfica, se extrajeron las ecuaciones en recurrencia, se resolvieron con Wolfram Alpha y se demostró por inducción el orden de la definición.

Como resumen, en la siguiente tabla se muestra los ejemplos presentados

Los apuntes correspondientes a la clase son