Álgebra

Polinomios de Bell

PorJosé A. Alonso 31-mayo-202229-mayo-2022

Los polinomios de Bell forman una sucesión de polinomios, definida como sigue:

B₀(x) = 1 (polinomio unidad)
Bₙ(x) = x·[Bₙ(x) + Bₙ'(x)] (donde Bₙ'(x) es la derivada de Bₙ(x))

Por ejemplo,

   B₀(x) = 1                     = 1
   B₁(x) = x·(1+0)               = x     
   B₂(x) = x·(x+1)               = x²+x         
   B₃(x) = x·(x²+x+2x+1)         = x³+3x²+x    
   B₄(x) = x·(x³+3x²+x+3x²+6x+1) = x⁴+6x³+7x²+x

B₀(x) = 1 = 1

B₁(x) = x·(1+0) = x

B₂(x) = x·(x+1) = x²+x

B₃(x) = x·(x²+x+2x+1) = x³+3x²+x

B₄(x) = x·(x³+3x²+x+3x²+6x+1) = x⁴+6x³+7x²+x

Definir la función

   polBell :: Integer -> Polinomio Integer

1	polBell :: Integer -> Polinomio Integer

tal que (polBell n) es el polinomio de Bell de grado n. Por ejemplo,

   polBell 4                    ==  x^4 + 6*x^3 + 7*x^2 + 1*x
   coeficiente 2 (polBell 4)    ==  7
   coeficiente 2 (polBell 30)   ==  536870911
   coeficiente 1 (polBell 1000) == 1
   length (show (coeficiente 9 (polBell 2000)))  ==  1903

polBell 4 == x^4 + 6*x^3 + 7*x^2 + 1*x

coeficiente 2 (polBell 4) == 7

coeficiente 2 (polBell 30) == 536870911

coeficiente 1 (polBell 1000) == 1

length (show (coeficiente 9 (polBell 2000))) == 1903

Notas: Se usa la librería I1M.PolOperaciones que se encuentra aquí y se describe aquí. Además, en el último ejemplo se usa la función coeficiente tal que (coeficiente k p) es el coeficiente del término de grado k en el polinomio p definida por

   coeficiente :: Num a => Int -> Polinomio a -> a
   coeficiente k p | k == n                 = coefLider p
                   | k > grado (restoPol p) = 0
                   | otherwise              = coeficiente k (restoPol p)
                   where n = grado p

coeficiente :: Num a => Int -> Polinomio a -> a

coeficiente k p | k == n = coefLider p

| k > grado (restoPol p) = 0

| otherwise = coeficiente k (restoPol p)

where n = grado p

Soluciones

import Data.List          (genericIndex)
import I1M.PolOperaciones (Polinomio, coefLider, consPol, derivada,
                           grado, multPol, polCero, polUnidad, restoPol,
                           sumaPol) 
import Test.QuickCheck    (Positive (Positive), quickCheck)

-- Función auxiliar
-- ================

-- (coeficiente k p) es el coeficiente del término de grado k en el
-- polinomio p.
coeficiente :: Num a => Int -> Polinomio a -> a
coeficiente k p | k == n                 = coefLider p
                | k > grado (restoPol p) = 0
                | otherwise              = coeficiente k (restoPol p)
                where n = grado p

-- 1ª solución
-- ===========

polBell1 :: Integer -> Polinomio Integer
polBell1 0 = polUnidad
polBell1 n = multPol (consPol 1 1 polCero) (sumaPol p (derivada p))
  where p = polBell1 (n-1)

-- 2ª solución
-- ===========

polBell2 :: Integer -> Polinomio Integer
polBell2 n = sucPolinomiosBell `genericIndex` n

sucPolinomiosBell :: [Polinomio Integer]
sucPolinomiosBell = iterate f polUnidad
  where f p = multPol (consPol 1 1 polCero) (sumaPol p (derivada p))

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_polBell :: Positive Integer -> Bool 
prop_polBell (Positive n) =
  polBell1 n == polBell2 n

-- La comprobación es
--    λ> quickCheck prop_polBell
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (show (coeficiente 9 (polBell1 2000)))
--    1903
--    (5.37 secs, 4,829,322,368 bytes)
--    λ> length (show (coeficiente 9 (polBell2 2000)))
--    1903
--    (4.03 secs, 4,825,094,064 bytes)

import Data.List (genericIndex)

import I1M.PolOperaciones (Polinomio, coefLider, consPol, derivada,

grado, multPol, polCero, polUnidad, restoPol,

sumaPol)

import Test.QuickCheck (Positive (Positive), quickCheck)

-- Función auxiliar

-- ================

-- (coeficiente k p) es el coeficiente del término de grado k en el

-- polinomio p.

coeficiente :: Num a => Int -> Polinomio a -> a

coeficiente k p | k == n = coefLider p

