Misceláneas

Las expresiones aritméticas se pueden definir usando el siguiente tipo de datos

data Expr = N Int
          | X
          | S Expr Expr
          | R Expr Expr
          | P Expr Expr
          | E Expr Int
          deriving (Eq, Show)

Por ejemplo, la expresión

3*x - (x+2)^7

se puede definir por

R (P (N 3) X) (E (S X (N 2)) 7)

Definir la función

maximo :: Expr -> [Int] -> (Int,[Int])

tal que (maximo e xs) es el par formado por el máximo valor de la expresión e para los puntos de xs y en qué puntos alcanza el máximo. Por ejemplo,

λ> maximo (E (S (N 10) (P (R (N 1) X) X)) 2) [-3..3]
(100,[0,1])

Clausura respecto de una operación binaria

José A. Alonso

02-05-2018

Misceláneas

Se dice que una operador @ es interno en un conjunto A si al @ sobre elementos de A se obtiene como resultado otro elemento de A. Por ejemplo, la suma es un operador interno en el conjunto de los números naturales pares.

La clausura de un conjunto A con respecto a un operador @ es el menor conjunto B tal que A está contenido en B y el operador @ es interno en el conjunto B. Por ejemplo, la clausura del conjunto {2} con respecto a la suma es el conjunto de los números pares positivos:

{2, 4, 6, 8, ...} = {2*k | k <- [1..]}

Definir la función

clausuraOperador :: (Int -> Int -> Int) -> Set Int -> Set Int

tal que (clausuraOperador op xs) es la clausura del conjunto xs con respecto a la operación op. Por ejemplo,

clausuraOperador gcd (fromList [6,9,10])     ==
   fromList [1,2,3,6,9,10]
clausuraOperador gcd (fromList [42,70,105])  ==
   fromList [7,14,21,35,42,70,105]
clausuraOperador lcm (fromList [6,9,10])     ==
   fromList [6,9,10,18,30,90]
clausuraOperador lcm (fromList [2,3,5,7])    ==
   fromList [2,3,5,6,7,10,14,15,21,30,35,42,70,105,210]

Polinomio digital

José A. Alonso

01-05-2018

Misceláneas

Definir la función

polinomioDigital :: Int -> Polinomio Int

tal que (polinomioDigital n) es el polinomio cuyos coeficientes son los dígitos de n. Por ejemplo,

