La semana en Exercitium (6 de mayo de 2023)

Esta semana he publicado en Exercitium las soluciones de los siguientes problemas sobre el tipo abstracto de los polinomios.

1. Comprobación de raíces de polinomios
2. Derivada de un polinomio
3. Resta de polinomios
4. Potencia de un polinomio
5. Integral de un polinomio

A continuación se muestran las soluciones.

1. Comprobación de raíces de polinomios

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

   esRaiz :: (Num a, Eq a) => a -> Polinomio a -> Bool

1	esRaiz :: (Num a, Eq a) => a -> Polinomio a -> Bool

tal que esRaiz c p se verifica si c es una raiz del polinomio p. Por ejemplo,

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

λ> ejPol = consPol 4 6 (consPol 1 2 polCero)

λ> ejPol

6*x^4 + 2*x

λ> esRaiz 0 ejPol

True

λ> esRaiz 1 ejPol

False

Soluciones

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

Soluciones en Haskell

import TAD.Polinomio (Polinomio, polCero, consPol)
import Pol_Valor_de_un_polinomio_en_un_punto (valor)

esRaiz :: (Num a, Eq a) => a -> Polinomio a -> Bool
esRaiz c p = valor p c == 0

import TAD.Polinomio (Polinomio, polCero, consPol)

import Pol_Valor_de_un_polinomio_en_un_punto (valor)

esRaiz :: (Num a, Eq a) => a -> Polinomio a -> Bool

esRaiz c p = valor p c == 0

Soluciones en Python

from typing import TypeVar

from src.Pol_Valor_de_un_polinomio_en_un_punto import valor
from src.TAD.Polinomio import Polinomio, consPol, polCero

A = TypeVar('A', int, float, complex)

def esRaiz(c: A, p: Polinomio[A]) -> bool:
    return valor(p, c) == 0

from typing import TypeVar

from src.Pol_Valor_de_un_polinomio_en_un_punto import valor

from src.TAD.Polinomio import Polinomio, consPol, polCero

A = TypeVar('A', int, float, complex)

def esRaiz(c: A, p: Polinomio[A]) -> bool:

return valor(p, c) == 0

2. Derivada de un polinomio

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

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

1	derivada :: (Eq a, Num a) => Polinomio a -> Polinomio a

tal que derivada p es la derivada del polinomio p. Por ejemplo,

   λ> ejPol = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> ejPol
   x^5 + 5*x^2 + 4*x
   λ> derivada ejPol
   5*x^4 + 10*x + 4

λ> ejPol = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))

λ> ejPol

x^5 + 5*x^2 + 4*x

λ> derivada ejPol

5*x^4 + 10*x + 4

Soluciones

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

Soluciones en Haskell

import TAD.Polinomio (Polinomio, polCero, consPol, grado, coefLider,
                      restoPol)
import Pol_Suma_de_polinomios (sumaPol)
import Test.QuickCheck

derivada :: (Eq a, Num a) => Polinomio a -> Polinomio a
derivada p
  | n == 0     = polCero
  | otherwise  = consPol (n-1) (b * fromIntegral n) (derivada r)
  where n = grado p
        b = coefLider p
        r = restoPol p

-- Propiedad. La derivada de la suma es la suma de las derivadas.
prop_derivada :: Polinomio Int -> Polinomio Int -> Bool
prop_derivada p q =
  derivada (sumaPol p q) == sumaPol (derivada p) (derivada q)

-- Comprobación
--    λ> quickCheck prop_derivada
--    OK, passed 100 tests.

import TAD.Polinomio (Polinomio, polCero, consPol, grado, coefLider,

restoPol)

import Pol_Suma_de_polinomios (sumaPol)

import Test.QuickCheck

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

derivada p

| n == 0 = polCero

| otherwise = consPol (n-1) (b * fromIntegral n) (derivada r)

where n = grado p

b = coefLider p

r = restoPol p

-- Propiedad. La derivada de la suma es la suma de las derivadas.

prop_derivada :: Polinomio Int -> Polinomio Int -> Bool

prop_derivada p q =

derivada (sumaPol p q) == sumaPol (derivada p) (derivada q)

-- Comprobación

-- λ> quickCheck prop_derivada

