Algorítmica

En la segunda parte de la clase de hoy del curso de Informática de 1º del Grado en Matemáticas hemos continuado el estudio de los tipos abstractos (TAD) de datos en Haskell y hemos presentados el TAD de las colas siguiendo el esquema usado para el TAD de las pilas.

Se ha comenzado la modelización de las pilas observando la forma de introducir o extraer sus elementos. El resultado de la modelización es la especificación del TAD: su signatura y propiedades características.

A continuación se han estudiados dos implementaciones (una basada listas y la otra en pares de listas) juntos con sus complejidades.

Se ha vuelto a resaltar la forma de conseguir la abstracción de tipos en Haskell mediante módulos y exportación sólo de la signatura.

Finalmente, usando QuickCheck se comprueban las propiedades características del TAD de las colas.

Los apuntes correspondientes a la clase son los del tema 15

En la primera parte de la clase de hoy del curso de Informática de 1º del Grado en Matemáticas hemos empezado el estudio de los tipos abstractos (TAD) de datos en Haskell.

Después de tratar de la abstracción, los TAD en general y su analogía con las estructuras algebraicas, se ha estudiado el primero de los TAD: las pilas.

Se ha comenzado la modelización de las pilas observando la forma de introducir o extraer sus elementos. El resultado de la modelización es la especificación del TAD: su signatura y propiedades características.

A continuación se han estudiados dos implementaciones (una basada en tipos de datos algebraicos y otra en listas) y las complejidades de las operaciones.

Un punto importante es la forma de conseguir la abstracción de tipos en Haskell mediante módulos y exportación sólo de la signatura.

Finalmente, usando QuickCheck se comprueban las propiedades características del TAD de las pilas.

Los apuntes correspondientes a la clase son los del tema 14

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

En la la segunda parte de la clase de hoy de del curso Informática de 1º del Grado en Matemáticas hemos estudiado la técnica de resolución de problemas mediante búsqueda en espacios de estados.

La clase comenzó analizando los árboles de búsquedas para el problema de las 4 reinas y para el problema del 8-puzzle

De este análisis se extrae el patrón de resolución de problemas mediante búsqueda en espacios de estados (EE) y sus argumentos:

• cuál es el estado inicial,
• cómo se calculan los sucesores de un estado y
• cómo decidir si un estado es un estado final.

A continuación se implementa el patrón de búsqueda en espacio de estados en Haskell, usando su posibilidad de programar en orden superior para abstraer los argumentos del problema.

Finalmente, se aplica el patrón para implementar las soluciones de los problemas de las N reinas y del cambio de monedas.

Las transparencias usadas en la clase son las páginas 11-28 del tema 23:

El código del patrón de búsqueda en espacio de estados es
Read More “I1M2015: El patrón de búsqueda en espacios de estados en Haskell”