λ> polinomioDigital 5703
5*x^3 + 7*x^2 + 3

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería [[https://hackage.haskell.org/package/I1M-0.2.2/docs/I1M-Pol.html][I1M.Pol]].

Las sucesiones de Loomis

José A. Alonso

30-04-2018

Misceláneas

La sucesión de Loomis generada por un número entero positivo x es la sucesión cuyos términos se definen por

f(0) es x
f(n) es la suma de f(n-1) y el producto de los dígitos no nulos de f(n-1)

Los primeros términos de las primeras sucesiones de Loomis son

Generada por 1: 1, 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, ...
Generada por 2: 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, ...
Generada por 3: 3, 6, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, ...
Generada por 4: 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, 138, ...
Generada por 5: 5, 10, 11, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, ...

Se observa que a partir de un término todas coinciden con la generada por 1. Dicho término se llama el punto de convergencia. Por ejemplo,

la generada por 2 converge a 2
la generada por 3 converge a 26
la generada por 4 converge a 4
la generada por 5 converge a 26

Definir las siguientes funciones

sucLoomis           :: Integer -> [Integer]
convergencia        :: Integer -> Integer
graficaConvergencia :: [Integer] -> IO ()

tales que

(sucLoomis x) es la sucesión de Loomis generada por x. Por ejemplo,

λ> take 15 (sucLoomis 1)
[1,2,4,8,16,22,26,38,62,74,102,104,108,116,122]
λ> take 15 (sucLoomis 2)
[2,4,8,16,22,26,38,62,74,102,104,108,116,122,126]
λ> take 15 (sucLoomis 3)
[3,6,12,14,18,26,38,62,74,102,104,108,116,122,126]
λ> take 15 (sucLoomis 4)
[4,8,16,22,26,38,62,74,102,104,108,116,122,126,138]
λ> take 15 (sucLoomis 5)
[5,10,11,12,14,18,26,38,62,74,102,104,108,116,122]
λ> take 15 (sucLoomis 20)
[20,22,26,38,62,74,102,104,108,116,122,126,138,162,174]
λ> take 15 (sucLoomis 100)
[100,101,102,104,108,116,122,126,138,162,174,202,206,218,234]
λ> sucLoomis 1 !! (2*10^5)
235180736652

(convergencia x) es el término de convergencia de la sucesioń de Loomis generada por x xon la geerada por 1. Por ejemplo,

convergencia  2      ==  2
convergencia  3      ==  26
convergencia  4      ==  4
convergencia 17      ==  38
convergencia 19      ==  102
convergencia 43      ==  162
convergencia 27      ==  202
convergencia 58      ==  474
convergencia 63      ==  150056
convergencia 81      ==  150056
convergencia 89      ==  150056
convergencia (10^12) ==  1000101125092

(graficaConvergencia xs) dibuja la gráfica de los términos de convergencia de las sucesiones de Loomis generadas por los elementos de xs. Por ejemplo, (graficaConvergencia ([1..50]) dibuja

Las sucesiones de Loomis

y graficaConvergencia ([1..148] \ [63,81,89,137]) dibuja

Las sucesiones de Loomis

Operaciones con series de potencias

José A. Alonso

27-04-2018

Misceláneas

Una serie de potencias es una serie de la forma

a₀ + a₁x + a₂x² + a₃x³ + ...

Las series de potencias se pueden representar mediante listas infinitas. Por ejemplo, la serie de la función exponencial es

e^x = 1 + x + x²/2! + x³/3! + ...

y se puede representar por [1, 1, 1/2, 1/6, 1/24, 1/120, ...]

Las operaciones con series se pueden ver como una generalización de las de los polinomios.

En lo que sigue, usaremos el tipo (Serie a) para representar las series de potencias con coeficientes en a y su definición es

type Serie a = [a]

Definir las siguientes funciones

opuesta      :: Num a => Serie a -> Serie a
suma         :: Num a => Serie a -> Serie a -> Serie a
resta        :: Num a => Serie a -> Serie a -> Serie a
producto     :: Num a => Serie a -> Serie a -> Serie a
cociente     :: Fractional a => Serie a -> Serie a -> Serie a
derivada     :: (Num a, Enum a) => Serie a -> Serie a
integral     :: (Fractional a, Enum a) => Serie a -> Serie a
expx         :: Serie Rational

tales que

(opuesta xs) es la opuesta de la serie xs. Por ejemplo,

λ> take 7 (opuesta [-6,-4..])
[6,4,2,0,-2,-4,-6]

(suma xs ys) es la suma de las series xs e ys. Por ejemplo,

λ> take 7 (suma [1,3..] [2,4..])
[3,7,11,15,19,23,27]

(resta xs ys) es la resta de las series xs es ys. Por ejemplo,

λ> take 7 (resta [3,5..] [2,4..])
[1,1,1,1,1,1,1]
λ> take 7 (resta ([3,7,11,15,19,23,27] ++ repeat 0) [1,3..])
[2,4,6,8,10,12,14]

(producto xs ys) es el producto de las series xs e ys. Por ejemplo,

λ> take 7 (producto [3,5..] [2,4..])
[6,22,52,100,170,266,392]

(cociente xs ys) es el cociente de las series xs e ys. Por ejemplo,

λ> take 7 (cociente ([6,22,52,100,170,266,392] ++ repeat 0) [3,5..])
[2.0,4.0,6.0,8.0,10.0,12.0,14.0]

(derivada xs) es la derivada de la serie xs. Por ejemplo,

λ> take 7 (derivada [2,4..])
[4,12,24,40,60,84,112]

(integral xs) es la integral de la serie xs. Por ejemplo,

λ> take 7 (integral ([4,12,24,40,60,84,112] ++ repeat 0))
[0.0,4.0,6.0,8.0,10.0,12.0,14.0]

expx es la serie de la función exponencial. Por ejemplo,

λ> take 8 expx
[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
λ> take 8 (derivada expx)
[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
λ> take 8 (integral expx)
[0 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]

Diccionario inverso

José A. Alonso

26-04-2018

Misceláneas

El inverso de un diccionario d es el diccionario que a cada valor x le asigna la lista de claves cuyo valor en d es x. Por ejemplo, el inverso de

[("a",3),("b",2),("c",3),("d",2),("e",1)])

es

[(1,["e"]),(2,["d","b"]),(3,["c","a"])]

Definir la función

inverso :: (Ord k, Ord v) => Map k v -> Map v [k]

tal que (inverso d) es el inverso del diccionario d. Por ejemplo,

λ> inverso (fromList [("a",3),("b",2),("c",3),("d",2),("e",1)])
fromList [(1,["e"]),(2,["d","b"]),(3,["c","a"])]
λ> inverso (fromList [(x,x^2) | x <- [-3,-2..3]])
fromList [(0,[0]),(1,[1,-1]),(4,[2,-2]),(9,[3,-3])]

Subconjuntos con suma dada

José A. Alonso

25-04-2018

Misceláneas

Sea S un conjunto finito de números enteros positivos y n un número natural. El problema consiste en calcular los subconjuntos de S cuya suma es n.

Definir la función

subconjuntosSuma:: [Int] -> Int -> [[Int]] tal que

tal que (subconjuntosSuma xs n) es la lista de los subconjuntos de xs cuya suma es n. Por ejemplo,

λ> subconjuntosSuma [3,34,4,12,5,2] 9
[[4,5],[3,4,2]]
λ> subconjuntosSuma [3,34,4,12,5,2] 13
[]
λ> length (subconjuntosSuma [1..100] (sum [1..100]))
1

Sumas de subconjuntos

José A. Alonso

24-04-2018

Misceláneas

Definir la función

sumasSubconjuntos :: Set Int -> Set Int

tal que (sumasSubconjuntos xs) es el conjunto de las sumas de cada uno de los subconjuntos de xs. Por ejemplo,

λ> sumasSubconjuntos (fromList [3,2,5])
fromList [0,2,3,5,7,8,10]
λ> length (sumasSubconjuntos (fromList [-40,-39..40]))
1641

Subsucesiones crecientes de elementos consecutivos

José A. Alonso

23-04-2018

Misceláneas

Definir la función

subsucesiones :: [Integer] -> [[Integer]]

tal que (subsucesiones xs) es la lista de las subsucesiones crecientes de elementos consecutivos de xs. Por ejemplo,

subsucesiones [1,0,1,2,3,0,4,5]  == [[1],[0,1,2,3],[0,4,5]]
subsucesiones [5,6,1,3,2,7]      == [[5,6],[1,3],[2,7]]
subsucesiones [2,3,3,4,5]        == [[2,3],[3,4,5]]
subsucesiones [7,6,5,4]          == [[7],[6],[5],[4]]

Números compuestos por un conjunto de primos

José A. Alonso

20-04-2018

Misceláneas

Los números compuestos por un conjunto de primos son los números cuyos factores primos pertenecen al conjunto. Por ejemplo, los primeros números compuestos por [2,5,7] son

1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70,...

El 28 es compuesto ya que sus divisores primos son 2 y 7 que están en [2,5,7].

Definir la función

compuestos :: [Integer] -> [Integer]

tal que (compuesto ps) es la lista de los números compuestos por el conjunto de primos ps. Por ejemplo,

λ> take 20 (compuestos [2,5,7])
[1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70]
λ> take 20 (compuestos [2,5])
[1,2,4,5,8,10,16,20,25,32,40,50,64,80,100,125,128,160,200,250]
λ> take 20 (compuestos [2,3,5])
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]
λ> take 20 (compuestos [3,5,7,11,13])
[1,3,5,7,9,11,13,15,21,25,27,33,35,39,45,49,55,63,65,75]
λ> take 15 (compuestos [2])
[1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384]
λ> compuestos [2,7] !! (10^4)
57399514149595471961908157955229677377312712667508119466382354072731648
λ> compuestos [2,3,5] !! (10^5)
290237644800000000000000000000000000000

Exercitium

Máximos de expresiones aritméticas

Clausura respecto de una operación binaria

Polinomio digital

Las sucesiones de Loomis

Operaciones con series de potencias

Diccionario inverso

Subconjuntos con suma dada

Sumas de subconjuntos

Subsucesiones crecientes de elementos consecutivos

Números compuestos por un conjunto de primos