Ir al contenido principal

Algoritmo divide y vencerás

Búsqueda en espacios de estados

La técnica divide y vencerás 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.

Definir la función

   divideVenceras :: (p -> Bool)
                  -> (p -> s)
                  -> (p -> [p])
                  -> (p -> [s] -> s)
                  -> p
                  -> s

tal que divideVenceras ind resuelve divide combina pbInicial resuelve el problema pbInicial mediante la técnica de divide y vencerás, donde

  • ind pb se verifica si el problema pb es indivisible
  • resuelve pb es la solución del problema indivisible pb
  • divide pb es la lista de subproblemas de pb
  • combina pb ss es la combinación de las soluciones ss de los subproblemas del problema pb.
  • pbInicial es el problema inicial

Usando la función DivideVenceras, definir las funciones

   ordenaPorMezcla :: Ord a => [a] -> [a]
   ordenaRapida    :: Ord a => [a] -> [a]

tales que

  • ordenaPorMezcla xs es la lista obtenida ordenando xs por el procedimiento de ordenación por mezcla. Por ejemplo,
     λ> ordenaPorMezcla [3,1,4,1,5,9,2,8]
     [1,1,2,3,4,5,8,9]
  • ordenaRapida xs es la lista obtenida ordenando xs por el procedimiento de ordenación rápida. Por ejemplo,
     λ> ordenaRapida [3,1,4,1,5,9,2,8]
     [1,1,2,3,4,5,8,9]

Leer más…

TAD de los grafos - Algoritmo de Prim

El tipo abstracto de datos de los grafos

El algoritmo de Prim calcula un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.

El algoritmo de Prim funciona de la siguiente manera:

  • Inicializar un árbol con un único vértice, elegido arbitrariamente, del grafo.
  • Aumentar el árbol por un lado. Llamamos lado a la unión entre dos vértices: de las posibles uniones que pueden conectar el árbol a los vértices que no están aún en el árbol, encontrar el lado de menor distancia y unirlo al árbol.
  • Repetir el paso 2 (hasta que todos los vértices pertenezcan al árbol)

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

   prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]

tal que prim g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Prim. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por

   g1, g2, g3, g4 :: Grafo Int Int
   g1 = creaGrafo ND (1,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)]
   g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),
                            (2,4,12),(2,5,32),
                            (3,4,14),(3,5,44),
                            (4,5,93)]
   g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                            (2,3,7),
                            (3,4,8),(3,5,7),
                            (4,5,5),
                            (5,6,3),(5,7,9),
                            (6,7,11)]
   g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                            (2,3,7),
                            (3,4,8),(3,5,1),
                            (4,5,5),
                            (5,6,3),(5,7,9),
                            (6,7,11)]

entonces

   prim g1  == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]
   prim g2  == [(32,2,5),(12,2,4),(13,1,2),(11,1,3)]
   prim g3  == [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)]

Leer más…

TAD de los grafos - Algoritmo de Kruskal

El tipo abstracto de datos de los grafos

El algoritmo de Kruskal calcula un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.

El algoritmo de Kruskal funciona de la siguiente manera:

  • se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado
  • se crea un conjunto C que contenga a todas las aristas del grafo
  • mientras C es no vacío,
  • eliminar una arista de peso mínimo de C
  • si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol
  • en caso contrario, se desecha la arista

Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo.

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

   kruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]

tal que kruskal g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Kruskal. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por

   g1, g2, g3, g4 :: Grafo Int Int
   g1 = creaGrafo ND (1,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)]
   g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),
                            (2,4,12),(2,5,32),
                            (3,4,14),(3,5,44),
                            (4,5,93)]
   g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                            (2,3,7),
                            (3,4,8),(3,5,7),
                            (4,5,5),
                            (5,6,3),(5,7,9),
                            (6,7,11)]
   g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                            (2,3,7),
                            (3,4,8),(3,5,1),
                            (4,5,5),
                            (5,6,3),(5,7,9),
                            (6,7,11)]

entonces

   kruskal g1  ==  [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]
   kruskal g2  ==  [(32,2,5),(13,1,2),(12,2,4),(11,1,3)]
   kruskal g3  ==  [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)]
   kruskal g4  ==  [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)]

Leer más…

TAD de los grafos - Nodos conectados en un grafo

El tipo abstracto de datos de los grafos

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

   conectados :: Grafo Int Int -> Int -> Int -> Bool

tal que conectados g v1 v2 se verifica si los vértices v1 y v2 están conectados en el grafo g. Por ejemplo, si grafo1 es el grafo definido por

   grafo1 :: Grafo Int Int
   grafo1 = creaGrafo' D (1,6) [(1,3),(1,5),(3,5),(5,1),(5,50),
                                (2,4),(2,6),(4,6),(4,4),(6,4)]

entonces,

   conectados grafo1 1 3  ==  True
   conectados grafo1 1 4  ==  False
   conectados grafo1 6 2  ==  False
   conectados grafo1 3 1  ==  True

Leer más…

TAD de los grafos - Nodos aislados de un grafo

El tipo abstracto de datos de los grafos

Dado un grafo dirigido G, diremos que un nodo está aislado si o bien de dicho nodo no sale ninguna arista o bien no llega al nodo ninguna arista. Por ejemplo, en el siguiente grafo

   grafo1 :: Grafo Int Int
   grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6),
                                (5,4),(6,2),(6,5)]

podemos ver que del nodo 1 salen 3 aristas pero no llega ninguna, por lo que lo consideramos aislado. Así mismo, a los nodos 2 y 4 llegan aristas pero no sale ninguna, por tanto también estarán aislados.

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

   aislados :: (Ix v, Num p) => Grafo v p -> [v]

tal que aislados g es la lista de nodos aislados del grafo g. Por ejemplo,

   aislados grafo1 == [1,2,4]

Leer más…

TAD de los grafos - Coloreado correcto de un mapa

El tipo abstracto de datos de los grafos

Un mapa se puede representar mediante un grafo donde los vértices son las regiones del mapa y hay una arista entre dos vértices si las correspondientes regiones son vecinas. Por ejemplo, el mapa siguiente

   +----------+----------+
   |    1     |     2    |
   +----+-----+-----+----+
   |    |           |    |
   | 3  |     4     | 5  |
   |    |           |    |
   +----+-----+-----+----+
   |    6     |     7    |
   +----------+----------+

