Ir al contenido principal

Árboles con la misma forma

Tipos definidos y tipos de datos algebraicos

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol a = Hoja a
                | Nodo (Arbol a) (Arbol a)
     deriving (Show, Eq)

Definir la función

   mismaForma :: Arbol a -> Arbol b -> Bool

tal que mismaForma t1 t2 se verifica si t1 y t2 tienen la misma estructura. Por ejemplo,

   λ> arbol1 = Hoja 5
   λ> arbol2 = Hoja 3
   λ> mismaForma arbol1 arbol2
   True
   λ> arbol3 = Nodo (Hoja 6) (Hoja 7)
   λ> mismaForma arbol1 arbol3
   False
   λ> arbol4 = Nodo (Hoja 9) (Hoja 5)
   λ> mismaForma arbol3 arbol4
   True

Leer más…

Aplicación de una función a un árbol

Tipos definidos y tipos de datos algebraicos

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol a = Hoja a
                | Nodo (Arbol a) (Arbol a)
     deriving (Show, Eq)

Definir la función

   mapArbol :: (a -> b) -> Arbol a -> Arbol b

tal que mapArbol f t es el árbolo obtenido aplicando la función f a los elementos del árbol t. Por ejemplo,

   λ> mapArbol (+ 1) (Nodo (Hoja 2) (Hoja 4))
   Nodo (Hoja 3) (Hoja 5)

Leer más…

Altura de un árbol binario

Tipos definidos y tipos de datos algebraicos

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol a = Hoja a
                | Nodo (Arbol a) (Arbol a)

Definir la función

   altura :: Arbol a -> Int

tal que altura t es la altura del árbol t. Por ejemplo,

   λ> altura (Hoja 1)
   0
   λ> altura (Nodo (Hoja 1) (Hoja 6))
   1
   λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Hoja 2))
   2
   λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Nodo (Hoja 2) (Hoja 7)))
   2

Leer más…

El tipo de los árboles binarios con valores en las hojas.

Tipos definidos y tipos de datos algebraicos

1. El tipo de los árboles binarios con valores en las hojas en Haskell

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

usando el tipo de los árboles binarios con valores en las hojas definido como se muestra a continuación.

data Arbol a = Hoja a
             | Nodo (Arbol a) (Arbol a)

2. El tipo de los árboles binarios con valores en las hojas en Python

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo(Nodo(Hoja(1), Hoja(4)),
                  Nodo(Hoja(6), Hoja(9)))

usando el tipo de los árboles binarios con valores en las hojas definido como se muestra a continuación.

from dataclasses import dataclass
from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class Hoja(Arbol[A]):
    x: A

@dataclass
class Nodo(Arbol[A]):
    i: Arbol[A]
    d: Arbol[A]

El tipo de las fórmulas proposicionales - Reconocedor de tautologías

Tipos definidos y tipos de datos algebraicos

Una fórmula es una tautología si es verdadera en todas sus interpretaciones. Por ejemplo,

  • (A ∧ B) → A es una tautología
  • A → (A ∧ B) no es una tautología

Usando el tipo de las fórmulas proposicionales definido en el ejercicio anterior, definir la función

   esTautologia :: FProp -> Bool

tal que esTautologia p se verifica si la fórmula p es una tautología. Por ejemplo,

   λ> esTautologia (Impl (Conj (Var 'A') (Var 'B')) (Var 'A'))
   True
   λ> esTautologia (Impl (Var 'A') (Conj (Var 'A') (Var 'B')))
   False

Leer más…

El tipo de las fórmulas proposicionales - Interpretaciones de una fórmula

Tipos definidos y tipos de datos algebraicos

Usando el tipo de las fórmulas proposicionales definido en el ejercicio anterior, definir la función

   interpretaciones :: FProp -> [Interpretacion]

tal que interpretaciones p es la lista de las interpretaciones de la fórmula p. Por ejemplo,

   λ> interpretaciones (Impl (Var 'A') (Conj (Var 'A') (Var 'B')))
   [[('A',False),('B',False)],
    [('A',False),('B',True)],
    [('A',True),('B',False)],
    [('A',True),('B',True)]]

