TAD de los grafos: Grafos completos

El grafo completo de orden n, K(n), es un grafo no dirigido cuyos conjunto de vértices es {1,..n} y tiene una arista entre cada par de vértices distintos.

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que completo n es el grafo completo de orden n. Por ejemplo,

Soluciones

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


Soluciones en Haskell


Soluciones en Python

El tipo abstracto de datos de los grafos

1. El tipo abstracto de datos de los grafos

Un grafo es una estructura que consta de un conjunto de vértices y un conjunto de aristas que conectan los vértices entre sí. Cada vértice representa una entidad o un elemento, y cada arista representa una relación o conexión entre dos vértices.

Por ejemplo,

representa un grafo no dirigido, lo que significa que las aristas tienen una dirección específica. Cada arista tiene un peso asociado, que puede representar una medida o una valoración de la relación entre los vértices que conecta.

El grafo consta de cinco vértices numerados del 1 al 5. Las aristas especificadas en la lista indican las conexiones entre los vértices y sus respectivos pesos. Por ejemplo, la arista (1,2,12) indica que existe una conexión entre el vértice 1 y el vértice 2 con un peso de 12.

En el grafo representado, se pueden observar las conexiones entre los vértices de la siguiente manera:

  • El vértice 1 está conectado con el vértice 2 (peso 12), el vértice 3 (peso 34) y el vértice 5 (peso 78).
  • El vértice 2 está conectado con el vértice 4 (peso 55) y el vértice 5 (peso 32).
  • El vértice 3 está conectado con el vértice 4 (peso 61) y el vértice 5 (peso 44).
  • El vértice 4 está conectado con el vértice 5 (peso 93).

Las operaciones del tipo abstracto de datos (TAD) de los grafos son

tales que
+ creaGrafo o cs as es un grafo (dirigido o no, según el de o), con el par de cotas cs y listas de aristas as (cada arista es un trío formado por los dos vértices y su peso).
+ creaGrafo' es la versión de creaGrafo para los grafos sin pesos.
+ dirigido g se verifica si g es dirigido.
+ nodos g es la lista de todos los nodos del grafo g.
+ aristas g es la lista de las aristas del grafo g.
+ adyacentes g v es la lista de los vértices adyacentes al nodo v en el grafo g.
+ aristaEn g a se verifica si a es una arista del grafo g.
+ peso v1 v2 g es el peso de la arista que une los vértices v1 y v2 en el grafo g.

Usando el TAD de los grafos, el grafo anterior se puede definir por

con los siguientes argumentos:

  • ND: Es un parámetro de tipo Orientacion que indica si el es dirigido o no. En este caso, se utiliza ND, lo que significa «no dirigido». Por lo tanto, el grafo creado será no dirigido, lo que implica que las aristas no tienen una dirección específica.
  • (1,5): Es el par de cotas que define los vértices del grafo. En este caso, el grafo tiene vértices numerados desde 1 hasta 5.
  • [(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61),(3,5,44),(4,5,93)]: Es una lista de aristas, donde cada arista está representada por un trío de valores. Cada trío contiene los dos vértices que están conectados por la arista y el peso de dicha arista.

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes:
+ mediante lista de adyacencia,
+ mediante vector de adyacencia y
+ mediante matriz de adyacencia.

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

2. Los grafos en Haskell

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

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

2.2. Implementación de los grafos mediante listas de adyacencia

La implementación se encuentra en el módulo GrafoConListaDeAdyacencia cuyo contenido es el siguiente:

2.3. Implementación de los grafos mediante vectores de adyacencia

La implementación se encuentra en el módulo GrafoConVectorDeAdyacencia cuyo contenido es el siguiente:

2.3. Implementación de los grafos mediante vectores de adyacencia

La implementación se encuentra en el módulo GrafoConMatrizDeAdyacencia cuyo contenido es el siguiente:

3. Los grafos en Python

3.1. El tipo abstracto de los grafos en Python

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

3.2. Implementación de los grafos mediante listas

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

  • dirigido() se verifica si el grafo es dirigido.
  • nodos() es la lista de todos los nodos del grafo.
  • aristas() es la lista de las aristas del grafo.
  • adyacentes(v) es la lista de los vértices adyacentes al vértice v en el grafo.
  • aristaEn(a) se verifica si a es una arista del grafo.
  • peso(v1, v2) es el peso de la arista que une los vértices v1 y v2 en el grafo.

Por ejemplo,

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

La implementación se encuentra en el módulo GrafoConListaDeAdyacencia cuyo contenido es el siguiente:

TAD de los polinomios: Factorización de un polinomio

Usando el tipo abstracto de los polinomios, definir la función

tal que factorizacion p es la lista de la descomposición del polinomio p en factores obtenida mediante el regla de Ruffini. 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 polinomios: Raíces enteras de un polinomio

Usando el tipo abstracto de los polinomios, definir la función

tal que raicesRuffini p es la lista de las raices enteras de p, calculadas usando el regla de Ruffini. 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 polinomios: Reconocimiento de raíces por la regla de Ruffini

Usando el tipo abstracto de los polinomios, definir la función

tal que esRaizRuffini r p se verifica si r es una raiz de p, usando para ello el regla de Ruffini. 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 polinomios: Regla de Ruffini

Usando el tipo abstracto de los polinomios, definir las funciones

tales que

  • cocienteRuffini r p es el cociente de dividir el polinomio p por el polinomio x-r. Por ejemplo:

  • restoRuffini r p es el resto de dividir el polinomio p por el polinomio x-r. Por ejemplo,

Comprobar con QuickCheck que, dado un polinomio p y un número entero r, las funciones anteriores verifican la propiedad de la división euclídea.