se pueden representar por

   mapa :: Grafo Int Int
   mapa = creaGrafo' ND (1,7)
                     [(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),
                      (3,6),(4,5),(4,6),(4,7),(5,7),(6,7)]

Para colorear el mapa se dispone de 4 colores definidos por

   data Color = A | B | C | D
     deriving (Eq, Show)

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

   correcta :: [(Int,Color)] -> Grafo Int Int -> Bool

tal que correcta ncs m se verifica si ncs es una coloración del mapa m tal que todos las regiones vecinas tienen colores distintos. Por ejemplo,

   correcta [(1,A),(2,B),(3,B),(4,C),(5,A),(6,A),(7,B)] mapa == True
   correcta [(1,A),(2,B),(3,A),(4,C),(5,A),(6,A),(7,B)] mapa == False

Leer más…

TAD de los grafos - Grafos conexos

El tipo abstracto de datos de los grafos

Un grafo no dirigido G se dice conexo, si para cualquier par de vértices u y v en G, existe al menos una trayectoria (una sucesión de vértices adyacentes) de u a v.

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

   conexo :: (Ix a, Num p, Eq p) => Grafo a p -> Bool

tal que conexo g se verifica si el grafo g es conexo. Por ejemplo,

   conexo (creaGrafo' ND (1,3) [(1,2),(3,2)])        ==  True
   conexo (creaGrafo' ND (1,4) [(1,2),(3,2),(4,1)])  ==  True
   conexo (creaGrafo' ND (1,4) [(1,2),(3,4)])        ==  False

Leer más…

TAD de los grafos - Recorrido en anchura

El tipo abstracto de datos de los grafos

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

   recorridoEnAnchura :: (Num p, Eq p, Ix v) => v -> Grafo v p -> [v]

tal que recorridoEnAnchura i g es el recorrido en anchura del grafo g desde el vértice i. Por ejemplo, en el grafo

   +---> 2 <---+
   |           |
   |           |
   1 --> 3 --> 6 --> 5
   |                 |
   |                 |
   +---> 4 <---------+

definido por

   grafo1 :: Grafo Int Int
   grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)]

entonces

   recorridoEnAnchura 1 grafo1  ==  [1,2,3,4,6,5]

Leer más…

TAD de los grafos - Recorrido en profundidad

El tipo abstracto de datos de los grafos

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

   recorridoEnProfundidad :: (Num p, Eq p, Ix v) => v -> Grafo v p -> [v]

tal que recorridoEnProfundidad i g es el recorrido en profundidad del grafo g desde el vértice i. Por ejemplo, en el grafo

   +---> 2 <---+
   |           |
   |           |
   1 --> 3 --> 6 --> 5
   |                 |
   |                 |
   +---> 4 <---------+

definido por

   grafo1 :: Grafo Int Int
   grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)]

entonces

   recorridoEnProfundidad 1 grafo1  ==  [1,2,3,6,5,4]

Leer más…

TAD de los grafos - Anchura de un grafo

El tipo abstracto de datos de los grafos

En un grafo, la anchura de un nodo es el máximo de los absolutos de la diferencia entre el valor del nodo y los de sus adyacentes; y la anchura del grafo es la máxima anchura de sus nodos. Por ejemplo, en el grafo

   grafo1 :: Grafo Int Int
   grafo1 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5),
                                (2,4),(2,5),
                                (3,4),(3,5),
                                (4,5)]

su anchura es 4 y el nodo de máxima anchura es el 5.

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

   anchura :: Grafo Int Int -> Int

tal que (anchuraG g) es la anchura del grafo g. Por ejemplo,

   anchura grafo1  ==  4

Comprobar experimentalmente que la anchura del grafo ciclo de orden n es n-1.

Leer más…

TAD de los grafos - Recorridos en un grafo completo

El tipo abstracto de datos de los grafos

Definir la función

   recorridos :: [a] -> [[a]]

tal que recorridos xs es la lista de todos los posibles por el grafo cuyo conjunto de vértices es xs y cada vértice se encuentra conectado con todos los otros y los recorridos pasan por todos los vértices una vez y terminan en el vértice inicial. Por ejemplo,

   λ> recorridos [2,5,3]
   [[2,5,3,2],[5,2,3,5],[3,5,2,3],[5,3,2,5],[3,2,5,3],[2,3,5,2]]

Leer más…

TAD de los grafos - Grafos k-regulares

El tipo abstracto de datos de los grafos

Un grafo k-regular es un grafo con todos sus vértices son de grado k.

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

   regularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int

tal que (regularidad g) es la regularidad de g. Por ejemplo,

   regularidad (creaGrafo' ND (1,2) [(1,2),(2,3)]) == Just 1
   regularidad (creaGrafo' D (1,2) [(1,2),(2,3)])  == Nothing
   regularidad (completo 4)                        == Just 3
   regularidad (completo 5)                        == Just 4
   regularidad (grafoCiclo 4)                      == Just 2
   regularidad (grafoCiclo 5)                      == Just 2

Comprobar que el grafo completo de orden n es (n-1)-regular (para n de 1 a 20) y el grafo ciclo de orden n es 2-regular (para n de 3 a 20).

Leer más…

TAD de los grafos - Grafos regulares

El tipo abstracto de datos de los grafos

Un grafo regular es un grafo en el que todos sus vértices tienen el mismo grado.

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

   regular :: (Ix v,Num p) => Grafo v p -> Bool

tal que (regular g) se verifica si el grafo g es regular. Por ejemplo,

   λ> regular (creaGrafo' D (1,3) [(1,2),(2,3),(3,1)])
   True
   λ> regular (creaGrafo' ND (1,3) [(1,2),(2,3)])
   False
   λ> regular (completo 4)
   True

Comprobar que los grafos completos son regulares.

Leer más…

TAD de los grafos - Grado de un vértice

El tipo abstracto de datos de los grafos

El grado de un vértice v de un grafo dirigido g, es el número aristas de g que contiene a v. Si g es no dirigido, el grado de un vértice v es el número de aristas incidentes en v, teniendo en cuenta que los lazos se cuentan dos veces.

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

   grado :: (Ix v,Num p) => Grafo v p -> v -> Int

tal que grado g v es el grado del vértice v en el grafo g. Por ejemplo,

   g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)]
   g2 = creaGrafo' D  (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)]
   g3 = creaGrafo' D  (1,3) [(1,2),(2,2),(3,1),(3,2)]
   g4 = creaGrafo' D  (1,1) [(1,1)]
   g5 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)]
   g6 = creaGrafo' D  (1,3) [(1,2),(1,3),(2,3),(3,3)]
   grado g1 5 ==  4
   grado g2 5 ==  3
   grado g2 1 ==  3
   grado g3 2 ==  4
   grado g3 1 ==  2
   grado g3 3 ==  2
   grado g4 1 ==  2
   grado g6 3 ==  4
   grado g6 3 ==  4

