Menu Close

Categoría: I1M2018

I1M2018: Razonamiento sobre programas

En la clase de hoy de Informática de 1º del Grado en Matemáticas se ha estudiado cómo demostrar propiedades de programas Haskell.

Los tipos de razonamiento estudiado son

  • Razonamiento ecuacional sin variables.
  • Razonamiento ecuacional con variables.
  • Razonamiento ecuacional con análisis de casos
  • Razonamiento por inducción sobre los naturales
  • Razonamiento por inducción sobre listas.

En las demostraciones por inducción se ha destacado la elección de variables, las demostraciones anidadas y la generalización de propiedades para su prueba por inducción.

Los apuntes correspondientes a la clase son los del tema 8

Además, se ha mostrado cómo automatizar las demostraciones usando Isabelle/HOL.

I1M2018: Programación dinámica: Apilamiento de barriles

En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas se han resuelto ejercicios de la relación 46, en el que se comparan distintas soluciones del problema del apilamiento de barriles. 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.

I1M2018: El problema de las fichas mediante búsqueda en espacio de estado

En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticasse han resuelto ejercicios de la relación 44 en el que se aplican los patrones de busqueda en profundidad, en anchura, primero el mejor y en escalada para resolver el provlema de las fichas y comparar las soluciones obtenidas.

Los ejercicios y su solución se muestran a continuación

I1M2018: Búsquedas heurísticas en Haskell

En la la primera 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 con heurísticas.

En primer lugar se estudió la búsqueda por primero el mejor, se implementó el patrón de búsqueda por primero el mejor y se aplicó el patrón para resolver el problema del 8 puzzle.

En segundó lugar se estudió la búsqueda en escalada, se implementó el patrón de búsqueda en escalada y se aplicó el patrón para resolver el el problema del cambio de monedas por escalada.

Finalmente, se estudió el algoritmo de Prim del árbol de expansión mínimo como un caso particular de búsqueda en escalada.

Los apuntes correspondientes a la clase son las secciones 3 y 4 del tema 23

I1M2018: El patrón de búsqueda en espacios de estados en Haskell

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.

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

Los apuntes correspondientes a la clase es la 2ª sección del tema 23

I1M2018: Resolución de problemas mediante búsqueda en espacio de estados

En la primera parte de la clase de hoy del curso de 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.

En primer lugar se ha visto cómo se describen los problemas mediante el estado inicial, los sucesores de los estados y los estados finales. Aplicándola a los problemas del 8-puzzle, del granjero, de las jarras y del viaje.

A continuación se han explicado los procedimientos básicos de búsquedas: en anchrura, en profundidad, en profundidad acotada y en profundidad iterativa.

Los apuntes correspondientes son las 53 primeras transparencias del tema 23a.