Soluciones

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


Soluciones en Haskell


Soluciones en Python

TAD de los polinomios: Regla de Ruffini con representación densa

Usando el tipo abstracto de los polinomios definir la función

tal que ruffiniDensa r cs es la lista de los coeficientes del cociente junto con el rsto que resulta de aplicar la regla de Ruffini para dividir el polinomio cuya representación densa es cs entre x-r. Por ejemplo,

ya que

Soluciones

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


Soluciones en Haskell


Soluciones en Python

TAD de los polinomios: Término independiente de un polinomio

Usando el tipo abstracto de datos de los polinomios definir la función

tal que terminoIndep p es el término independiente del polinomio 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 polinomios: Método de Horner del valor de un polinomio

El método de Horner para calcular el valor de un polinomio se basa en representarlo de una forma forma alernativa. Por ejemplo, para calcular el valor de

se representa como

y se evalúa de dentro hacia afuera; es decir,

Usando el tipo abstracto de los polinomios, definir la función

tal que horner p x es el valor del polinomio p al sustituir su variable por el número 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 polinomios: Divisibilidad de polinomios

Usando el tipo abstracto de los polinomios, definir la función

tal que divisiblePol p q se verifica si el polinomio p es divisible por el polinomio q. 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 polinomios: División de polinomios

Usando el tipo abstracto de los polinomios, definir las funciones

tales que

  • cociente p q es el cociente de la división de p entre q. Por ejemplo,

  • resto p q es el resto de la división de p entre q. 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 polinomios: Multiplicación de un polinomio por un número

Usando el tipo abstracto de los polinomios, definir la función

tal que multEscalar c p es el polinomio obtenido multiplicando el número c por el polinomio 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 polinomios: Integral definida de un polinomio

Usando el tipo abstracto de datos de los polinomios definir la función

tal que integralDef p a b es la integral definida del polinomio p entre a y b. 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 polinomios: Integral de un polinomio

Usando el tipo abstracto de los polinomios, definir la función

tal que integral p es la integral del polinomio p cuyos coefientes son números racionales. 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 polinomios: Potencia de un polinomio

Usando el tipo abstracto de los polinomios, definir la función

tal que potencia p n es la potencia n-ésima del polinomio 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 polinomios: Resta de polinomios

Usando el tipo abstracto de los polinomios, definir la función

tal que restaPol p q es el polinomio obtenido restándole a p el q. 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 polinomios: Derivada de un polinomio

Usando el tipo abstracto de los polinomios, definir la función

tal que derivada p es la derivada del polinomio 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 polinomios: Comprobación de raíces de polinomios

Usando el tipo abstracto de los polinomios,
definir la función

tal que esRaiz c p se verifica si c es una raiz del polinomio 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 polinomios: Valor de un polinomio en un punto

Usando el tipo abstracto de los polinomios, definir la función

tal que valor p c es el valor del polinomio p al sustituir su variable por c. 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 polinomios: Producto de polinomios

Usando el tipo abstracto de los polinomios, definir la función

tal que multPol p q es el producto de los polinomios p y q. Por ejemplo,

Comprobar con QuickCheck las siguientes propiedades

  • El producto de polinomios es conmutativo.
  • El producto es distributivo respecto de la suma.

Soluciones

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


Soluciones en Haskell


Soluciones en Python

TAD de los polinomios: Suma de polinomios

Usando el tipo abstracto de los polinomios, definir la función

tal que (sumaPol p q) es la suma de los polinomios p y q. Por ejemplo,

Comprobar con QuickCheck las siguientes propiedades:

  • polCero es el elemento neutro de la suma.
  • la suma es conmutativa.

Soluciones

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


Soluciones en Haskell


Soluciones en Python

TAD de los polinomios: Término líder de un polinomio

Usando el tipo abstracto de los polinomios, definir la función

tal que termLider p es el término líder del polinomio 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 polinomios: Construcción de términos

Usando el tipo abstracto de los polinomios, definir la función

tal que (creaTermino n a) es el término a*x^n. 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 polinomios: Transformaciones entre polinomios y listas densas

Utilizando el tipo abstracto de datos de los polinomios definir las funciones

tales que

  • densaApolinomio xs es el polinomio cuya representación densa es xs. Por ejemplo,

  • polinomioAdensa p es la representación densa del polinomio p. Por ejemplo,

Comprobar con QuickCheck que ambas funciones son inversas.

Soluciones

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


Soluciones en Haskell


Soluciones en Python

TAD de los polinomios: Coeficiente del término de grado k

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

tal que coeficiente k p es el coeficiente del término de grado k del polinomio 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 polinomios: Transformaciones entre polinomios y listas dispersas

Utilizando el tipo abstracto de datos de los polinomios definir las funciones

tales que

  • dispersaApolinomio ps es el polinomiocuya representación dispersa es ps. Por ejemplo,

  • polinomioAdispersa p es la representación dispersa del polinomio p. Por ejemplo,

Comprobar con QuickCheck que ambas funciones son inversas.

Soluciones

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


Soluciones en Haskell


Soluciones en Python

TAD de los polinomios: Transformaciones entre las representaciones dispersa y densa

Definir las funciones

tales que

  • densaAdispersa xs es la representación dispersa del polinomio cuya representación densa es xs. Por ejemplo,

  • dispersaAdensa ps es la representación densa del polinomio cuya representación dispersa es ps. Por ejemplo,

Comprobar con QuickCheck que las funciones densaAdispersa y dispersaAdensa son inversas.

Soluciones

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


Soluciones en Haskell


Soluciones en Python

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