Comprobar con QuickCheck que en todo grafo, el número de nodos de grado impar es par.

Leer más…

TAD de los grafos - Generadores de grafos

El tipo abstracto de datos de los grafos

Definir un generador de grafos para comprobar propiedades de grafos con QuickCheck y hacer el tipo de los Grafos un subtipo de Arbutrary.

Usando el generador, con QuickCheck que para cualquier grafo g, las sumas de los grados positivos y la de los grados negativos de los vértices de g son iguales.

Leer más…

TAD de los grafos - Grados positivos y negativos

El tipo abstracto de datos de los grafos

El grado positivo de un vértice v de un grafo g es el número de vértices de g adyacentes con v y su grado negativo es el número de vértices de g incidentes con v.

Usando el tipo abstrado de datos de los grafos, definir las funciones

   gradoPos :: (Ix v,Num p) => Grafo v p -> v -> Int
   gradoNeg :: (Ix v,Num p) => Grafo v p -> v -> Int

tales que + gradoPos g v es el grado positivo del vértice v en el grafo g. Por ejemplo,

     λ> g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)]
     λ> g2 = creaGrafo' D  (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)]
     λ> gradoPos g1 5
     4
     λ> gradoPos g2 5
     0
     λ> gradoPos g2 1
     3
  • gradoNeg g v es el grado negativo del vértice v en el grafo g. Por ejemplo,
     λ> gradoNeg g1 5
     4
     λ> gradoNeg g2 5
     3
     λ> gradoNeg g2 1
     0

Leer más…

TAD de los grafos - Número de aristas de un grafo

El tipo abstracto de datos de los grafos

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

   nAristas :: (Ix v,Num p) => Grafo v p ->  Int

tal que nAristas g es el número de aristas del grafo g. Si g es no dirigido, las aristas de v1 a v2 y de v2 a v1 sólo se cuentan una vez. Por ejemplo,

   λ> g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)]
   λ> g2 = creaGrafo' D  (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)]
   λ> g3 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)]
   λ> g4 = creaGrafo' ND (1,4) [(1,1),(1,2),(3,3)]
   λ> nAristas g1
   8
   λ> nAristas g2
   7
   λ> nAristas g3
   4
   λ> nAristas g4
   3
   λ> nAristas (completo 4)
   6
   λ> nAristas (completo 5)
   10

Definir la función

   prop_nAristasCompleto :: Int -> Bool

tal que prop_nAristasCompleto n se verifica si el número de aristas del grafo completo de orden n es n*(n-1)/2 y, usando la función, comprobar que la propiedad se cumple para n de 1 a 20.

Leer más…

TAD de los grafos - Lazos de un grafo

El tipo abstracto de datos de los grafos

Usando el tipo abstrado de datos de los grafos, definir las funciones

   lazos  :: (Ix v,Num p) => Grafo v p -> [(v,v)]
   nLazos :: (Ix v,Num p) => Grafo v p -> Int

tales que

  • lazos g es el conjunto de los lazos (es decir, aristas cuyos extremos son iguales) del grafo g. Por ejemplo,
     λ> ej1 = creaGrafo' D (1,3) [(1,1),(2,3),(3,2),(3,3)]
     λ> ej2 = creaGrafo' ND (1,3) [(2,3),(3,1)]
     λ> lazos ej1
     [(1,1),(3,3)]
     λ> lazos ej2
     []
  • nLazos g es el número de lazos del grafo g. Por ejemplo,
     λ> nLazos ej1
     2
     λ> nLazos ej2
     0

Leer más…

TAD de los grafos - Contiguos de un vértice

El tipo abstracto de datos de los grafos

En un un grafo g, los contiguos de un vértice v es el conjuntos de vértices x de g tales que x es adyacente o incidente con v.

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

   contiguos :: (Ix v,Num p) => Grafo v p -> v -> [v]

tal que contiguos g v es el conjunto de los vértices de g contiguos con el vértice v. Por ejemplo,

   λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> contiguos g1 1
   [2,3]
   λ> contiguos g1 2
   [2,1,3]
   λ> contiguos g1 3
   [1,2]
   λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> contiguos g2 1
   [2,3]
   λ> contiguos g2 2
   [1,2,3]
   λ> contiguos g2 3
   [1,2]

Leer más…

TAD de los grafos - Incidentes de un vértice

El tipo abstracto de datos de los grafos

En un un grafo g, los incidentes de un vértice v es el conjuntos de vértices x de g para los que hay un arco (o una arista) de x a v; es decir, que v es adyacente a x.

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

   incidentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]

tal que incidentes g v es la lista de los vértices incidentes en el vértice v. Por ejemplo,

   λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> incidentes g1 1
   [3]
   λ> incidentes g1 2
   [1,2,3]
   λ> incidentes g1 3
   []
   λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> incidentes g2 1
   [2,3]
   λ> incidentes g2 2
   [1,2,3]
   λ> incidentes g2 3
   [1,2]

Leer más…

Grafos completos

El tipo abstracto de datos de los grafos

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 abstrado de datos de los grafos, definir la función,

   completo :: Int -> Grafo Int Int

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

   λ> completo 4
   G ND ([1,2,3,4],[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)])

Leer más…

El tipo abstracto de datos de los grafos

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,

         12
    1 -------- 2
    | \78     /|
    |  \   32/ |
    |   \   /  |
  34|     5    |55
    |   /   \  |
    |  /44   \ |
    | /     93\|
    3 -------- 4
         61

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

   creaGrafo  :: (Ix v, Num p, Ord v, Ord p) =>
                  Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p
   creaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>
                  Orientacion -> (v,v) -> [(v,v)] -> Grafo v p
   dirigido   :: (Ix v,Num p) => (Grafo v p) -> Bool
   adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]
   nodos      :: (Ix v,Num p) => (Grafo v p) -> [v]
   aristas    :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
   aristaEn   :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool
   peso       :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p

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

   creaGrafo ND (1,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)]

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.

