En la clase de hoy del curso de Informática de 1º del Grado en Matemáticas hemos estudiado el tipo abstracto de datos de los grafos y dos de sus implementaciones en Haskell: mediante vectores y matrices de adyacencia.
La clase se ha dado mediante videoconferencia los correspondientes vídeos son
El TAD de grafos mediante vectores
El TAD de grafos mediante matricess
Los apuntes correspondientes a la clase es la sección 1 del tema 22
Una versión interactiva de los apuntes en IHaskell se encuentra aquí.
En 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 escalada en espacios de estados.
En primer lugar se explicó la idea de la búsqueda en escalada y cómo, usando dicha idea, se puede transformar el patrón de búsqueda por primero el mejor en el de búsqueda en escalada. Finalmente, se aplicó el patrón de búsqueda en escalada a la resolución del problema del cambio de monedas.
La clase se ha dado mediante videoconferencia y el correspondiente vídeo es
Los apuntes correspondientes a la clase es la sección 3 del tema 23
Una versión interactiva de los apuntes en IHaskell se encuentra aquí.
El código del problema del cambio de monedas usado en la clase es
En 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 informada en espacios de estados.
En primer lugar se estudiaron los algoritmos búsqueda con información (coste, heurística y A*). A continuación se estudió cómo adaptar el patrón de búsqueda ciega a búsqueda informada usando las colas de prioridad. Finalmente, se aplicó el patrón de búsqueda por primero el mejor a la resolución del problema del 8 puzzle.
La clase se ha dado mediante videoconferencia los correspondientes vídeos son
Algoritmos de búsqueda informada en espacios de estados
El patrón de búsqueda por primero el mejor en Haskell
Los apuntes correspondientes a la clase es la sección 3 del tema 23
Una versión interactiva de los apuntes en IHaskell se encuentra aquí.
El código de la primera solución del problema del 8 puzzle usado en la clase es
Con motivo de la pandemia hemos tenido que pasar la docencia al formato no presencial.
En la asignatura de Informática de 1º de Matemáticas el cambio ha tenido lugar al principio de la segunda parte del curso en el que aplica la programación funcional con Haskell, estudiada en la primera parte, a problemas de algorítmica.
Todas las clases no presenciales las he dado por videoconferencia y he subido sus vídeos a YouTube. En este momento hay 16 vídeos correspondientes a las 9 clases no presenciales impartidas:
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.
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í.
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 ejemplos 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.
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í.
Comenzamos la clase analizando las posibles representaciones de los polinomios y, como consecuencia, establecer la signatura y las propiedades del TAD de los polinomios.
A continuación, estudiamos tres posibles representaciones del TAD de los polinomios mediante tipos algebraicos, mediantes listas dispersas y mediante listas densas y sus implementaciones en Haskell
La clase se ha dado mediante videoconferencia y los correspondientes vídeos son
Los apuntes correspondientes a la clase son
Una versión interactiva de los apuntes en IHaskell se encuentra aquí.
