I1M2010

En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos estudiado el tipo abstracto de los polinomios y su implementación en Haskell.

Comenzamos la clase analizando las posibles representaciones de los polinomios y, como consecuencia, establecer la signatura y las propiedades del TAD de los polinomios.

A continuación, estudiamos tres implementaciones del TAD de los polinomios: mediante tipos algebraicas, mediantes listas dispersas y mediante listas densas.

Finalmente, mediante QuickCheck, se comprobó que las distintas implementaciones verifican las propiedades del TAD.

Las transparencias usadas en la clase son las páginas 1-42 del tema 21.

El código se encuentra en

• PolRepTDA: Implementación de los polinomios mediante tipos de datos algebraicos.
• PolRepDispersa: Implementación de los polinomios mediante listas dispersas.
• PolRepDensa: Implementación de los polinomios mediante listas densas.
• PolPropiedades: Propiedades del TAD de los polinomios.

En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones a los ejercicios sobre la numeración de los números racionales en Haskell de la 31ª relación.

Los ejercicios y su solución se muestran a continuación
Read More “I1M2010: Ejercicios sobre la numeración de los racionales en Haskell”

En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos estudiado el patrón de programación dinámica en Haskell.

Comenzamos la clase analizando los inconvenientes de la técnica del divide y vencerás en el cálculo de la sucesión de Fibonacci y cómo la corregirlos mediante programación dinámica.

A continuación, se vió la implementación del patrón de programación dinámica en Haskell y se aplicó el patrón a la sucesión de Fibonacci lo que permitió comprobar experimentalmente la ganancia en eficiencia respecto de la solución mediante divide y vencerás.

Finalmente, se aplicó el patrón de programación dinámica a la resolución del problema del producto de cadenas de matrices (en inglés, “matrix chain multiplication”) que consiste en dada una sucesión de matrices encontrar la manera de multiplicarlas usando el menor número de productos de elementos.

Las transparencias usadas en la clase son las páginas 1-39 del tema 24:
Read More “I1M2010: Programación dinámica en Haskell y el problema del producto de cadenas de matrices”

En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos continuado el estudio de la resolución de problemas mediante búsqueda en espacios de estados, introduciendo el patrón de búsqueda en escalada y resolviendo con dicho patrón el problema del cambio de monedas y el algoritmo de Prim del árbol de expansión mínimo.

Las transparencias usadas en la clase son las páginas 44-55 del tema 23:
Read More “I1M2010: Búsqueda en escalada en Haskell”

En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos continuado el estudio de la resolución de problemas mediante búsqueda en espacios de estados.

La clase comenzó representando el problema del 8 puzzle en Haskell de acuerdo con el patrón de búsqueda en espacios de estados.

A continuación se comprobó la imposibilidad de resolver algunas instancias del problema con dicho patrón y cómo a partir de dicho patrón se puede obtener el de búsqueda por primero el mejor

Finalmente, se resolvió el problema del 8 puzzle mediante búsqueda por primero el mejor.

Las transparencias usadas en la clase son las páginas 38-43 del tema 23:
Read More “I1M2010: Búsqueda por primero el mejor en Haskell”