-- OK, passed 100 tests.

Soluciones en Python

from typing import TypeVar

from hypothesis import given

from src.Pol_Suma_de_polinomios import sumaPol
from src.TAD.Polinomio import (Polinomio, coefLider, consPol, grado, polCero,
                               polinomioAleatorio, restoPol)

A = TypeVar('A', int, float, complex)


def derivada(p: Polinomio[A]) -> Polinomio[A]:
    n = grado(p)
    if n == 0:
        return polCero()
    b = coefLider(p)
    r = restoPol(p)
    return consPol(n - 1, b * n, derivada(r))

# Propiedad. La derivada de la suma es la suma de las derivadas.
@given(p=polinomioAleatorio(), q=polinomioAleatorio())
def test_derivada(p: Polinomio[int], q: Polinomio[int]) -> None:
    assert derivada(sumaPol(p, q)) == sumaPol(derivada(p), derivada(q))

# La comprobación es
#    > poetry run pytest -q Pol_Derivada_de_un_polinomio.py
#    1 passed in 0.46s

from typing import TypeVar

from hypothesis import given

from src.Pol_Suma_de_polinomios import sumaPol

from src.TAD.Polinomio import (Polinomio, coefLider, consPol, grado, polCero,

polinomioAleatorio, restoPol)

A = TypeVar('A', int, float, complex)

def derivada(p: Polinomio[A]) -> Polinomio[A]:

n = grado(p)

if n == 0:

return polCero()

b = coefLider(p)

r = restoPol(p)

return consPol(n - 1, b * n, derivada(r))

# Propiedad. La derivada de la suma es la suma de las derivadas.

@given(p=polinomioAleatorio(), q=polinomioAleatorio())

def test_derivada(p: Polinomio[int], q: Polinomio[int]) -> None:

assert derivada(sumaPol(p, q)) == sumaPol(derivada(p), derivada(q))

# La comprobación es

# > poetry run pytest -q Pol_Derivada_de_un_polinomio.py

# 1 passed in 0.46s

3. Resta de polinomios

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

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

1	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

λ> 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

Soluciones

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

Soluciones en Haskell

import TAD.Polinomio (Polinomio, polCero, consPol)
import Pol_Suma_de_polinomios (sumaPol)
import Pol_Crea_termino (creaTermino)
import Pol_Producto_polinomios (multPorTerm)

restaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
restaPol p q  =
  sumaPol p (multPorTerm (creaTermino 0 (-1)) q)

import TAD.Polinomio (Polinomio, polCero, consPol)

import Pol_Suma_de_polinomios (sumaPol)

import Pol_Crea_termino (creaTermino)

import Pol_Producto_polinomios (multPorTerm)

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

restaPol p q =

sumaPol p (multPorTerm (creaTermino 0 (-1)) q)

Soluciones en Python

from typing import TypeVar

from src.Pol_Crea_termino import creaTermino
from src.Pol_Producto_polinomios import multPorTerm
from src.Pol_Suma_de_polinomios import sumaPol
from src.TAD.Polinomio import Polinomio, consPol, polCero

A = TypeVar('A', int, float, complex)

def restaPol(p: Polinomio[A], q: Polinomio[A]) -> Polinomio[A]:
    return sumaPol(p, multPorTerm(creaTermino(0, -1), q))

from typing import TypeVar

from src.Pol_Crea_termino import creaTermino

from src.Pol_Producto_polinomios import multPorTerm

from src.Pol_Suma_de_polinomios import sumaPol

from src.TAD.Polinomio import Polinomio, consPol, polCero

A = TypeVar('A', int, float, complex)

def restaPol(p: Polinomio[A], q: Polinomio[A]) -> Polinomio[A]:

return sumaPol(p, multPorTerm(creaTermino(0, -1), q))

4. Potencia de un polinomio

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

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

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

tal que potencia p n es la potencia n-ésima del polinomio p. Por ejemplo,

   λ> ejPol = consPol 1 2 (consPol 0 3 polCero)
   λ> ejPol
   2*x + 3
   λ> potencia ejPol 2
   4*x^2 + 12*x + 9
   λ> potencia ejPol 3
   8*x^3 + 36*x^2 + 54*x + 27