Leer más…

TAD de los polinomios - Factorización de un polinomio

El tipo abstracto de datos de los polinomios

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

   factorizacion :: Polinomio Int -> [Polinomio Int]

tal que factorizacion p es la lista de la descomposición del polinomio p en factores obtenida mediante el regla de Ruffini. Por ejemplo,

   λ> ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> ejPol1
   x^5 + 5*x^2 + 4*x
   λ> factorizacion ejPol1
   [1*x,1*x + 1,x^3 + -1*x^2 + 1*x + 4]
   λ> ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
   λ> ejPol2
   x^3 + 2*x^2 + -1*x + -2
   λ> factorizacion ejPol2
   [1*x + -1,1*x + 1,1*x + 2,1]

Leer más…

TAD de los polinomios - Raíces enteras de un polinomio

El tipo abstracto de datos de los polinomios

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

    raicesRuffini :: Polinomio Int -> [Int]

tal que raicesRuffini p es la lista de las raices enteras de p, calculadas usando el regla de Ruffini. Por ejemplo,

    λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
    λ> ejPol1
    3*x^4 + -5*x^2 + 3
    λ> raicesRuffini ejPol1
    []
    λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
    λ> ejPol2
    x^5 + 5*x^2 + 4*x
    λ> raicesRuffini ejPol2
    [0,-1]
    λ> ejPol3 = consPol 4 6 (consPol 1 2 polCero)
    λ> ejPol3
    6*x^4 + 2*x
    λ> raicesRuffini ejPol3
    [0]
    λ> ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
    λ> ejPol4
    x^3 + 2*x^2 + -1*x + -2
    λ> raicesRuffini ejPol4
    [1,-1,-2]

Leer más…

TAD de los polinomios - Reconocimiento de raíces por la regla de Ruffini

El tipo abstracto de datos de los polinomios

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

   esRaizRuffini :: Int -> Polinomio Int -> Bool

tal que esRaizRuffini r p se verifica si r es una raiz de p, usando para ello el regla de Ruffini. Por ejemplo,

   λ> ejPol = consPol 4 6 (consPol 1 2 polCero)
   λ> ejPol
   6*x^4 + 2*x
   λ> esRaizRuffini 0 ejPol
   True
   λ> esRaizRuffini 1 ejPol
   False

Leer más…

TAD de los polinomios - Regla de Ruffini

El tipo abstracto de datos de los polinomios

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

   cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int
   restoRuffini    :: Int -> Polinomio Int -> Int

tales que

  • cocienteRuffini r p es el cociente de dividir el polinomio p por el polinomio x-r. Por ejemplo:
     λ> ejPol = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
     λ> ejPol
     x^3 + 2*x^2 + -1*x + -2
     λ> cocienteRuffini 2 ejPol
     x^2 + 4*x + 7
     λ> cocienteRuffini (-2) ejPol
     x^2 + -1
     λ> cocienteRuffini 3 ejPol
     x^2 + 5*x + 14
  • restoRuffini r p es el resto de dividir el polinomio p por el polinomio x-r. Por ejemplo,
     λ> restoRuffini 2 ejPol
     12
     λ> restoRuffini (-2) ejPol
     0
     λ> restoRuffini 3 ejPol
     40

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.

Leer más…

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

El tipo abstracto de datos de los polinomios

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

   ruffiniDensa :: Int -> [Int] -> [Int]

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,

   ruffiniDensa 2 [1,2,-1,-2] == [1,4,7,12]
   ruffiniDensa 1 [1,2,-1,-2] == [1,3,2,0]

ya que

     | 1  2  -1  -2           | 1  2  -1  -2
   2 |    2   8  14         1 |    1   3   2
   --+--------------        --+-------------
     | 1  4   7  12           | 1  3   2   0

Leer más…

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

El tipo abstracto de datos de los polinomios

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

   terminoIndep :: (Num a, Eq a) => Polinomio  a -> a

tal que terminoIndep p es el término independiente del polinomio p. Por ejemplo,

   λ> ejPol1 = consPol 4 3 (consPol 2 5 (consPol 0 3 polCero))
   λ> ejPol1
   3*x^4 + 5*x^2 + 3
   λ> terminoIndep ejPol1
   3
   λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> ejPol2
   x^5 + 5*x^2 + 4*x
   λ> terminoIndep ejPol2
   0

Leer más…

TAD de los polinomios - Método de Horner del valor de un polinomio

El tipo abstracto de datos de los polinomios

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

   a*x^5 + b*x^4 + c*x^3 + d*x^2 + e*x + f

se representa como

  (((((0 * x + a) * x + b) * x + c) * x + d) * x + e) * x + f

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

  v(0) = 0
  v(1) = v(0)*x+a = 0*x+a = a
  v(2) = v(1)*x+b = a*x+b
  v(3) = v(2)*x+c = (a*x+b)*x+c = a*x^2+b*x+c
  v(4) = v(3)*x+d = (a*x^2+b*x+c)*x+d = a*x^3+b*x^2+c*x+d
  v(5) = v(4)*x+e = (a*x^3+b*x^2+c*x+d)*x+e = a*x^4+b*x^3+c*x^2+d*x+e
  v(6) = v(5)*x+f = (a*x^4+b*x^3+c*x^2+d*x+e)*x+f = a*x^5+b*x^4+c*x^3+d*x^2+e*x+f

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

   horner :: (Num a, Eq a) => Polinomio a -> a -> a

tal que horner p x es el valor del polinomio p al sustituir su variable por el número x. Por ejemplo,

   λ> pol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> pol1
   x^5 + 5*x^2 + 4*x
   λ> horner pol1 0
   0
   λ> horner pol1 1
   10
   λ> horner pol1 1.5
   24.84375
   λ> import Data.Ratio
   λ> horner pol1 (3%2)
   795 % 32

Leer más…

TAD de los polinomios - Divisibilidad de polinomios

El tipo abstracto de datos de los polinomios

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

   divisiblePol :: (Fractional a, Eq a) =>
                   Polinomio a -> Polinomio a -> Bool

tal que divisiblePol p q se verifica si el polinomio p es divisible por el polinomio q. Por ejemplo,

   λ> pol1 = consPol 2 8 (consPol 1 14 (consPol 0 3 polCero))
   λ> pol1
   8*x^2 + 14*x + 3
   λ> pol2 = consPol 1 2 (consPol 0 3 polCero)
   λ> pol2
   2*x + 3
   λ> pol3 = consPol 2 6 (consPol 1 2 polCero)
   λ> pol3
   6*x^2 + 2*x
   λ> divisiblePol pol1 pol2
   True
   λ> divisiblePol pol1 pol3
   False

