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 41 sobre la solución del problema del triominó mediante divide y vencerás.
Los ejercicios y su solución se muestran a continuación
Read More “I1M2018: El rompecabeza del triominó mediante divide y vencerás”
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 divide y vencerás.
La clase comenzó analizando los árboles de ordenación de una lista de números mediante la ordenación por mezcla y la ordenación rápida.
De este análisis se extrae el patrón de resolución de problemas mediante divide y vencerás (DyV) y sus argumentos:
A continuación se implementa el patrón DyV en Haskell, usando su posibilidad de programar en orden superior para abstraer los argumentos del problema.
Finalmente, se aplica el patrón DyV para implementar los algoritmos de ordenación por mezcla y ordenación rápida.
Las transparencias usadas en la clase son las páginas 1-10 del tema 23:
El código del patrón divide y vencerás es
Read More “I1M2018: El patrón de divide y vencerás en Haskell”
En la segunda parte de la clase de hoy del curso de Lógica matemática y fundamentos se ha estudiado cómo definir en Isabelle/HOL conjuntos y relaciones inductivas y cómo demostrar sus propiedades.
La clase se ha basado en la siguiente teoría Isabelle
Read More “LMF2018: Definiciones inductivas en Isabelle/HOL”
En la primera parte de la clase de hoy del curso de Lógica matemática y fundamentos se ha estudiado cómo definir y razonar en Isabelle/HOL tipos de datos recursivos como árboles binarios, árboles generales y bosques. En su definición se usa recursión cruzada y en la demostración de sus propiedades se usa inducción doble.
La teoría utilizada es la siguiente
Read More “LMF2018: Razonamiento sobre árboles y bosques en Isabelle/HOL”
En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos estudiado la implementación en Haskell de algunos algoritmos sobre grafos usando el TAD de los grafos.
Concretamente los algoritmos que se han estudiado son los del recorrido del grafo (en profundidad o en anchura y los algoritmos de Kruskal y de Prim para calcular el árbol de expansión minimal.
Las transparencias usadas en la clase son las secciones 2 y 3 del tema 22