El tipo abstracto de datos de los polinomios

1. El tipo abstracto de datos de los polinomios

Un polinomio es una expresión matemática compuesta por una suma de términos, donde cada término es el producto de un coeficiente y una variable elevada a una potencia. Por ejemplo, el polinomio 3x^2+2x-1 tiene un término de segundo grado (3x^2), un término de primer grado (2x) y un término constante (-1).

Las operaciones que definen al tipo abstracto de datos (TAD) de los polinomios (cuyos coeficientes son del tipo a) son las siguientes:

tales que

  • polCero es el polinomio cero.
  • (esPolCero p) se verifica si p es el polinomio cero.
  • (consPol n b p) es el polinomio bx^n+p
  • (grado p) es el grado del polinomio p.
  • (coefLider p) es el coeficiente líder del polinomio p.
  • (restoPol p) es el resto del polinomio p.

Por ejemplo, el polinomio

se representa por

Las operaciones tienen que verificar las siguientes propiedades:

  • esPolCero polCero
  • n > grado p && b /= 0 ==> not (esPolCero (consPol n b p))
  • consPol (grado p) (coefLider p) (restoPol p) == p
  • n > grado p && b /= 0 ==> grado (consPol n b p) == n
  • n > grado p && b /= 0 ==> coefLider (consPol n b p) == b
  • n > grado p && b /= 0 ==> restoPol (consPol n b p) == p

2. Los polinomios en Haskell

2.1. El tipo abstracto de datos de los polinomios en Haskell

El TAD de los polinomios se encuentra en el módulo Polinomio.hs cuyo contenido es el siguiente:

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes:

  • mediante tipo de dato algebraico,
  • mediante listas densas y
  • mediante listas dispersas.

Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

2.2. Implementación de los polinomios mediante tipos de datos algebraicos

Representamos un polinomio mediante los constructores ConsPol y
PolCero. Por ejemplo, el polinomio

se representa por

La implementación se encuentra en el módulo PolRepTDA.hs cuyo contenido es el siguiente:

2.3. Implementación de polinomios mediante listas densas

Representaremos un polinomio por la lista de sus coeficientes ordenados en orden decreciente según el grado. Por ejemplo, el polinomio

se representa por

En la representación se supone que, si la lista no es vacía, su primer elemento es distinto de cero.

La implementación se encuentra en el módulo PolRepDensa.hs cuyo contenido es el siguiente:

2.4. Implementación de polinomios mediante listas dispersas

Representaremos un polinomio mediante una lista de pares (grado,coef),
ordenados en orden decreciente según el grado. Por ejemplo, el polinomio

se representa por

En la representación se supone que los primeros elementos de los pares forman una sucesión estrictamente decreciente y que los segundos elementos son distintos de cero.

La implementación se encuentra en el módulo PolRepDispersa.hs cuyo contenido es el siguiente:

3. Los polinomios en Python

3.1. El tipo abstracto de los polinomios en Python

La implementación se encuentra en el módulo Polinomio.py cuyo contenido es el siguiente:

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes:

  • mediante listas densas y
  • mediante listas dispersas.

3.2. Implementación de los polinomios mediante listas densas

Representaremos un polinomio por la lista de sus coeficientes ordenados en orden decreciente según el grado. Por ejemplo, el polinomio

se representa por

En la representación se supone que, si la lista no es vacía, su primer elemento es distinto de cero.

Se define la clase Polinomio con los siguientes métodos:

  • esPolCero() se verifica si es el polinomio cero.
  • consPol(n, b) es el polinomio obtenido añadiendo el térmiono bx^n
  • grado() es el grado del polinomio.
  • coefLider() es el coeficiente líder del polinomio.
  • restoPol() es el resto del polinomio.

Por ejemplo,

Además se definen las correspondientes funciones. Por ejemplo,

Finalmente, se define un generador aleatorio de polinomios y se comprueba que los polinomios cumplen las propiedades de su especificación.

La implementación se encuentra en el módulo PolRepDensa.py en el que se define la clase Conj con los siguientes métodos:

3.3. Implementación de los polinomios mediante listas dispersas

Representaremos un polinomio mediante una lista de pares (grado,coef), ordenados en orden decreciente según el grado. Por ejemplo, el polinomio

se representa por

En la representación se supone que los primeros elementos de los pares forman una sucesión estrictamente decreciente y que los segundos elementos son distintos de cero.

La implementación se encuentra en el módulo PolRepDispersa.py cuyo contenido es

Clausura transitiva

Usando el tipo de las relaciones binarias, definir la función

tal que clausuraTransitiva r es la clausura transitiva de r; es decir, la menor relación transitiva que contiene a r. Por ejemplo,

Comprobar con QuickCheck que clausuraTransitiva es transitiva.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Clausura simétrica