Leer más…

TAD de los polinomios - División de polinomios

El tipo abstracto de datos de los polinomios

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

   cociente :: (Fractional a, Eq a) =>
               Polinomio a -> Polinomio a -> Polinomio a
   resto    :: (Fractional a, Eq a) =>
               Polinomio a -> Polinomio a -> Polinomio a

tales que

  • cociente p q es el cociente de la división de p entre q. Por ejemplo,
     λ> pol1 = consPol 3 2 (consPol 2 9 (consPol 1 10 (consPol 0 4 polCero)))
     λ> pol1
     2*x^3 + 9*x^2 + 10*x + 4
     λ> pol2 = consPol 2 1 (consPol 1 3 polCero)
     λ> pol2
     x^2 + 3*x
     λ> cociente pol1 pol2
     2.0*x + 3.0
  • resto p q es el resto de la división de p entre q. Por ejemplo,
     λ> resto pol1 pol2
     1.0*x + 4.0

Leer más…

TAD de los polinomios - Multiplicación de un polinomio por un número

El tipo abstracto de datos de los polinomios

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

   multEscalar :: (Num a, Eq a) => a -> Polinomio a -> Polinomio a

tal que multEscalar c p es el polinomio obtenido multiplicando el número c por el polinomio p. Por ejemplo,

   λ> ejPol = consPol 1 2 (consPol 0 3 polCero)
   λ> ejPol
   2*x + 3
   λ> multEscalar 4 ejPol
   8*x + 12
   λ> multEscalar (1 % 4) ejPol
   1 % 2*x + 3 % 4

Leer más…

TAD de los polinomios - Integral definida de un polinomio

El tipo abstracto de datos de los polinomios

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

   integralDef :: (Fractional t, Eq t) => Polinomio t -> t -> t -> t

tal que integralDef p a b es la integral definida del polinomio p entre a y b. Por ejemplo,

   λ> ejPol = consPol 7 2 (consPol 4 5 (consPol 2 5 polCero))
   λ> ejPol
   2*x^7 + 5*x^4 + 5*x^2
   λ> integralDef ejPol 0 1
   2.916666666666667
   λ> integralDef ejPol 0 1 :: Rational
   35 % 12

Leer más…

TAD de los polinomios - Integral de un polinomio

El tipo abstracto de datos de los polinomios

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

   integral :: (Fractional a, Eq a) => Polinomio a -> Polinomio a

tal que integral p es la integral del polinomio p cuyos coefientes son números racionales. Por ejemplo,

   λ> ejPol = consPol 7 2 (consPol 4 5 (consPol 2 5 polCero))
   λ> ejPol
   2*x^7 + 5*x^4 + 5*x^2
   λ> integral ejPol
   0.25*x^8 + x^5 + 1.6666666666666667*x^3
   λ> integral ejPol :: Polinomio Rational
   1 % 4*x^8 + x^5 + 5 % 3*x^3

Leer más…

TAD de los polinomios - Resta de polinomios

El tipo abstracto de datos de los polinomios

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

   restaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a

tal que restaPol p q es el polinomio obtenido restándole a p el q. Por ejemplo,

   λ> ejPol1 = consPol 5 1 (consPol 4 5 (consPol 2 5 (consPol 0 9 polCero)))
   λ> ejPol2 = consPol 4 3 (consPol 2 5 (consPol 0 3 polCero))
   λ> ejPol1
   x^5 + 5*x^4 + 5*x^2 + 9
   λ> ejPol2
   3*x^4 + 5*x^2 + 3
   λ> restaPol ejPol1 ejPol2
   x^5 + 2*x^4 + 6

Leer más…

TAD de los polinomios - Valor de un polinomio en un punto

El tipo abstracto de datos de los polinomios

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

   valor :: (Num a, Eq a) => Polinomio a -> a -> a

tal que valor p c es el valor del polinomio p al sustituir su variable por c. Por ejemplo,

   λ> ejPol = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
   λ> ejPol
   3*x^4 + -5*x^2 + 3
   λ> valor ejPol 0
   3
   λ> valor ejPol 1
   1
   λ> valor ejPol (-2)
   31

Leer más…

TAD de los polinomios - Producto de polinomios

El tipo abstracto de datos de los polinomios

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

   multPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a

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

   λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
   λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> ejPol1
   3*x^4 + -5*x^2 + 3
   λ> ejPol2
   x^5 + 5*x^2 + 4*x
   λ> multPol ejPol1 ejPol2
   3*x^9 + -5*x^7 + 15*x^6 + 15*x^5 + -25*x^4 + -20*x^3 + 15*x^2 + 12*x

Comprobar con QuickCheck las siguientes propiedades

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

Leer más…

TAD de los polinomios - Suma de polinomios

El tipo abstracto de datos de los polinomios

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

   sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a

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

   λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
   λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> ejPol1
   3*x^4 + -5*x^2 + 3
   λ> ejPol2
   x^5 + 5*x^2 + 4*x
   λ> sumaPol ejPol1 ejPol2
   x^5 + 3*x^4 + 4*x + 3

Comprobar con QuickCheck las siguientes propiedades:

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

Leer más…

TAD de los polinomios - Transformaciones entre polinomios y listas densas

El tipo abstracto de datos de los polinomios

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

   densaApolinomio :: (Num a, Eq a) => [a] -> Polinomio a
   polinomioAdensa :: (Num a, Eq a) => Polinomio a -> [a]

tales que

  • densaApolinomio xs es el polinomio cuya representación densa es xs. Por ejemplo,
     λ> densaApolinomio [9,0,0,5,0,4,7]
     9*x^6 + 5*x^3 + 4*x + 7
  • polinomioAdensa p es la representación densa del polinomio p. Por ejemplo,
     λ> ejPol = consPol 6 9 (consPol 3 5 (consPol 1 4 (consPol 0 7 polCero)))
     λ> ejPol
     9*x^6 + 5*x^3 + 4*x + 7
     λ> polinomioAdensa ejPol
     [9,0,0,5,0,4,7]

Comprobar con QuickCheck que ambas funciones son inversas.

Leer más…

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

El tipo abstracto de datos de los polinomios

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

   coeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a

