Menu Close

Categoría: I1M2019

I1M2019: El TAD de los montículos en Haskell

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

I1M2019: El TAD de los árboles binarios de búsqueda en Haskell

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:

    5                     5
  /   \                 /   \
 2     6               3     8
  \     \             / \   / \
   4     8           2   4 6   9
  /       \
 3         9

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

I1M2019: Las librerías de conjuntos y de diccionarios en Haskell

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:

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.

I1M2019: El TAD de los conjuntos en Haskell

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.

I1M2019: El tipo abstracto de datos de las colas de prioridad en Haskell

En la primera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas se ha estudiado el tipo abstracto de las colas de prioridad.

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 listas,
  • análisis de la complejidad de las definiciones de las operaciones básicas 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 los del tema 16

Una versión interactiva de los apuntes en IHaskell se encuentra aquí.

I1M2019: El tipo abstracto de datos de las colas en Haskell

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

La clase se ha dado mediante videoconferencia y el correspondiente vídeo es

Los apuntes correspondientes a la clase son los del tema 15

I1M2019: El tipo abstracto de datos de las pilas en Haskell

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.

La clase se ha dado mediante videoconferencia y el correspondiente vídeo es

Los apuntes correspondientes a la clase son los del tema 14

I1M2019: Análisis de la complejidad de los algoritmos

En 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

| Ejemplo     | Ecuaciones         | Orden      |
|-------------|--------------------|------------|
| suma        | T(1)   = k         | O(n)       |
|             | T(n+1) = T(n)+k'   |            |
|-------------|--------------------|------------|
| suma2       | T(1) = k           | O(1)       |
|-------------|--------------------|------------|
| sumaDeSumas | T(1)   = k         | O(n²)      |
|             | T(n+1) = T(n)+n    |            |
|-------------|--------------------|------------|
| potencia    | T(1)   = k         | O(log(n))  |
|             | T(n)   = T(n/2)+k' |            |
|-------------|--------------------|------------|
| raiz        | T(0)   = k         | O(2ⁿ)      |
|             | T(n+1) = 2T(n)+k'  |            |
|-------------|--------------------|------------|
| ordenación  | T(1)   = k         | O(nlog(n)) |
| por mezcla  | T(n)   = 2T(n/2)+n |            |

La clase se ha dado mediante videoconferencia y el correspondiente vídeo es

Los apuntes correspondientes a la clase son