λ> ejPol = consPol 1 2 (consPol 0 3 polCero)

λ> ejPol

2*x + 3

λ> potencia ejPol 2

4*x^2 + 12*x + 9

λ> potencia ejPol 3

8*x^3 + 36*x^2 + 54*x + 27

Soluciones

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

Soluciones en Haskell

import TAD.Polinomio (Polinomio, polCero, consPol)
import Pol_Producto_polinomios (multPol)
import Test.QuickCheck

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

potencia :: (Num a, Eq a) => Polinomio a -> Int -> Polinomio a
potencia _ 0 = polUnidad
potencia p n = multPol p (potencia p (n-1))

polUnidad :: (Num a, Eq a) => Polinomio a
polUnidad = consPol 0 1 polCero

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

potencia2 :: (Num a, Eq a) => Polinomio a -> Int -> Polinomio a
potencia2 _ 0 = polUnidad
potencia2 p n
  | even n    = potencia2 (multPol p p) (n `div` 2)
  | otherwise = multPol p (potencia2 (multPol p p) ((n-1) `div` 2))

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

-- La propiedad es
prop_potencia :: Polinomio Int -> NonNegative Int -> Bool
prop_potencia p (NonNegative n) =
  potencia p n == potencia2 p n

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

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

-- La comparación es
--    λ> import TAD.Polinomio (grado)
--    λ> ejPol = consPol 1 2 (consPol 0 3 polCero)
--    λ> grado (potencia ejPol 1000)
--    1000
--    (4.57 secs, 2,409,900,720 bytes)
--    λ> grado (potencia2 ejPol 1000)
--    1000
--    (2.78 secs, 1,439,596,632 bytes)

import TAD.Polinomio (Polinomio, polCero, consPol)

import Pol_Producto_polinomios (multPol)

import Test.QuickCheck

-- 1ª solución

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

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

potencia _ 0 = polUnidad

potencia p n = multPol p (potencia p (n-1))

polUnidad :: (Num a, Eq a) => Polinomio a

polUnidad = consPol 0 1 polCero

-- 2ª solución

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

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

potencia2 _ 0 = polUnidad

potencia2 p n

| even n = potencia2 (multPol p p) (n `div` 2)

| otherwise = multPol p (potencia2 (multPol p p) ((n-1) `div` 2))

-- Comprobación de equivalencia

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

-- La propiedad es

prop_potencia :: Polinomio Int -> NonNegative Int -> Bool

prop_potencia p (NonNegative n) =

potencia p n == potencia2 p n

-- La comprobación es

-- λ> quickCheck prop_potencia

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> import TAD.Polinomio (grado)

-- λ> ejPol = consPol 1 2 (consPol 0 3 polCero)

-- λ> grado (potencia ejPol 1000)

-- 1000

-- (4.57 secs, 2,409,900,720 bytes)

-- λ> grado (potencia2 ejPol 1000)

-- 1000

-- (2.78 secs, 1,439,596,632 bytes)

Soluciones en Python

from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.Pol_Producto_polinomios import multPol
from src.TAD.Polinomio import Polinomio, consPol, polCero, polinomioAleatorio

setrecursionlimit(10**6)

A = TypeVar('A', int, float, complex)

# 1ª solución
# ===========

def potencia(p: Polinomio[A], n: int) -> Polinomio[A]:
    if n == 0:
        return consPol(0, 1, polCero())
    return multPol(p, potencia(p, n - 1))

# 2ª solución
# ===========