tal que coeficiente k p es el coeficiente del término de grado k del polinomio p. Por ejemplo,

   λ> ejPol = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> ejPol
   x^5 + 5*x^2 + 4*x
   λ> coeficiente 2 ejPol
   5
   λ> coeficiente 3 ejPol
   0

Leer más…

TAD de los polinomios - Transformaciones entre polinomios y listas dispersas

El tipo abstracto de datos de los polinomios

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

   dispersaApolinomio :: (Num a, Eq a) => [(Int,a)] -> Polinomio a
   polinomioAdispersa :: (Num a, Eq a) => Polinomio a -> [(Int,a)]

tales que

  • dispersaApolinomio ps es el polinomiocuya representación dispersa es ps. Por ejemplo,
     λ> dispersaApolinomio [(6,9),(3,5),(1,4),(0,7)]
     9*x^6 + 5*x^3 + 4*x + 7
  • polinomioAdispersa p es la representación dispersa del polinomio p. Por ejemplo,
     λ> ejPol = consPol 6 9 (consPol 3 5 (consPol 1 4 (consPol 0 7 polCero)))
     λ> ejPol
     9*x^6 + 5*x^3 + 4*x + 7
     λ> polinomioAdispersa ejPol
     [(6,9),(3,5),(1,4),(0,7)]

Comprobar con QuickCheck que ambas funciones son inversas.

Leer más…

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

El tipo abstracto de datos de los polinomios

Definir las funciones

   densaAdispersa :: (Num a, Eq a) => [a] -> [(Int,a)]
   dispersaAdensa :: (Num a, Eq a) => [(Int,a)] -> [a]

tales que

  • densaAdispersa xs es la representación dispersa del polinomio cuya representación densa es xs. Por ejemplo,
     λ> densaAdispersa [9,0,0,5,0,4,7]
     [(6,9),(3,5),(1,4),(0,7)]
  • dispersaAdensa ps es la representación densa del polinomio cuya representación dispersa es ps. Por ejemplo,
     λ> dispersaAdensa [(6,9),(3,5),(1,4),(0,7)]
     [9,0,0,5,0,4,7]

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

Leer más…

El tipo abstracto de datos de los polinomios

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:

   polCero   :: Polinomio a
   esPolCero :: Polinomio a -> Bool
   consPol   :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a
   grado     :: Polinomio a -> Int
   coefLider :: Num a => Polinomio a -> a
   restoPol  :: (Num a, Eq a) => Polinomio a -> Polinomio a

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

   3*x^4 + -5*x^2 + 3

se representa por

   consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))

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

Leer más…

Clausura transitiva

Relaciones binarias

Usando el tipo de las relaciones binarias, definir las funciones

   clausuraTransitiva :: Eq a => Rel a -> Rel a

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

   λ> clausuraTransitiva (R ([1..6],[(1,2),(2,5),(5,6)]))
   R ([1,2,3,4,5,6],[(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)])

Comprobar con QuickCheck que clausuraTransitiva es transitiva.

Leer más…

Clausura simétrica

Relaciones binarias

Usando el tipo de las relaciones binarias, definir las funciones

   clausuraSimetrica :: Eq a => Rel a -> Rel a

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,

   λ> clausuraSimetrica (R ([1,3,5],[(1,1),(3,1),(1,5)]))
   R ([1,3,5],[(1,1),(3,1),(1,5),(1,3),(5,1)])

Comprobar con QuickCheck que clausuraSimetrica es simétrica.

Leer más…

Relaciones totales

Relaciones binarias

Usando el tipo de las relaciones binarias, definir las funciones

   total :: Eq a => Rel a -> Bool

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,

   total (R ([1,3],[(1,1),(3,1),(3,3)]))  ==  True
   total (R ([1,3],[(1,1),(3,1)]))        ==  False
   total (R ([1,3],[(1,1),(3,3)]))        ==  False

Leer más…

Relaciones antisimétricas

Relaciones binarias

Usando el tipo de las relaciones binarias, definir las funciones

   antisimetrica :: Eq a => Rel a -> Bool

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,

   antisimetrica (R ([1,2],[(1,2)]))        ==  True
   antisimetrica (R ([1,2],[(1,2),(2,1)]))  ==  False
   antisimetrica (R ([1,2],[(1,1),(2,1)]))  ==  True

Leer más…

Relaciones de equivalencia

Relaciones binarias

Usando el tipo de las relaciones binarias, definir las funciones

   esEquivalencia :: Ord a => Rel a -> Bool

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

   λ> esEquivalencia (R ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)]))
   True
   λ> esEquivalencia (R ([1,2,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)]))
   False
   λ> esEquivalencia (R ([1,3,5],[(1,1),(1,3),(3,3),(5,5)]))
   False

Leer más…

Relaciones binarias

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

   esRelacionBinaria :: Eq a => Rel a -> Bool

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

   λ> esRelacionBinaria (R ([1, 3], [(3, 1), (3, 3)]))
   True
   λ> esRelacionBinaria (R ([1, 3], [(3, 1), (3, 2)]))
   False

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

Leer más…

TAD de los conjuntos - TAD Producto cartesiano

El tipo abstracto de datos de los conjuntos

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

   productoC :: (Ord a, Ord b) => Conj a -> Conj b -> Conj (a,b)

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

   λ> ej1 = inserta 2 (inserta 5 vacio)
   λ> ej2 = inserta 9 (inserta 4 (inserta 3 vacio))
   λ> productoC ej1 ej2
   {(2,3), (2,4), (2,9), (5,3), (5,4), (5,9)}

Leer más…

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

El tipo abstracto de datos de los conjuntos

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

   particion :: Ord a => (a -> Bool) -> Conj a -> (Conj a, Conj a)

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,

   λ> ej = inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio)))
   λ> particion even ej
   ({2, 4},{5, 7})

Leer más…

TAD de los conjuntos - Subconjunto determinado por una propiedad

El tipo abstracto de datos de los conjuntos

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

   filtra :: Ord a => (a -> Bool) -> Conj a -> Conj a

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

   λ> filtra even (inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio))))
   {2, 4}
   λ> filtra odd (inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio))))
   {5, 7}

Leer más…

TAD de los conjuntos - Diferencia simétrica

