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

Escribe tu solución