| k > grado (restoPol p) = 0

| otherwise = coeficiente k (restoPol p)

where n = grado p

-- 1ª solución

-- ===========

polBell1 :: Integer -> Polinomio Integer

polBell1 0 = polUnidad

polBell1 n = multPol (consPol 1 1 polCero) (sumaPol p (derivada p))

where p = polBell1 (n-1)

-- 2ª solución

-- ===========

polBell2 :: Integer -> Polinomio Integer

polBell2 n = sucPolinomiosBell `genericIndex` n

sucPolinomiosBell :: [Polinomio Integer]

sucPolinomiosBell = iterate f polUnidad

where f p = multPol (consPol 1 1 polCero) (sumaPol p (derivada p))

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_polBell :: Positive Integer -> Bool

prop_polBell (Positive n) =

polBell1 n == polBell2 n

-- La comprobación es

-- λ> quickCheck prop_polBell

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> length (show (coeficiente 9 (polBell1 2000)))

-- 1903

-- (5.37 secs, 4,829,322,368 bytes)

-- λ> length (show (coeficiente 9 (polBell2 2000)))

-- 1903

-- (4.03 secs, 4,825,094,064 bytes)

El código se encuentra en GitHub.

Clausura de un conjunto respecto de una función

PorJosé A. Alonso 2-mayo-20223-mayo-2022

Un conjunto A está cerrado respecto de una función f si para elemento x de A se tiene que f(x) pertenece a A. La clausura de un conjunto B respecto de una función f es el menor conjunto A que contiene a B y es cerrado respecto de f. Por ejemplo, la clausura de {0,1,2] respecto del opuesto es {-2,-1,0,1,2}.

Definir la función

   clausura :: Ord a => (a -> a) -> [a] -> [a]

1	clausura :: Ord a => (a -> a) -> [a] -> [a]

tal que (clausura f xs) es la clausura de xs respecto de f. Por ejemplo,

   clausura (\x -> -x) [0,1,2]         ==  [-2,-1,0,1,2]
   clausura (\x -> (x+1) `mod` 5) [0]  ==  [0,1,2,3,4]
   length (clausura (\x -> (x+1) `mod` (10^6)) [0]) == 1000000

clausura (\x -> -x) [0,1,2] == [-2,-1,0,1,2]

clausura (\x -> (x+1) `mod` 5) [0] == [0,1,2,3,4]

length (clausura (\x -> (x+1) `mod` (10^6)) [0]) == 1000000

Soluciones

module Clausura where