El tipo abstracto de datos de los conjuntos

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

   diferenciaSimetrica :: Ord a => Conj a -> Conj a -> Conj a

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

   λ> ej1 = inserta 5 (inserta 3 (inserta 2 (inserta 7 vacio)))
   λ> ej2 = inserta 7 (inserta 4 (inserta 3 vacio))
   λ> diferenciaSimetrica ej1 ej2
   {2, 4, 5}

Leer más…

TAD de los conjuntos - Diferencia de conjuntos

El tipo abstracto de datos de los conjuntos

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

   diferencia :: Ord a => Conj a -> Conj a -> Conj a

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

   λ> ej1 = inserta 5 (inserta 3 (inserta 2 (inserta 7 vacio)))
   λ> ej2 = inserta 7 (inserta 4 (inserta 3 vacio))
   λ> diferencia ej1 ej2
   {2, 5}
   λ> diferencia ej2 ej1
   {4}
   λ> diferencia ej1 ej1
   {}

Leer más…

TAD de los conjuntos - Conjuntos disjuntos

El tipo abstracto de datos de los conjuntos

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

   disjuntos :: Ord a => Conj a -> Conj a -> Bool

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

   λ> ej1 = inserta 2 (inserta 5 vacio)
   λ> ej2 = inserta 4 (inserta 3 vacio)
   λ> ej3 = inserta 5 (inserta 3 vacio)
   λ> disjuntos ej1 ej2
   True
   λ> disjuntos ej1 ej3
   False

Leer más…

TAD de los conjuntos - Intersección de varios conjuntos

El tipo abstracto de datos de los conjuntos

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

   interseccionG :: Ord a => [Conj a] -> Conj a

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

   λ> ej1 = inserta 2 (inserta 3 (inserta 5 vacio))
   λ> ej2 = inserta 5 (inserta 2 (inserta 7 vacio))
   λ> ej3 = inserta 3 (inserta 2 (inserta 5 vacio))
   λ> interseccionG [ej1, ej2, ej3]
   {2, 5}

Leer más…

TAD de los conjuntos - Reconocimiento de subconjunto propio

El tipo abstracto de datos de los conjuntos

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

   subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool

tal subconjuntoPropio c1 c2 se verifica si c1 es un subconjunto propio de c2. Por ejemplo,

   λ> ej1 = inserta 5 (inserta 2 vacio)
   λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))
   λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))
   λ> ej4 = inserta 2 (inserta 5 vacio)
   λ> subconjuntoPropio ej1 ej2
   True
   λ> subconjuntoPropio ej1 ej3
   False
   λ> subconjuntoPropio ej1 ej4
   False

Leer más…

TAD de los conjuntos - Reconocimiento de subconjunto

El tipo abstracto de datos de los conjuntos

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

   subconjunto :: Ord a => Conj a -> Conj a -> Bool

tal que subconjunto c1 c2 se verifica si todos los elementos de c1 pertenecen a c2. Por ejemplo,

   λ> ej1 = inserta 5 (inserta 2 vacio)
   λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))
   λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))
   λ> subconjunto ej1 ej2
   True
   λ> subconjunto ej1 ej3
   False

Leer más…

TAD de los conjuntos - Transformaciones entre conjuntos y listas

El tipo abstracto de datos de los conjuntos

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

   listaAconjunto :: [a] -> Conj a
   conjuntoAlista :: Conj a -> [a]

tales que

  • listaAconjunto xs es el conjunto formado por los elementos de xs. Por ejemplo,
     λ> listaAconjunto [3, 2, 5]
     {2, 3, 5}
  • conjuntoAlista c es la lista formada por los elementos del conjunto c. Por ejemplo,
     λ> conjuntoAlista (inserta 5 (inserta 2 (inserta 3 vacio)))
     [2,3,5]

Comprobar con QuickCheck que ambas funciones son inversa; es decir,

   conjuntoAlista (listaAconjunto xs) = sort (nub xs)
   listaAconjunto (conjuntoAlista c)  = c

Leer más…

El tipo abstracto de datos de los conjuntos

El tipo abstracto de datos de los conjuntos

1. El tipo abstracto de datos de los conjuntos

Un conjunto es una estructura de datos, caracterizada por ser una colección de elementos en la que no importe ni el orden ni la repetición de elementos.

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

   vacio      :: Conj a
   inserta    :: Ord a => a -> Conj a -> Conj a
   menor      :: Ord a => Conj a -> a
   elimina    :: Ord a => a -> Conj a -> Conj a
   pertenece  :: Ord a => a -> Conj a -> Bool
   esVacio    :: Conj a -> Bool

tales que

  • vacio es el conjunto vacío.
  • (inserta x c) es el conjunto obtenido añadiendo el elemento x al conjunto c.
  • (menor c) es el menor elemento del conjunto c.
  • (elimina x c) es el conjunto obtenido eliminando el elemento x del conjunto c.
  • (pertenece x c) se verifica si x pertenece al conjunto c.
  • (esVacio c) se verifica si c es el conjunto vacío.

Las operaciones tienen que verificar las siguientes propiedades:

  • inserta x (inserta x c) == inserta x c
  • inserta x (inserta y c) == inserta y (inserta x c)
  • not (pertenece x vacio)
  • pertenece y (inserta x c) == (x==y) || pertenece y c
  • elimina x vacio == vacio
  • Si x == y, entonces elimina x (inserta y c) == elimina x c
  • Si x /= y, entonces elimina x (inserta y c) == inserta y (elimina x c)
  • esVacio vacio
  • not (esVacio (inserta x c))

Leer más…

TAD de las colas - Reconocimiento de subcolas

El tipo abstracto de datos de las colas

Utilizando el tipo abstracto de datos de las colas, definir las funciones

   subCola :: Eq a => Cola a -> Cola a -> Bool

tal que subCola c1 c2 se verifica si c1 es una subcola de c2. Por ejemplo,

   λ> ej1 = inserta 2 (inserta 3 vacia)
   λ> ej2 = inserta 7 (inserta 2 (inserta 3 (inserta 5 vacia)))
   λ> ej3 = inserta 2 (inserta 7 (inserta 3 (inserta 5 vacia)))
   λ> subCola ej1 ej2
   True
   λ> subCola ej1 ej3
   False

Leer más…

TAD de las colas - Reconocimiento de prefijos de colas

El tipo abstracto de datos de las colas

Utilizando el tipo abstracto de datos de las colas, definir las funciones

   prefijoCola :: Eq a => Cola a -> Cola a -> Bool

