En la clase de hoy de del curso Informática de 1º del Grado en Matemáticas hemos estudiado cómo programar en Haskell los algoritmos de búsqueda en espacios de estados que vimos en la clase anterior y su aplicación al problema de las N reinas.

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

Los apuntes correspondientes a la clase son la segunda sección de

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

En 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 anchura, en profundidad, en profundidad acotada y en profundidad iterativa.

La clase se ha dado mediante videoconferencia y los correspondientes vídeos son

• Representación de problemas mediante espacios de estados:

• Algoritmos de búsqueda en espacios de estados:

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

En 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 divide y vencerás.

La resolución de problemas mediante la técnica de divide y vencerás la
hemos estado utilizando a lo largo del curso en distintos problemas como el de ordenar una lista mediante la ordenación por mezcla o la ordenación rápida.

Analizando estos casos, se extrae el patrón de resolución de problemas mediante divide y vencerás (DyV) que consta de los siguientes pasos:

• Dividir el problema en subproblemas menores.
• Resolver por separado cada uno de los subproblemas; si los subproblemas son complejos, usar la misma técnica recursivamente; si son simples, resolverlos directamente.
• Combinar todas las soluciones de los subproblemas en una solución simple.

Para implementarla, necesitamos funciones que determinen

• cómo reconocer si el problema es elemental,
• cómo se resuelven los problemas elementales,
• cómo se descompone un problema y
• cómo se combinan las soluciones de los subproblemas.

A continuación se implementa el patrón DyV en Haskell, usando su posibilidad de programar en orden superior para usar las anteriores funciones como argumento

Finalmente, se aplica el patrón DyV para implementar los algoritmos de ordenación por mezcla y ordenación rápida.

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

Los apuntes correspondientes a la clase son la primera sección de

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