Menu Close

Categoría: I1M2017

I1M2017: Programación dinámica: Caminos en una retícula

En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas se han explicado las soluciones de los ejercicios de la relación 29, en el que se comparan distintas soluciones del problema de calcular los caminos en una retícula. Se ha mostrado como transformar las definiciones recursivas en definiciones con programación dinámica. Además, se han comparado experimentalmente la eficiencia de las distintas definiciones.

Los ejercicios, y sus soluciones, se muestran a continuación.

I1M2017: 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.

Los apuntes correspondientes a la clase son los del tema 16

I1M2017: 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 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

I1M2017: 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.

Los apuntes correspondientes a la clase son los del tema 14

I1M2017: Programación dinámica en Haskell

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

I1M2017: Ejercicios de programación de cálculo numérico en Maxima

En la tercera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas se han comentado las soluciones de los ejercicios de la relación 28, en la que se definen en Maxima funciones para resolver los siguientes problemas de cálculo numérico:

  • diferenciación numérica,
  • cálculo de la raíz cuadrada mediante el método de Herón,
  • cálculo de los ceros de una función por el método de Newton y
  • cálculo de funciones inversas.

Estas funciones se han definido en Haskell en la relación 26

Los ejercicios, y sus soluciones, se muestran a continuación.

I1M2017: Cálculo numérico en Haskell (2º parte)

En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas se han explicado las soluciones de los ejercicios de la relación 27, en la que se definen funciones para resolver los siguientes problemas de cálculo numérico:

  • Cálculo de límites.
  • Cálculo de los ceros de una función por el método de la bisección.
  • Cálculo de raíces enteras.
  • Cálculo de integrales por el método de los rectángulos.
  • Algoritmo de bajada para resolver un sistema triangular inferior.

Los ejercicios, y sus soluciones, se muestran a continuación.

I1M2017: Análisis de la complejidad de los algoritmos

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

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

Los apuntes correspondientes a la clase son

I1M2017: De la matemática a la máquina

En la segunda parte de la clase de hoy del curso de Informática de 1º del Grado en Matemáticas se ha comentado cómo los se pueden representar los conceptos matemáticos en los ordenadores.

Para ello se ha visto cómo la definición de factorial se puede definir en distintos paradigmas desde la matemática al código máquina. Las definiciones consideradas han sido

  • En matemáticas
  • En programación funcional (Haskell).
  • En programación imperativa (C).
  • En ensamblador.
  • En código máquina.

La exposición se ha basado en el artículo From math to machine: translating a function to machine code de Brian Steffens.