{"id":7937,"date":"2023-05-20T08:26:34","date_gmt":"2023-05-20T06:26:34","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7937"},"modified":"2023-05-20T08:26:34","modified_gmt":"2023-05-20T06:26:34","slug":"20-may-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/20-may-23\/","title":{"rendered":"La semana en Exercitium (20 de mayo de 2023)"},"content":{"rendered":"<p>Esta semana he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas sibre el <a href=\"https:\/\/bit.ly\/3KwqXYu\">tipo abstracto de datos de los polinomios<\/a><\/p>\n<ul>\n<li><a href=\"#ej1\">1. T\u00e9rmino independiente de un polinomio<\/a><\/li>\n<li><a href=\"#ej2\">2. Regla de Ruffini con representaci\u00f3n densa<\/a><\/li>\n<li><a href=\"#ej3\">3. Regla de Ruffini<\/a><\/li>\n<li><a href=\"#ej4\">4. Reconocimiento de ra\u00edces por la regla de Ruffini<\/a><\/li>\n<li><a href=\"#ej5\">5. Ra\u00edces enteras de un polinomio<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. T\u00e9rmino independiente de un polinomio<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3KwqXYu\">tipo abstracto de datos de los polinomios<\/a> definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   terminoIndep :: (Num a, Eq a) => Polinomio  a -> a\n<\/pre>\n<p>tal que <code>terminoIndep p<\/code> es el t\u00e9rmino independiente del polinomio <code>p<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> ejPol1 = consPol 4 3 (consPol 2 5 (consPol 0 3 polCero))\n   \u03bb> ejPol1\n   3*x^4 + 5*x^2 + 3\n   \u03bb> terminoIndep ejPol1\n   3\n   \u03bb> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\n   \u03bb> ejPol2\n   x^5 + 5*x^2 + 4*x\n   \u03bb> terminoIndep ejPol2\n   0\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport TAD.Polinomio (Polinomio, consPol, polCero)\nimport Pol_Coeficiente (coeficiente)\n\nterminoIndep :: (Num a, Eq a) => Polinomio  a -> a\nterminoIndep = coeficiente 0\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import TypeVar\n\nfrom src.Pol_Coeficiente import coeficiente\nfrom src.TAD.Polinomio import Polinomio, consPol, polCero\n\nA = TypeVar('A', int, float, complex)\n\ndef terminoIndep(p: Polinomio[A]) -> A:\n    return coeficiente(0, p)\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Regla de Ruffini con representaci\u00f3n densa<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3KwqXYu\">tipo abstracto de los polinomios<\/a> definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   ruffiniDensa :: Int -> [Int] -> [Int]\n<\/pre>\n<p>tal que <code>ruffiniDensa r cs<\/code> es la lista de los coeficientes del cociente junto con el rsto que resulta de aplicar la regla de Ruffini para dividir el polinomio cuya representaci\u00f3n densa es <code>cs<\/code> entre <code>x-r<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   ruffiniDensa 2 [1,2,-1,-2] == [1,4,7,12]\n   ruffiniDensa 1 [1,2,-1,-2] == [1,3,2,0]\n<\/pre>\n<p>ya que<\/p>\n<pre lang=\"text\">\n     | 1  2  -1  -2           | 1  2  -1  -2\n   2 |    2   8  14         1 |    1   3   2\n   --+--------------        --+-------------\n     | 1  4   7  12           | 1  3   2   0\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nruffiniDensa :: Int -> [Int] -> [Int]\nruffiniDensa _ [] = []\nruffiniDensa r p@(c:cs) =\n  c : [x+r*y | (x,y) <- zip cs (ruffiniDensa r p)]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nruffiniDensa2 :: Int -> [Int] -> [Int]\nruffiniDensa2 r =\n  scanl1 (\\s x -> s * r + x)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_ruffiniDensa :: Int -> [Int] -> Bool\nprop_ruffiniDensa r cs =\n  ruffiniDensa r cs == ruffiniDensa2 r cs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_ruffiniDensa\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\ndef ruffiniDensa(r: int, p: list[int]) -> list[int]:\n    if not p:\n        return []\n    res = [p[0]]\n    for x in p[1:]:\n        res.append(x + r * res[-1])\n    return res\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Regla de Ruffini<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3KwqXYu\">tipo abstracto de los polinomios<\/a>, definir las funciones<\/p>\n<pre lang=\"text\">\n   cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int\n   restoRuffini    :: Int -> Polinomio Int -> Int\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>cocienteRuffini r p<\/code> es el cociente de dividir el polinomio <code>p<\/code> por el polinomio <code>x-r<\/code>. Por ejemplo:<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> ejPol = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))\n     \u03bb> ejPol\n     x^3 + 2*x^2 + -1*x + -2\n     \u03bb> cocienteRuffini 2 ejPol\n     x^2 + 4*x + 7\n     \u03bb> cocienteRuffini (-2) ejPol\n     x^2 + -1\n     \u03bb> cocienteRuffini 3 ejPol\n     x^2 + 5*x + 14\n<\/pre>\n<ul>\n<li><code>restoRuffini r p<\/code> es el resto de dividir el polinomio <code>p<\/code> por el polinomio <code>x-r<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> restoRuffini 2 ejPol\n     12\n     \u03bb> restoRuffini (-2) ejPol\n     0\n     \u03bb> restoRuffini 3 ejPol\n     40\n<\/pre>\n<p>Comprobar con QuickCheck que, dado un polinomio p y un n\u00famero entero r, las funciones anteriores verifican la propiedad de la divisi\u00f3n eucl\u00eddea.<\/p>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport TAD.Polinomio (Polinomio, consPol, polCero)\nimport Pol_Transformaciones_polinomios_densas (densaApolinomio,\n                                               polinomioAdensa)\nimport Pol_Division_de_Ruffini_con_representacion_densa (ruffiniDensa)\nimport Pol_Producto_polinomios (multPol)\nimport Pol_Suma_de_polinomios (sumaPol)\nimport Pol_Crea_termino (creaTermino)\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n de cocienteRuffini\n-- ================================\n\ncocienteRuffini :: Int -> Polinomio Int -> Polinomio Int\ncocienteRuffini r p = densaApolinomio (init (ruffiniDensa r (polinomioAdensa p)))\n\n-- 2\u00aa definici\u00f3n de cocienteRuffini\n-- ================================\n\ncocienteRuffini2 :: Int -> Polinomio Int -> Polinomio Int\ncocienteRuffini2 r = densaApolinomio . ruffiniDensa r . init . polinomioAdensa\n\n-- 1\u00aa definici\u00f3n de restoRuffini\n-- =============================\n\nrestoRuffini :: Int -> Polinomio Int -> Int\nrestoRuffini r p = last (ruffiniDensa r (polinomioAdensa p))\n\n-- 2\u00aa definici\u00f3n de restoRuffini\n-- =============================\n\nrestoRuffini2 :: Int -> Polinomio Int -> Int\nrestoRuffini2 r = last . ruffiniDensa r . polinomioAdensa\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_diviEuclidea :: Int -> Polinomio Int -> Bool\nprop_diviEuclidea r p =\n  p == sumaPol (multPol coci divi) rest\n  where coci = cocienteRuffini r p\n        divi = densaApolinomio [1,-r]\n        rest = creaTermino 0 (restoRuffini r p)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_diviEuclidea\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.Pol_Crea_termino import creaTermino\nfrom src.Pol_Division_de_Ruffini_con_representacion_densa import ruffiniDensa\nfrom src.Pol_Producto_polinomios import multPol\nfrom src.Pol_Suma_de_polinomios import sumaPol\nfrom src.Pol_Transformaciones_polinomios_densas import (densaApolinomio,\n                                                        polinomioAdensa)\nfrom src.TAD.Polinomio import (Polinomio, consPol, esPolCero, polCero,\n                               polinomioAleatorio)\n\n\ndef cocienteRuffini(r: int, p: Polinomio[int]) -> Polinomio[int]:\n    if esPolCero(p):\n        return polCero()\n    return densaApolinomio(ruffiniDensa(r, polinomioAdensa(p))[:-1])\n\ndef restoRuffini(r: int, p: Polinomio[int]) -> int:\n    if esPolCero(p):\n        return 0\n    return ruffiniDensa(r, polinomioAdensa(p))[-1]\n\n# Comprobaci\u00f3n de la propiedad\n# ============================\n\n# La propiedad es\n@given(r=st.integers(), p=polinomioAleatorio())\ndef test_diviEuclidea (r: int, p: Polinomio[int]) -> None:\n    coci = cocienteRuffini(r, p)\n    divi = densaApolinomio([1, -r])\n    rest = creaTermino(0, restoRuffini(r, p))\n    assert p == sumaPol(multPol(coci, divi), rest)\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q Pol_Regla_de_Ruffini.py\n#    1 passed in 0.32s\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Reconocimiento de ra\u00edces por la regla de Ruffini<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3KwqXYu\">tipo abstracto de los polinomios<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   esRaizRuffini :: Int -> Polinomio Int -> Bool\n<\/pre>\n<p>tal que <code>esRaizRuffini r p<\/code> se verifica si <code>r<\/code> es una raiz de <code>p<\/code>, usando para ello el regla de Ruffini. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> ejPol = consPol 4 6 (consPol 1 2 polCero)\n   \u03bb> ejPol\n   6*x^4 + 2*x\n   \u03bb> esRaizRuffini 0 ejPol\n   True\n   \u03bb> esRaizRuffini 1 ejPol\n   False\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini where\n\nimport TAD.Polinomio (Polinomio, consPol, polCero)\nimport Pol_Regla_de_Ruffini (restoRuffini)\n\nesRaizRuffini :: Int -> Polinomio Int -> Bool\nesRaizRuffini r p = restoRuffini r p == 0\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom src.Pol_Regla_de_Ruffini import restoRuffini\nfrom src.TAD.Polinomio import Polinomio, consPol, polCero\n\n\ndef esRaizRuffini(r: int, p: Polinomio[int]) -> bool:\n    return restoRuffini(r, p) == 0\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Ra\u00edces enteras de un polinomio<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3KwqXYu\">tipo abstracto de los polinomios<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n    raicesRuffini :: Polinomio Int -> [Int]\n<\/pre>\n<p>tal que <code>raicesRuffini p<\/code> es la lista de las raices enteras de <code>p<\/code>, calculadas usando el regla de Ruffini. Por ejemplo,<\/p>\n<pre lang=\"text\">\n    \u03bb> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\n    \u03bb> ejPol1\n    3*x^4 + -5*x^2 + 3\n    \u03bb> raicesRuffini ejPol1\n    []\n    \u03bb> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\n    \u03bb> ejPol2\n    x^5 + 5*x^2 + 4*x\n    \u03bb> raicesRuffini ejPol2\n    [0,-1]\n    \u03bb> ejPol3 = consPol 4 6 (consPol 1 2 polCero)\n    \u03bb> ejPol3\n    6*x^4 + 2*x\n    \u03bb> raicesRuffini ejPol3\n    [0]\n    \u03bb> ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))\n    \u03bb> ejPol4\n    x^3 + 2*x^2 + -1*x + -2\n    \u03bb> raicesRuffini ejPol4\n    [1,-1,-2]\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport TAD.Polinomio (Polinomio, consPol, polCero, esPolCero)\nimport Pol_Termino_independiente_de_un_polinomio (terminoIndep)\nimport Pol_Regla_de_Ruffini (cocienteRuffini)\nimport Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini (esRaizRuffini)\n\nraicesRuffini :: Polinomio Int -> [Int]\nraicesRuffini p\n  | esPolCero p = []\n  | otherwise   = aux (0 : divisores (terminoIndep p))\n  where aux [] = []\n        aux (r:rs)\n          | esRaizRuffini r p = r : raicesRuffini (cocienteRuffini r p)\n          | otherwise         = aux rs\n\n-- (divisores n) es la lista de todos los divisores enteros de n. Por\n-- ejemplo,\n--    divisores 4     ==  [1,-1,2,-2,4,-4]\n--    divisores (-6)  ==  [1,-1,2,-2,3,-3,6,-6]\ndivisores :: Int -> [Int]\ndivisores n = concat [[x,-x] | x <- [1..abs n], rem n x == 0]\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom src.Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini import \\\n    esRaizRuffini\nfrom src.Pol_Regla_de_Ruffini import cocienteRuffini\nfrom src.Pol_Termino_independiente_de_un_polinomio import terminoIndep\nfrom src.TAD.Polinomio import Polinomio, consPol, esPolCero, polCero\n\n\n# (divisores n) es la lista de todos los divisores enteros de n. Por\n# ejemplo,\n#    divisores(4)  == [1, 2, 4, -1, -2, -4]\n#    divisores(-6) == [1, 2, 3, 6, -1, -2, -3, -6]\ndef divisores(n: int) -> list[int]:\n    xs = [x for x in range(1, abs(n)+1) if n % x == 0]\n    return xs + [-x for x in xs]\n\ndef raicesRuffini(p: Polinomio[int]) -> list[int]:\n    if esPolCero(p):\n        return []\n    def aux(rs: list[int]) -> list[int]:\n        if not rs:\n            return []\n        x, *xs = rs\n        if esRaizRuffini(x, p):\n            return [x] + raicesRuffini(cocienteRuffini(x, p))\n        return aux(xs)\n\n    return aux([0] + divisores(terminoIndep(p)))\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas sibre el tipo abstracto de datos de los polinomios 1. T\u00e9rmino independiente de un polinomio 2. Regla de Ruffini con representaci\u00f3n densa 3. Regla de Ruffini 4. Reconocimiento de ra\u00edces por la regla de Ruffini 5. Ra\u00edces enteras de un polinomio A continuaci\u00f3n&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[337],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7937"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=7937"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7937\/revisions"}],"predecessor-version":[{"id":7938,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7937\/revisions\/7938"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7937"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7937"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7937"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}