tal que prefijoCola c1 c2 se verifica si la cola c1 es justamente un prefijo de la cola c2. Por ejemplo,

   λ> ej1 = inserta 4 (inserta 2 vacia)
   λ> ej2 = inserta 5 (inserta 4 (inserta 2 vacia))
   λ> ej3 = inserta 5 (inserta 2 (inserta 4 vacia))
   λ> prefijoCola ej1 ej2
   True
   λ> prefijoCola ej1 ej3
   False

Leer más…

TAD de las colas - Inclusión de colas

El tipo abstracto de datos de las colas

Utilizando el tipo abstracto de datos de las colas, definir las funciones

   contenidaCola :: Eq a => Cola a -> Cola a -> Bool

tal que contenidaCola c1 c2 se verifica si todos los elementos de la cola c1 son elementos de la cola c2. Por ejemplo,

   λ> ej1 = inserta 3 (inserta 2 vacia)
   λ> ej2 = inserta 3 (inserta 4 vacia)
   λ> ej3 = inserta 5 (inserta 2 (inserta 3 vacia))
   λ> contenidaCola ej1 ej3
   True
   λ> contenidaCola ej2 ej3
   False

Leer más…

TAD de las colas - Agrupación de colas

El tipo abstracto de datos de las colas

Utilizando el tipo abstracto de datos de las colas, definir las funciones

   agrupaColas :: [Cola a] -> Cola a

tal que agrupaColas [c1,c2,c3,...,cn] es la cola formada mezclando las colas de la lista como sigue: mezcla c1 con c2, el resultado con c3, el resultado con c4, y así sucesivamente. Por ejemplo,

   λ> ej1 = inserta 2 (inserta 5 vacia)
   λ> ej2 = inserta 3 (inserta 7 (inserta 4 vacia))
   λ> ej3 = inserta 9 (inserta 0 (inserta 1 (inserta 6 vacia)))
   λ> agrupaColas []
   -
   λ> agrupaColas [ej1]
   5 | 2
   λ> agrupaColas [ej1, ej2]
   5 | 4 | 2 | 7 | 3
   λ> agrupaColas [ej1, ej2, ej3]
   5 | 6 | 4 | 1 | 2 | 0 | 7 | 9 | 3

Leer más…

TAD de las colas - Intercalado de dos colas

El tipo abstracto de datos de las colas

Utilizando el tipo abstracto de datos de las colas, definir las funciones

   intercalaColas :: Cola a -> Cola a -> Cola a

tal que intercalaColas c1 c2 es la cola formada por los elementos de c1 y c2 colocados en una cola, de forma alternativa, empezando por los elementos de c1. Por ejemplo,

   λ> ej1 = inserta 3 (inserta 5 vacia)
   λ> ej2 = inserta 0 (inserta 7 (inserta 4 (inserta 9 vacia)))
   λ> intercalaColas ej1 ej2
   5 | 9 | 3 | 4 | 7 | 0
   λ> intercalaColas ej2 ej1
   9 | 5 | 4 | 3 | 7 | 0

Leer más…

TAD de las colas - Extensión de colas

El tipo abstracto de datos de las colas

Utilizando el tipo abstracto de datos de las colas, definir las funciones

   extiendeCola :: Cola a -> Cola a -> Cola a

tal que extiendeCola c1 c2 es la cola que resulta de poner los elementos de la cola c2 a continuación de los de la cola de c1. Por ejemplo,

   λ> ej1 = inserta 3 (inserta 2 vacia)
   λ> ej2 = inserta 5 (inserta 3 (inserta 4 vacia))
   λ> ej1
   2 | 3
   λ> ej2
   4 | 3 | 5
   λ> extiendeCola ej1 ej2
   2 | 3 | 4 | 3 | 5
   λ> extiendeCola ej2 ej1
   4 | 3 | 5 | 2 | 3

Leer más…

TAD de las colas - Alguno de los elementos verifican una propiedad

El tipo abstracto de datos de las colas

Utilizando el tipo abstracto de datos de las colas, definir las funciones

   algunoVerifica :: (a -> Bool) -> Cola a -> Bool

tal que algunoVerifica p c se verifica si alguno de los elementos de la cola c cumplen la propiedad p. Por ejemplo,

   algunoVerifica (< 0) (inserta 3 (inserta (-2) vacia)) == True
   algunoVerifica (< 0) (inserta 3 (inserta 2 vacia))    == False

Leer más…

TAD de las colas - Transformaciones entre colas y listas

El tipo abstracto de datos de las colas

Utilizando el tipo abstracto de datos de las colas, definir las funciones

   listaAcola :: [a] -> Cola a
   colaAlista :: Cola a -> [a]

tales que

  • listaAcola xs es la cola formada por los elementos de xs. Por ejemplo,
     λ> listaAcola [3, 2, 5]
     3 | 2 | 5
  • colaAlista c es la lista formada por los elementos de la cola c. Por ejemplo,
     λ> colaAlista (inserta 5 (inserta 2 (inserta 3 vacia)))
     [3, 2, 5]

Comprobar con QuickCheck que ambas funciones son inversa; es decir,

   colaAlista (listaAcola xs) = xs
   listaAcola (colaAlista c)  = c

Leer más…

El tipo abstracto de datos de las colas

El tipo abstracto de datos de las colas

1. El tipo abstracto de datos de las colas

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción se realiza por un extremo (el posterior o final) y la operación de extracción por el otro (el anterior o frente).

Las operaciones que definen a tipo abstracto de datos (TAD) de las colas (cuyos elementos son del tipo a) son las siguientes:

   vacia   :: Cola a
   inserta :: a -> Cola a -> Cola a
   primero :: Cola a -> a
   resto   :: Cola a -> Cola a
   esVacia :: Cola a -> Bool

tales que

  • vacia es la cola vacía.
  • (inserta x c) es la cola obtenida añadiendo x al final de c.
  • (primero c) es el primero de la cola c.
  • (resto c) es la cola obtenida eliminando el primero de c.
  • (esVacia c) se verifica si c es la cola vacía.

Las operaciones tienen que verificar las siguientes propiedades:

  • primero (inserta x vacia) == x
  • Si c es una cola no vacía, entonces primero (inserta x c) == primero c,
  • resto (inserta x vacia) == vacia
  • Si c es una cola no vacía, entonces resto (inserta x c) == inserta x (resto c)
  • esVacia vacia
  • not (esVacia (inserta x c))

Leer más…