Usando el tipo de las relaciones binarias, definir la función

tal que clausuraSimetrica r es la clausura simétrica de r; es decir, la menor relación simétrica que contiene a r. Por ejemplo,

Comprobar con QuickCheck que clausuraSimetrica es simétrica.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Clausura reflexiva

Usando el tipo de las relaciones binarias, definir la función

tal que clausuraReflexiva r es la clausura reflexiva de r; es decir, la menor relación reflexiva que contiene a r. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Relaciones totales

Usando el tipo de las relaciones binarias, definir la función

tal que total r se verifica si la relación r es total; es decir, si para cualquier par x, y de elementos del universo de r, se tiene que x está relacionado con y o y está relacionado con x. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Relaciones antisimétricas

Usando el tipo de las relaciones binarias, definir la función

tal que antisimetrica r se verifica si la relación r es antisimétrica; es decir, si (x,y) e (y,x) están relacionado, entonces x=y. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Relaciones irreflexivas

Usando el tipo de las relaciones binarias, definir la función

tal que irreflexiva r se verifica si la relación r es irreflexiva; es decir, si ningún elemento de su universo está relacionado con él mismo. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Relaciones de equivalencia

Usando el tipo de las relaciones binarias, definir la función

tal que esEquivalencia r se verifica si la relación r es de equivalencia. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Relaciones transitivas

Usando el tipo de las relaciones binarias, definir la función

tal que transitiva r se verifica si la relación r es transitiva. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Reconocimiento de subconjunto

Definir la función

tal que subconjunto xs ys se verifica si xs es un subconjunto de ys. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Composición de relaciones binarias

Usando el tipo de las relaciones binarias, definir la función

tal que composicion r s es la composición de las relaciones r y s. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Relaciones simétricas

Usando el tipo de las relaciones binarias, definir la función

tal que simetrica r se verifica si la relación r es simétrica. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Relaciones reflexivas

Usando el tipo de las relaciones binarias, definir la función

tal que reflexiva r se verifica si la relación r es reflexiva. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Universo y grafo de una relación binaria

Usando el tipo de las relaciones binarias, definir las funciones

tales que

  • universo r es el universo de la relación r. Por ejemplo,

  • grafo r es el grafo de la relación r. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Relaciones binarias

Una relación binaria R sobre un conjunto A se puede mediante un par (u,g) donde u es la lista de los elementos de tipo A (el universo de R) y g es la lista de pares de elementos de u (el grafo de R).

Definir el tipo de dato (Rel a), para representar las relaciones binarias sobre a, y la función

tal que esRelacionBinaria r se verifica si r es una relación binaria. Por ejemplo,

Además, definir un generador de relaciones binarias y comprobar que las relaciones que genera son relaciones binarias.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Producto cartesiano de dos conjuntos

Utilizando el tipo abstracto de datos de los conjuntos (https://bit.ly/3HbB7fo) definir la función

tal que productoC c1 c2 es el producto cartesiano de los conjuntos c1 y c2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Algunos elementos verifican una propiedad

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que algunos p c se verifica si algún elemento de c verifica el predicado p. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Todos los elementos verifican una propiedad

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que todos p c se verifica si todos los elemsntos de c verifican el predicado p. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Aplicación de una función a los elementos de un conjunto

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que map f c es el conjunto formado por las imágenes de los elementos del conjunto c, mediante la aplicación f. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Partición según un número

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que divide x c es el par formado por dos subconjuntos de c: el de los elementos menores o iguales que x y el de los mayores que x. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Partición de un conjunto según una propiedad

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que particion c es el par formado por dos conjuntos: el de los elementos de c que verifican p y el de los elementos que no lo verifican. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Subconjunto determinado por una propiedad

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal filtra p c es el conjunto de elementos de c que verifican el predicado p. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Diferencia simétrica

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que diferenciaSimetrica c1 c2 es la diferencia simétrica de los conjuntos c1 y c2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Diferencia de conjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que diferencia c1 c2 es el conjunto de los elementos de c1 que no son elementos de c2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Conjuntos disjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que disjuntos c1 c2 se verifica si los conjuntos c1 y c2 son disjuntos. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Intersección de varios conjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que interseccionG cs es la intersección de la lista de conjuntos cs. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Intersección de dos conjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que interseccion c1 c2 es la intersección de los conjuntos c1 y c2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Unión de varios conjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal unionG cs calcule la unión de la lista de conjuntos cs. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Unión de dos conjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal union c1 c2 es la unión de ambos conjuntos. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los conjuntos: Número de elementos de un conjunto

Utilizando el tipo abstracto de datos de los conjuntos definir la función

tal que cardinal c es el número de elementos del conjunto c. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python