Leer más…

El tipo de las fórmulas proposicionales - Valor de una fórmula

Tipos definidos y tipos de datos algebraicos

Una interpretación de una fórmula es una función de sus variables en los booleanos. Por ejemplo, la interpretación que a la variable A le asigna verdadero y a la B falso se puede representar por

   [('A', True), ('B', False)]

El tipo de las intepretaciones de puede definir por

   type Interpretacion = [(Char, Bool)]

El valor de una fórmula en una interpretación se calcula usando las funciones de verdad de las conectivas que se muestran a continuación

   |---+----|   |---+---+-------+-------|
   | p | ¬p |   | p | q | p ∧ q | p → q |
   |---+----|   |---+---+-------+-------|
   | T | F  |   | T | T | T     | T     |
   | F | T  |   | T | F | F     | F     |
   |---+----|   | F | T | F     | T     |
                | F | F | F     | T     |
                |---+---+-------+-------|

Usando el tipo de las fórmulas proposicionales definido en el ejercicio anterior, definir la función

   valor :: Interpretacion -> FProp -> Bool

tal que valor i p es el valor de la fórmula p en la interpretación i. Por ejemplo,

   λ> p = Impl (Var 'A') (Conj (Var 'A') (Var 'B'))
   λ> valor [('A',False),('B',False)] p
   True
   λ> valor [('A',True),('B',False)] p
   False

Leer más…

El tipo de las fórmulas proposicionales - Variables de una fórmula

Tipos definidos y tipos de datos algebraicos

Usando el tipo de las fórmulas proposicionales definido en el ejercicio anterior, definir la función

   variables :: FProp -> [Char]

tal que variables p es la lista de las variables de la fórmula p. Por ejemplo,

   λ> variables (Impl (Var 'A') (Conj (Const False) (Neg (Var 'B'))))
   "AB"
   λ> variables (Impl (Var 'A') (Conj (Var 'A') (Neg (Var 'B'))))
   "AAB"

Leer más…

El tipo de las fórmulas proposicionales

Tipos definidos y tipos de datos algebraicos

1. El tipo de las fórmulas proposicionales en Haskell

La fórmula A → ⊥ ∧ ¬B se representa por

   Impl (Var 'A') (Conj (Const False) (Neg (Var 'B')))

usando el tipo de las fórmulas proposicionales definido por

data FProp = Const Bool
           | Var Char
           | Neg FProp
           | Conj FProp FProp
           | Impl FProp FProp
  deriving Show

1. El tipo de las fórmulas proposicionales en Python

La fórmula A → ⊥ ∧ ¬B se representa por

   Impl(Var('A'), Conj(Const(False), Neg (Var('B'))))

usando el tipo de las fórmulas proposicionales definido por

from dataclasses import dataclass

@dataclass
class FProp:
    pass

@dataclass
class Const(FProp):
    x: bool

@dataclass
class Var(FProp):
    x: str

@dataclass
class Neg(FProp):
    x: FProp

@dataclass
class Conj(FProp):
    x: FProp
    y: FProp

@dataclass
class Impl(FProp):
    x: FProp
    y: FProp

El tipo de los árboles binarios

Tipos definidos y tipos de datos algebraicos

El árbol binario

        5
       / \
      /   \
     3     7
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4))
                  5
                  (Nodo (Hoja 6) 7 (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol = Hoja Int
              | Nodo Arbol Int Arbol

Definir las funciones

   ocurre :: Int -> Arbol -> Bool
   aplana :: Arbol -> [Int]

tales que

  • ocurre m a se verifica si m ocurre en el árbol a. Por ejemplo,
     ocurre 4  ejArbol  ==  True
     ocurre 10 ejArbol  ==  False
  • aplana a es la lista obtenida aplanando el árbol a. Por ejemplo,
     aplana ejArbol  ==  [1,3,4,5,6,7,9]

Leer más…