import Data.List ((\\), nub, sort, union)
import Test.QuickCheck.HigherOrder (quickCheck')
import qualified Data.Set as S (Set, difference, fromList, map, null, toList, union)

-- 1ª solución
-- ===========

clausura1 :: Ord a => (a -> a) -> [a] -> [a]
clausura1 f xs
  | esCerrado f xs = sort xs
  | otherwise      = clausura1 f (expansion f xs)

-- (esCerrado f xs) se verifica si al aplicar f a cualquier elemento de
-- xs se obtiene un elemento de xs. Por ejemplo,
--    λ> esCerrado (\x -> -x) [0,1,2]
--    False
--    λ> esCerrado (\x -> -x) [0,1,2,-2,-1]
--    True
esCerrado :: Ord a => (a -> a) -> [a] -> Bool
esCerrado f xs = all (`elem` xs) (map f xs)

-- (expansion f xs) es la lista (sin repeticiones) obtenidas añadiéndole
-- a xs el resulta de aplicar f a sus elementos. Por ejemplo,
--    expansion (\x -> -x) [0,1,2]  ==  [0,1,2,-1,-2]
expansion :: Ord a => (a -> a) -> [a] -> [a]
expansion f xs = xs `union` map f xs

-- 2ª solución
-- ===========

clausura2 :: Ord a => (a -> a) -> [a] -> [a]
clausura2 f xs = sort (until (esCerrado f) (expansion f) xs)

-- 3ª solución
-- ===========

clausura3 :: Ord a => (a -> a) -> [a] -> [a]
clausura3 f xs = aux xs xs
  where aux ys vs | null ns   = sort vs
                  | otherwise = aux ns (vs ++ ns)
          where ns = nub (map f ys) \\ vs

-- 4ª solución
-- ===========

clausura4 :: Ord a => (a -> a) -> [a] -> [a]
clausura4 f xs = S.toList (clausura4' f (S.fromList xs))

clausura4' :: Ord a => (a -> a) -> S.Set a -> S.Set a
clausura4' f xs = aux xs xs
  where aux ys vs | S.null ns = vs
                  | otherwise = aux ns (vs `S.union` ns)
          where ns = S.map f ys `S.difference` vs

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_clausura :: (Int -> Int) -> [Int] -> Bool
prop_clausura f xs =
  all (== clausura1 f xs')
      [ clausura2 f xs'
      , clausura3 f xs'
      , clausura4 f xs'
      ]
  where xs' = sort (nub xs)

-- La comprobación es
--    λ> quickCheck' prop_clausura
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (clausura1 (\x -> (x+1) `mod` 800) [0])
--    800
--    (1.95 secs, 213,481,560 bytes)
--    λ> length (clausura2 (\x -> (x+1) `mod` 800) [0])
--    800
--    (1.96 secs, 213,372,824 bytes)
--    λ> length (clausura3 (\x -> (x+1) `mod` 800) [0])
--    800
--    (0.03 secs, 42,055,128 bytes)
--    λ> length (clausura4 (\x -> (x+1) `mod` 800) [0])
--    800
--    (0.01 secs, 1,779,768 bytes)
--
--    λ> length (clausura3 (\x -> (x+1) `mod` (10^4)) [0])
--    10000
--    (2.50 secs, 8,080,105,816 bytes)
--    λ> length (clausura4 (\x -> (x+1) `mod` (10^4)) [0])
--    10000
--    (0.05 secs, 27,186,920 bytes)

module Clausura where

import Data.List ((\\), nub, sort, union)

import Test.QuickCheck.HigherOrder (quickCheck')

import qualified Data.Set as S (Set, difference, fromList, map, null, toList, union)

-- 1ª solución

-- ===========

clausura1 :: Ord a => (a -> a) -> [a] -> [a]

clausura1 f xs

| esCerrado f xs = sort xs

| otherwise = clausura1 f (expansion f xs)

-- (esCerrado f xs) se verifica si al aplicar f a cualquier elemento de

-- xs se obtiene un elemento de xs. Por ejemplo,

-- λ> esCerrado (\x -> -x) [0,1,2]

-- False

-- λ> esCerrado (\x -> -x) [0,1,2,-2,-1]

-- True

esCerrado :: Ord a => (a -> a) -> [a] -> Bool

esCerrado f xs = all (`elem` xs) (map f xs)

-- (expansion f xs) es la lista (sin repeticiones) obtenidas añadiéndole

-- a xs el resulta de aplicar f a sus elementos. Por ejemplo,

-- expansion (\x -> -x) [0,1,2] == [0,1,2,-1,-2]

expansion :: Ord a => (a -> a) -> [a] -> [a]

expansion f xs = xs `union` map f xs

-- 2ª solución

-- ===========

clausura2 :: Ord a => (a -> a) -> [a] -> [a]

clausura2 f xs = sort (until (esCerrado f) (expansion f) xs)

-- 3ª solución

-- ===========

clausura3 :: Ord a => (a -> a) -> [a] -> [a]

clausura3 f xs = aux xs xs

where aux ys vs | null ns = sort vs

| otherwise = aux ns (vs ++ ns)

where ns = nub (map f ys) \\ vs

-- 4ª solución

-- ===========

clausura4 :: Ord a => (a -> a) -> [a] -> [a]

clausura4 f xs = S.toList (clausura4' f (S.fromList xs))

clausura4' :: Ord a => (a -> a) -> S.Set a -> S.Set a

clausura4' f xs = aux xs xs

where aux ys vs | S.null ns = vs

| otherwise = aux ns (vs `S.union` ns)

where ns = S.map f ys `S.difference` vs

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_clausura :: (Int -> Int) -> [Int] -> Bool

prop_clausura f xs =

all (== clausura1 f xs')

[ clausura2 f xs'

, clausura3 f xs'

, clausura4 f xs'

]

where xs' = sort (nub xs)

-- La comprobación es

-- λ> quickCheck' prop_clausura

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> length (clausura1 (\x -> (x+1) `mod` 800) [0])

-- 800

-- (1.95 secs, 213,481,560 bytes)

-- λ> length (clausura2 (\x -> (x+1) `mod` 800) [0])

-- 800

-- (1.96 secs, 213,372,824 bytes)

-- λ> length (clausura3 (\x -> (x+1) `mod` 800) [0])

-- 800

-- (0.03 secs, 42,055,128 bytes)

-- λ> length (clausura4 (\x -> (x+1) `mod` 800) [0])

-- 800

-- (0.01 secs, 1,779,768 bytes)

-- λ> length (clausura3 (\x -> (x+1) `mod` (10^4)) [0])

-- 10000

-- (2.50 secs, 8,080,105,816 bytes)

-- λ> length (clausura4 (\x -> (x+1) `mod` (10^4)) [0])

-- 10000

-- (0.05 secs, 27,186,920 bytes)

El código se encuentra en GitHub.

La elaboración de las soluciones se describe en el siguiente vídeo

Polinomios de Bell

Soluciones

Clausura de un conjunto respecto de una función

Soluciones

Entradas recientes

Buscar

Correo electrónico