I1M2019

En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos estudiado el tipo abstracto de datos de los montículos en Haskell.

En primer lugar, se han introduccido los montículos usando el artículo Functional heap – Leftist tree.

En segundo lugar, se ha seguido el mismo patrón que en los anteriores tipos de datos para estudiar el TAD de los montículos:

• elección de las operaciones básicas,
• especificación de sus propiedades,
• implementación en Haskel,
• análisis de la complejidad de las definiciones de las operaciones básicas y
• verificación con QuickCheck de sus propiedades características.

En tercer lugar, se ha usado los montículos para implementar el TAD de las colas de prioridad.

Finalmente, se ha comentado las librerías de Haskell para montículos: Data.Heap.Leftist y Data.Heap. La primera se corresponde totalmente con la implementación presentada en clase y la segunda es una generalización ampliada.

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

En la primera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos estudiado el tipo abstracto de datos de los árboles binarios de búsqueda.

Un árbol binario de búsqueda (ABB) (binary search tree) en inglés) es un árbol binario tal que el valor de cada nodo es mayor que los valores de su subárbol izquierdo y es menor que los valores de su subárbol derecho y, además, ambos subárboles son árboles binarios de búsqueda. Por ejemplo, al almacenar los valores de [2,3,4,5,6,8,9] en un ABB se puede obtener los siguientes ABB:

El objetivo principal de los ABB es reducir el tiempo de acceso a los valores.

El contenido de la clase ha sido el siguiente:

• la signatura del TAD de los árboles binarios de búsqueda;
• las propiedades del TAD de los árboles binarios de búsqueda;
• la implementación, en Haskell, de los árboles binarios de búsqueda mediante tipos de datos algebraicos y
• la comprobación con QuickCheck de sus propiedades.

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

En la clase de hoy de Informática de 1º del Grado en Matemáticas se han estudiado las librerías de diccionarios y de conjuntos en Haskell.

Como primera aproximación se ha explicado, siguiendo los apuntes del tema 29, las funciones básicas y las más frecuentes. En segundo lugar se ha comentado las funciones con las librerías con sus ejemplos:

• Manual de la librería de conjuntos Data.Set.
• Manual de la librería de diccionarios Data.Map.

Finalmente, para comentar las complejidades de las funciones, se ha visto la documentación de las librerías Data.Set y Data.Map.

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

Como tarea se han propuesto los ejercicios de la relación 28 y de la relación 29.

En la primera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos estudiado el tipo abstracto de datos de los conjuntos y tres de sus implementaciones en Haskell.

Se ha seguido el mismo patrón que en los anteriores tipos de datos:

• elección de las operaciones básicas,
• especificación de sus propiedades,
• implementación en Haskell mediante no ordenadas con duplicados,
• implementación en Haskell mediante listas no ordenadas sin duplicados,
• implementación en Haskell mediante listas ordenadas sin duplicados,
• análisis de la complejidad de las definiciones de las operaciones básicas en las tres implementaciones y
• verificación con QuickCheck de sus propiedades características.

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

Como tarea se han propuesto los ejercicios de la relación 29.

En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones de los ejercicios de la relación 24 sobre algoritmos de ordenación en Haskell y sus complejidades.

Los ejercicios y su solución se muestran a continuación
Read More “I1M2019: Algoritmos de ordenación en Haskell”