Codificación de Huffman en Haskell
En esta relación de ejercicios, para la asignatura de Programación declarativa, se estudia la codificación de Huffman. El contenido de la relación es el siguiente:
Read More “Codificación de Huffman en Haskell”
Para contestar rapidito y casi sin pensar
El enunciado del problema de hoy de Números y algo más …, titulado Para contestar rapidito y casi sin pensar, es el siguiente
¿Cuál es último dígito de la suma de las cuartas potencias de los primeros 100 números enteros positivos?
A partir del problema he escrito la siguiente relación de ejercicios para la asignatura de Informática de 1º del Grado en Matemáticas.
Read More “Para contestar rapidito y casi sin pensar”
Enumeraciones de los números racionales en Haskell
He publicado en LógicaMente una relación de ejercicios en Haskell sobre enumeraciones de los números racionales, cuyo contenido es el siguiente.
El objetivo de esta relación es construir dos enumeraciones de los números racionales. Concretamente,
- una enumeración basada en las representaciones hiperbinarias y
- una enumeración basada en los los árboles de Calkin-Wilf.
También se incluye la comprobación de la igualdad de las dos sucesiones y una forma alternativa de calcular el número de representaciones hiperbinarias mediante la función fucs.
Esta relación se basa en los siguientes artículos:
- Gaussianos Sorpresa sumando potencias de 2.
- N. Calkin y H.S. Wilf Recounting the rationals.
- Wikipedia Calkin-Wilf tree.
La relación de ejercicios es
Read More “Enumeraciones de los números racionales en Haskell”
Expresiones aritméticas mediante tipos abstracto de datos y polinomios en Haskell
El objetivo de esta relación de ejercicios es estudiar dos representaciones de las expresiones aritméticas construidas con una variable, los números enteros y las operaciones suma y producto.
Una representación es mediante tipo algebraico y la otra es mediante la lista de los coeficientes del polinomio correspondiente.
Se verá como puede transformarse una representación en la otra y se comprobará con QuickCheck la equivalencia de las representaciones.
La relación está basada en el ejercicio 3.3 (página 15) del artículo Interactive Proof Introduction to Isabelle/HOL de Tobias Nipkow.
El contenido de la relación de ejercicios se encuentra en LógicaMente y se muestra a continuación:
Read More “Expresiones aritméticas mediante tipos abstracto de datos y polinomios en Haskell”
El tipo abstracto de datos de las colas de prioridad en Haskell
En este artículo continúo la serie dedicada a los tipos de datos abstractos (TAD) en Haskell presentando el TAD de las colas de prioridad.
Una cola de prioridad (en inglés, priority queue) es una cola en la que cada elemento tiene asociada una prioridad y la operación de extracción siempre elige el elemento de menor prioridad. Un ejemplo de cola de prioridad es el formado por una lista de ciudades ordenadas por su distancia a un destino final.
El contenido del resto del artículo es el siguiente:
- la signatura del TAD de las colas de prioridad;
- las propiedades del TAD de las colas de prioridad;
- la implementación, en Haskell, de las colas de prioridad mediante listas y
- la comprobación con QuickCheck de sus propiedades.
Posteriormente, cuando se estudien los montículos, se presentará otra implementación de las colas de prioridad mediante montículos.
Read More “El tipo abstracto de datos de las colas de prioridad en Haskell”