Menu Close

La semana en Exercitium (6 de mayo de 2023)

José A. Alonso

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

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

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

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


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

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

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

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.


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

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

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

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)


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

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

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

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)


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

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

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

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


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))
Posted in PFH