def potencia2(p: Polinomio[A], n: int) -> Polinomio[A]:
    if n == 0:
        return consPol(0, 1, polCero())
    if n % 2 == 0:
        return potencia2(multPol(p, p), n // 2)
    return multPol(p, potencia2(multPol(p, p), (n - 1) // 2))

# 3ª solución
# ===========

def potencia3(p: Polinomio[A], n: int) -> Polinomio[A]:
    r: Polinomio[A] = consPol(0, 1, polCero())
    for _ in range(0, n):
        r = multPol(p, r)
    return r

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(p=polinomioAleatorio(),
       n=st.integers(min_value=1, max_value=10))
def test_potencia(p: Polinomio[int], n: int) -> None:
    r = potencia(p, n)
    assert potencia2(p, n) == r
    assert potencia3(p, n) == r

# La comprobación es
#    src> poetry run pytest -q Pol_Potencia_de_un_polinomio.py
#    1 passed in 0.89s

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> from src.TAD.Polinomio import grado
#    >>> ejPol = consPol(1, 2, consPol(0, 3, polCero()))
#    >>> tiempo('grado(potencia(ejPol, 1000))')
#    8.58 segundos
#    >>> tiempo('grado(potencia2(ejPol, 1000))')
#    8.75 segundos

from sys import setrecursionlimit

from timeit import Timer, default_timer

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.Pol_Producto_polinomios import multPol

from src.TAD.Polinomio import Polinomio, consPol, polCero, polinomioAleatorio

setrecursionlimit(10**6)

A = TypeVar('A', int, float, complex)

# 1ª solución

# ===========

def potencia(p: Polinomio[A], n: int) -> Polinomio[A]:

if n == 0:

return consPol(0, 1, polCero())

return multPol(p, potencia(p, n - 1))

# 2ª solución

# ===========

def potencia2(p: Polinomio[A], n: int) -> Polinomio[A]:

if n == 0:

return consPol(0, 1, polCero())

if n % 2 == 0:

return potencia2(multPol(p, p), n // 2)

return multPol(p, potencia2(multPol(p, p), (n - 1) // 2))

# 3ª solución

# ===========

def potencia3(p: Polinomio[A], n: int) -> Polinomio[A]:

r: Polinomio[A] = consPol(0, 1, polCero())

for _ in range(0, n):

r = multPol(p, r)

return r

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(p=polinomioAleatorio(),

n=st.integers(min_value=1, max_value=10))

def test_potencia(p: Polinomio[int], n: int) -> None:

r = potencia(p, n)

assert potencia2(p, n) == r

assert potencia3(p, n) == r

# La comprobación es

# src> poetry run pytest -q Pol_Potencia_de_un_polinomio.py

# 1 passed in 0.89s

# Comparación de eficiencia

# =========================

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> from src.TAD.Polinomio import grado

# >>> ejPol = consPol(1, 2, consPol(0, 3, polCero()))

# >>> tiempo('grado(potencia(ejPol, 1000))')

# 8.58 segundos

# >>> tiempo('grado(potencia2(ejPol, 1000))')

# 8.75 segundos

5. Integral de un polinomio

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

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

1	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

λ> 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

Soluciones

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

Soluciones en Haskell

import TAD.Polinomio (Polinomio, polCero, consPol, esPolCero, grado,
                      coefLider, restoPol)
import Data.Ratio

integral :: (Fractional a, Eq a) => Polinomio a -> Polinomio a
integral p
  | esPolCero p = polCero
  | otherwise   = consPol (n+1) (b / fromIntegral (n+1)) (integral r)
  where n = grado p
        b = coefLider p
        r = restoPol p

import TAD.Polinomio (Polinomio, polCero, consPol, esPolCero, grado,

coefLider, restoPol)

import Data.Ratio

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

integral p

| esPolCero p = polCero

| otherwise = consPol (n+1) (b / fromIntegral (n+1)) (integral r)

where n = grado p

b = coefLider p

r = restoPol p

Soluciones en Python

from src.TAD.Polinomio import (Polinomio, coefLider, consPol, esPolCero, grado,
                               polCero, restoPol)


def integral(p: Polinomio[float]) -> Polinomio[float]:
    if esPolCero(p):
        return  polCero()
    n = grado(p)
    b = coefLider(p)
    r = restoPol(p)
    return consPol(n + 1, b / (n + 1), integral(r))

from src.TAD.Polinomio import (Polinomio, coefLider, consPol, esPolCero, grado,

polCero, restoPol)

def integral(p: Polinomio[float]) -> Polinomio[float]:

if esPolCero(p):

return polCero()

n = grado(p)

b = coefLider(p)

r = restoPol(p)

return consPol(n + 1, b / (n + 1), integral(r))

1. Comprobación de raíces de polinomios

2. Derivada de un polinomio

3. Resta de polinomios

4. Potencia de un polinomio

5. Integral de un polinomio

Se puede imprimir o compartir con