{"id":8035,"date":"2023-04-17T06:00:26","date_gmt":"2023-04-17T04:00:26","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8035"},"modified":"2023-05-02T12:56:38","modified_gmt":"2023-05-02T10:56:38","slug":"17-abr-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/17-abr-23\/","title":{"rendered":"El tipo abstracto de datos de los polinomios"},"content":{"rendered":"<h3>1. El tipo abstracto de datos de los polinomios<\/h3>\n<p>Un polinomio es una expresi\u00f3n matem\u00e1tica compuesta por una suma de t\u00e9rminos, donde cada t\u00e9rmino es el producto de un coeficiente y una variable elevada a una potencia. Por ejemplo, el polinomio 3x^2+2x-1 tiene un t\u00e9rmino de segundo grado (3x^2), un t\u00e9rmino de primer grado (2x) y un t\u00e9rmino constante (-1).<\/p>\n<p>Las operaciones que definen al tipo abstracto de datos (TAD) de los polinomios (cuyos coeficientes son del tipo a) son las siguientes:<\/p>\n<pre lang=\"text\">\n   polCero   :: Polinomio a\n   esPolCero :: Polinomio a -> Bool\n   consPol   :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a\n   grado     :: Polinomio a -> Int\n   coefLider :: Num a => Polinomio a -> a\n   restoPol  :: (Num a, Eq a) => Polinomio a -> Polinomio a\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>polCero es el polinomio cero.<\/li>\n<li>(esPolCero p) se verifica si p es el polinomio cero.<\/li>\n<li>(consPol n b p) es el polinomio bx^n+p<\/li>\n<li>(grado p) es el grado del polinomio p.<\/li>\n<li>(coefLider p) es el coeficiente l\u00edder del polinomio p.<\/li>\n<li>(restoPol p) es el resto del polinomio p.<\/li>\n<\/ul>\n<p>Por ejemplo, el polinomio<\/p>\n<pre lang=\"text\">\n   3*x^4 + -5*x^2 + 3\n<\/pre>\n<p>se representa por<\/p>\n<pre lang=\"text\">\n   consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\n<\/pre>\n<p>Las operaciones tienen que verificar las siguientes propiedades:<\/p>\n<ul>\n<li>esPolCero polCero<\/li>\n<li>n > grado p &amp;&amp; b \/= 0 ==> not (esPolCero (consPol n b p))<\/li>\n<li>consPol (grado p) (coefLider p) (restoPol p) == p<\/li>\n<li>n > grado p &amp;&amp; b \/= 0 ==> grado (consPol n b p) == n<\/li>\n<li>n > grado p &amp;&amp; b \/= 0 ==> coefLider (consPol n b p) == b<\/li>\n<li>n > grado p &amp;&amp; b \/= 0 ==> restoPol (consPol n b p) == p<\/li>\n<\/ul>\n<h3>2. Los polinomios en Haskell<\/h3>\n<h4>2.1. El tipo abstracto de datos de los polinomios en Haskell<\/h4>\n<p>El TAD de los polinomios se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3MRpRth\">Polinomio.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\nmodule TAD.Polinomio\n  ( Polinomio,\n    polCero,   -- Polinomio a\n    esPolCero, -- Polinomio a -> Bool\n    consPol,   -- (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a\n    grado,     -- Polinomio a -> Int\n    coefLider, -- Num a => Polinomio a -> a\n    restoPol   -- (Num a, Eq a) => Polinomio a -> Polinomio a\n  ) where\n\nimport TAD.PolRepTDA\n-- import TAD.PolRepDensa\n-- import TAD.PolRepDispersa\n<\/pre>\n<p>Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio, consideraremos las siguientes:<\/p>\n<ul>\n<li>mediante tipo de dato algebraico,<\/li>\n<li>mediante listas densas y<\/li>\n<li>mediante listas dispersas.<\/li>\n<\/ul>\n<p>Hay que elegir la que se desee utilizar, descoment\u00e1ndola y comentando las otras.<\/p>\n<h4>2.2. Implementaci\u00f3n de los polinomios mediante tipos de datos algebraicos<\/h4>\n<p>Representamos un polinomio mediante los constructores ConsPol y<br \/>\nPolCero. Por ejemplo, el polinomio<\/p>\n<pre lang=\"text\">\n   6x^4 -5x^2 + 4x -7\n<\/pre>\n<p>se representa por<\/p>\n<pre lang=\"text\">\n   ConsPol 4 6 (ConsPol 2 (-5) (ConsPol 1 4 (ConsPol 0 (-7) PolCero)))\n<\/pre>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3zPN8Ec\">PolRepTDA.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\n{-# LANGUAGE TemplateHaskell #-}\n{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}\n\nmodule TAD.PolRepTDA\n  ( Polinomio,\n    polCero,   -- Polinomio a\n    esPolCero, -- Polinomio a -> Bool\n    consPol,   -- (Num a, Eq a)) => Int -> a -> Polinomio a -> Polinomio a\n    grado,     -- Polinomio a -> Int\n    coefLider, -- Num t => Polinomio t -> t\n    restoPol   -- Polinomio t -> Polinomio t\n  ) where\n\nimport Test.QuickCheck\n\n-- Polinomio como tipo de dato algebra\ndata Polinomio a = PolCero\n                 | ConsPol Int a (Polinomio a)\n  deriving Eq\n\n-- (escribePol p) es la cadena correspondiente al polinomio p. Por\n-- ejemplo,\n--    \u03bb> escribePol (consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)))\n--    \"3*x^4 + -5*x^2 + 3\"\nescribePol :: (Num a, Show a, Eq a) => Polinomio a -> String\nescribePol PolCero               = \"0\"\nescribePol (ConsPol 0 b PolCero) = show b\nescribePol (ConsPol 0 b p)       = concat [show b, \" + \", escribePol p]\nescribePol (ConsPol 1 b PolCero) = show b ++ \"*x\"\nescribePol (ConsPol 1 b p)       = concat [show b, \"*x + \", escribePol p]\nescribePol (ConsPol n 1 PolCero) = \"x^\" ++ show n\nescribePol (ConsPol n b PolCero) = concat [show b, \"*x^\", show n]\nescribePol (ConsPol n 1 p)       = concat [\"x^\", show n, \" + \", escribePol p]\nescribePol (ConsPol n b p)       = concat [show b, \"*x^\", show n, \" + \", escribePol p]\n\n-- Procedimiento de escritura de polinomios.\ninstance (Num a, Show a, Eq a) => Show (Polinomio a) where\n  show = escribePol\n\n-- Ejemplos de polinomios con coeficientes enteros:\nejPol1, ejPol2, ejPol3 :: Polinomio Int\nejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\nejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\nejPol3 = consPol 4 6 (consPol 1 2 polCero)\n\n-- Comprobaci\u00f3n de escritura:\n--    > ejPol1\n--    3*x^4 + -5*x^2 + 3\n--    > ejPol2\n--    x^5 + 5*x^2 + 4*x\n--    > ejPol3\n--    6*x^4 + 2*x\n\n-- polCero es el polinomio cero. Por ejemplo,\n--    > polCero\n--    0\npolCero :: Polinomio a\npolCero = PolCero\n\n-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,\n--    esPolCero polCero  ==  True\n--    esPolCero ejPol1   ==  False\nesPolCero :: Polinomio a -> Bool\nesPolCero PolCero = True\nesPolCero _       = False\n\n-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,\n--    ejPol2               ==  x^5 + 5*x^2 + 4*x\n--    consPol 3 0 ejPol2   ==  x^5 + 5*x^2 + 4*x\n--    consPol 3 2 polCero  ==  2*x^3\n--    consPol 6 7 ejPol2   ==  7*x^6 + x^5 + 5*x^2 + 4*x\n--    consPol 4 7 ejPol2   ==  x^5 + 7*x^4 + 5*x^2 + 4*x\n--    consPol 5 7 ejPol2   ==  8*x^5 + 5*x^2 + 4*x\nconsPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a\nconsPol _ 0 p = p\nconsPol n b PolCero = ConsPol n b PolCero\nconsPol n b (ConsPol m c p)\n  | n > m      = ConsPol n b (ConsPol m c p)\n  | n < m      = ConsPol m c (consPol n b p)\n  | b+c == 0   = p\n  | otherwise  = ConsPol n (b+c) p\n\n-- (grado p) es el grado del polinomio p. Por ejemplo,\n--    ejPol3        ==  6*x^4 + 2*x\n--    grado ejPol3  ==  4\ngrado :: Polinomio a -> Int\ngrado PolCero         = 0\ngrado (ConsPol n _ _) = n\n\n-- (coefLider p) es el coeficiente l\u00edder del polinomio p. Por ejemplo,\n--    ejPol3            ==  6*x^4 + 2*x\n--    coefLider ejPol3  ==  6\ncoefLider :: Num t => Polinomio t -> t\ncoefLider PolCero         = 0\ncoefLider (ConsPol _ b _) = b\n\n-- (restoPol p) es el resto del polinomio p. Por ejemplo,\n--    ejPol3           ==  6*x^4 + 2*x\n--    restoPol ejPol3  ==  2*x\n--    ejPol2           ==  x^5 + 5*x^2 + 4*x\n--    restoPol ejPol2  ==  5*x^2 + 4*x\nrestoPol :: Polinomio t -> Polinomio t\nrestoPol PolCero         = PolCero\nrestoPol (ConsPol _ _ p) = p\n\n-- Generador de polinomios                                          --\n-- =======================\n\n-- genPolinomio es un generador de polinomios. Por ejemplo,\n--    \u03bb> sample (genPol 1)\n--    7*x^9 + 9*x^8 + 10*x^7 + -14*x^5 + -15*x^2 + -10\n--    -4*x^8 + 2*x\n--    -8*x^9 + 4*x^8 + 2*x^6 + 4*x^5 + -6*x^4 + 5*x^2 + -8*x\n--    -9*x^9 + x^5 + -7\n--    8*x^10 + -9*x^7 + 7*x^6 + 9*x^5 + 10*x^3 + -1*x^2\n--    7*x^10 + 5*x^9 + -5\n--    -8*x^10 + -7\n--    -5*x\n--    5*x^10 + 4*x^4 + -3\n--    3*x^3 + -4\n--    10*x\ngenPol :: (Num a, Arbitrary a, Eq a) => Int -> Gen (Polinomio a)\ngenPol 0 = return polCero\ngenPol _ = do\n  n <- choose (0,10)\n  b <- arbitrary\n  p <- genPol (div n 2)\n  return (consPol n b p)\n\ninstance (Num a, Arbitrary a, Eq a) => Arbitrary (Polinomio a) where\n  arbitrary = sized genPol\n\n-- Propiedades de los polinomios\n-- =============================\n\n-- polCero es el polinomio cero.\nprop_polCero_es_cero :: Bool\nprop_polCero_es_cero =\n  esPolCero polCero\n\n-- Si n es mayor que el grado de p y b no es cero, entonces\n-- (consPol n b p) es un polinomio distinto del cero.\nprop_consPol_no_cero :: Int -> Int -> Polinomio Int -> Property\nprop_consPol_no_cero n b p =\n  n > grado p && b \/= 0  ==>\n  not (esPolCero (consPol n b p))\n\n-- (consPol (grado p) (coefLider p) (restoPol p)) es igual a p.\nprop_consPol :: Polinomio Int -> Bool\nprop_consPol p =\n  consPol (grado p) (coefLider p) (restoPol p) == p\n\n-- Si n es mayor que el grado de p y b no es cero, entonces\n-- el grado de (consPol n b p) es n.\nprop_grado :: Int -> Int -> Polinomio Int -> Property\nprop_grado n b p =\n  n > grado p && b \/= 0 ==>\n  grado (consPol n b p) == n\n\n-- Si n es mayor que el grado de p y b no es cero, entonces\n-- el coeficiente l\u00edder de (consPol n b p) es b.\nprop_coefLider :: Int -> Int -> Polinomio Int -> Property\nprop_coefLider n b p =\n  n > grado p && b \/= 0 ==>\n  coefLider (consPol n b p) == b\n\n-- Si n es mayor que el grado de p y b no es cero, entonces\n-- el resto de (consPol n b p) es p.\nprop_restoPol :: Int -> Int -> Polinomio Int -> Property\nprop_restoPol n b p =\n  n > grado p && b \/= 0 ==>\n  restoPol (consPol n b p) == p\n\n-- Verificaci\u00f3n\n-- ============\n\nreturn []\n\nverificaPol :: IO Bool\nverificaPol = $quickCheckAll\n\n-- La verificaci\u00f3n es\n--    \u03bb> verificaPol\n--    === prop_polCero_es_cero from PolPropiedades.hs:53 ===\n--    +++ OK, passed 1 test.\n--\n--    === prop_consPol_no_cero from PolPropiedades.hs:63 ===\n--    +++ OK, passed 100 tests; 251 discarded.\n--\n--    === prop_consPol from PolPropiedades.hs:73 ===\n--    +++ OK, passed 100 tests.\n--\n--    === prop_grado from PolPropiedades.hs:83 ===\n--    +++ OK, passed 100 tests; 321 discarded.\n--\n--    === prop_coefLider from PolPropiedades.hs:94 ===\n--    +++ OK, passed 100 tests; 340 discarded.\n--\n--    === prop_restoPol from PolPropiedades.hs:105 ===\n--    +++ OK, passed 100 tests; 268 discarded.\n--\n--    True\n<\/pre>\n<h4>2.3. Implementaci\u00f3n de polinomios mediante listas densas<\/h4>\n<p>Representaremos un polinomio por la lista de sus coeficientes ordenados en orden decreciente seg\u00fan el grado. Por ejemplo, el polinomio<\/p>\n<pre lang=\"text\">\n   6x^4 -5x^2 + 4x -7\n<\/pre>\n<p>se representa por<\/p>\n<pre lang=\"text\">\n   [6,0,-2,4,-7]\n<\/pre>\n<p>En la representaci\u00f3n se supone que, si la lista no es vac\u00eda, su primer elemento es distinto de cero.<\/p>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3GBR4Ml\">PolRepDensa.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\n{-# LANGUAGE TemplateHaskell #-}\n{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}\n\nmodule TAD.PolRepDensa\n  ( Polinomio,\n    polCero,   -- Polinomio a\n    esPolCero, -- Polinomio a -> Bool\n    consPol,   -- (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a\n    grado,     -- Polinomio a -> Int\n    coefLider, -- Num a => Polinomio a -> a\n    restoPol   -- (Num a, Eq a) => Polinomio a -> Polinomio a\n  ) where\n\nimport Test.QuickCheck\n\nnewtype Polinomio a = Pol [a]\n  deriving Eq\n\n-- (escribePol p) es la cadena correspondiente al polinomio p. Por\n-- ejemplo,\n--    \u03bb> escribePol (consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)))\n--    \"3*x^4 + -5*x^2 + 3\"\nescribePol :: (Num a, Show a, Eq a) => Polinomio a -> String\nescribePol pol\n  | esPolCero pol         = \"0\"\n  | n == 0 && esPolCero p = show a\n  | n == 0                = concat [show a, \" + \", escribePol p]\n  | n == 1 && esPolCero p = show a ++ \"*x\"\n  | n == 1                = concat [show a, \"*x + \", escribePol p]\n  | a == 1 && esPolCero p = \"x^\" ++ show n\n  | esPolCero p           = concat [show a, \"*x^\", show n]\n  | a == 1                = concat [\"x^\", show n, \" + \", escribePol p]\n  | otherwise             = concat [show a, \"*x^\", show n, \" + \", escribePol p]\n  where n = grado pol\n        a = coefLider pol\n        p = restoPol pol\n\n-- Procedimiento de escritura de polinomios.\ninstance (Num a, Show a, Eq a) => Show (Polinomio a) where\n  show = escribePol\n\n-- Ejemplos de polinomios con coeficientes enteros:\nejPol1, ejPol2, ejPol3 :: Polinomio Int\nejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\nejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\nejPol3 = consPol 4 6 (consPol 1 2 polCero)\n\n-- Comprobaci\u00f3n de escritura:\n--    > ejPol1\n--    3*x^4 + -5*x^2 + 3\n--    > ejPol2\n--    x^5 + 5*x^2 + 4*x\n--    > ejPol3\n--    6*x^4 + 2*x\n\n-- polCero es el polinomio cero. Por ejemplo,\n--    \u03bb> polCero\n--    0\npolCero :: Polinomio a\npolCero = Pol []\n\n-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,\n--    esPolCero polCero  ==  True\n--    esPolCero ejPol1   ==  False\nesPolCero :: Polinomio a -> Bool\nesPolCero (Pol []) = True\nesPolCero _        = False\n\n-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,\n--    ejPol2               ==  x^5 + 5*x^2 + 4*x\n--    consPol 3 0 ejPol2   ==  x^5 + 5*x^2 + 4*x\n--    consPol 3 2 polCero  ==  2*x^3\n--    consPol 6 7 ejPol2   ==  7*x^6 + x^5 + 5*x^2 + 4*x\n--    consPol 4 7 ejPol2   ==  x^5 + 7*x^4 + 5*x^2 + 4*x\n--    consPol 5 7 ejPol2   ==  8*x^5 + 5*x^2 + 4*x\nconsPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a\nconsPol _ 0 p = p\nconsPol n b p@(Pol xs)\n    | esPolCero p = Pol (b : replicate n 0)\n    | n > m       = Pol (b : replicate (n-m-1) 0 ++ xs)\n    | n < m       = consPol m c (consPol n b (restoPol p))\n    | b+c == 0    = Pol (dropWhile (==0) (tail xs))\n    | otherwise   = Pol ((b+c):tail xs)\n    where\n      c = coefLider p\n      m = grado p\n\n-- (grado p) es el grado del polinomio p. Por ejemplo,\n--    ejPol3        ==  6*x^4 + 2*x\n--    grado ejPol3  ==  4\ngrado :: Polinomio a -> Int\ngrado (Pol []) = 0\ngrado (Pol xs) = length xs - 1\n\n-- (coefLider p) es el coeficiente l\u00edder del polinomio p. Por ejemplo,\n--    ejPol3            ==  6*x^4 + 2*x\n--    coefLider ejPol3  ==  6\ncoefLider :: Num t => Polinomio t -> t\ncoefLider (Pol [])    = 0\ncoefLider (Pol (a:_)) = a\n\n-- (restoPol p) es el resto del polinomio p. Por ejemplo,\n--    ejPol3           ==  6*x^4 + 2*x\n--    restoPol ejPol3  ==  2*x\n--    ejPol2           ==  x^5 + 5*x^2 + 4*x\n--    restoPol ejPol2  ==  5*x^2 + 4*x\nrestoPol :: (Num t, Eq t) => Polinomio t -> Polinomio t\nrestoPol (Pol [])     = polCero\nrestoPol (Pol [_])    = polCero\nrestoPol (Pol (_:b:as))\n  | b == 0    = Pol (dropWhile (==0) as)\n  | otherwise = Pol (b:as)\n\n-- Generador de polinomios\n-- =======================\n\n-- genPolinomio es un generador de polinomios. Por ejemplo,\n--    \u03bb> sample (genPol 1)\n--    7*x^9 + 9*x^8 + 10*x^7 + -14*x^5 + -15*x^2 + -10\n--    -4*x^8 + 2*x\n--    -8*x^9 + 4*x^8 + 2*x^6 + 4*x^5 + -6*x^4 + 5*x^2 + -8*x\n--    -9*x^9 + x^5 + -7\n--    8*x^10 + -9*x^7 + 7*x^6 + 9*x^5 + 10*x^3 + -1*x^2\n--    7*x^10 + 5*x^9 + -5\n--    -8*x^10 + -7\n--    -5*x\n--    5*x^10 + 4*x^4 + -3\n--    3*x^3 + -4\n--    10*x\ngenPol :: (Num a, Arbitrary a, Eq a) => Int -> Gen (Polinomio a)\ngenPol 0 = return polCero\ngenPol _ = do\n  n <- choose (0,10)\n  b <- arbitrary\n  p <- genPol (div n 2)\n  return (consPol n b p)\n\ninstance (Num a, Arbitrary a, Eq a) => Arbitrary (Polinomio a) where\n  arbitrary = sized genPol\n\n-- Propiedades de los polinomios\n-- =============================\n\n-- polCero es el polinomio cero.\nprop_polCero_es_cero :: Bool\nprop_polCero_es_cero =\n  esPolCero polCero\n\n-- Si n es mayor que el grado de p y b no es cero, entonces\n-- (consPol n b p) es un polinomio distinto del cero.\nprop_consPol_no_cero :: Int -> Int -> Polinomio Int -> Property\nprop_consPol_no_cero n b p =\n  n > grado p && b \/= 0  ==>\n  not (esPolCero (consPol n b p))\n\n-- (consPol (grado p) (coefLider p) (restoPol p)) es igual a p.\nprop_consPol :: Polinomio Int -> Bool\nprop_consPol p =\n  consPol (grado p) (coefLider p) (restoPol p) == p\n\n-- Si n es mayor que el grado de p y b no es cero, entonces\n-- el grado de (consPol n b p) es n.\nprop_grado :: Int -> Int -> Polinomio Int -> Property\nprop_grado n b p =\n  n > grado p && b \/= 0 ==>\n  grado (consPol n b p) == n\n\n-- Si n es mayor que el grado de p y b no es cero, entonces\n-- el coeficiente l\u00edder de (consPol n b p) es b.\nprop_coefLider :: Int -> Int -> Polinomio Int -> Property\nprop_coefLider n b p =\n  n > grado p && b \/= 0 ==>\n  coefLider (consPol n b p) == b\n\n-- Si n es mayor que el grado de p y b no es cero, entonces\n-- el resto de (consPol n b p) es p.\nprop_restoPol :: Int -> Int -> Polinomio Int -> Property\nprop_restoPol n b p =\n  n > grado p && b \/= 0 ==>\n  restoPol (consPol n b p) == p\n\n-- Verificaci\u00f3n\n-- ============\n\nreturn []\n\nverificaPol :: IO Bool\nverificaPol = $quickCheckAll\n\n-- La verificaci\u00f3n es\n--    \u03bb> verificaPol\n--    === prop_polCero_es_cero from \/home\/jalonso\/alonso\/estudio\/Exercitium\/Exercitium\/src\/TAD\/PolRepDensa.hs:157 ===\n--    +++ OK, passed 1 test.\n--\n--    === prop_consPol_no_cero from \/home\/jalonso\/alonso\/estudio\/Exercitium\/Exercitium\/src\/TAD\/PolRepDensa.hs:163 ===\n--    +++ OK, passed 100 tests; 274 discarded.\n--\n--    === prop_consPol from \/home\/jalonso\/alonso\/estudio\/Exercitium\/Exercitium\/src\/TAD\/PolRepDensa.hs:169 ===\n--    +++ OK, passed 100 tests.\n--\n--    === prop_grado from \/home\/jalonso\/alonso\/estudio\/Exercitium\/Exercitium\/src\/TAD\/PolRepDensa.hs:175 ===\n--    +++ OK, passed 100 tests; 297 discarded.\n--\n--    === prop_coefLider from \/home\/jalonso\/alonso\/estudio\/Exercitium\/Exercitium\/src\/TAD\/PolRepDensa.hs:182 ===\n--    +++ OK, passed 100 tests; 248 discarded.\n--\n--    === prop_restoPol from \/home\/jalonso\/alonso\/estudio\/Exercitium\/Exercitium\/src\/TAD\/PolRepDensa.hs:189 ===\n--    +++ OK, passed 100 tests; 322 discarded.\n--\n--    True\n<\/pre>\n<h4>2.4. Implementaci\u00f3n de polinomios mediante listas dispersas<\/h4>\n<p>Representaremos un polinomio mediante una lista de pares (grado,coef),<br \/>\nordenados en orden decreciente seg\u00fan el grado. Por ejemplo, el polinomio<\/p>\n<pre lang=\"text\">\n   6x^4 -5x^2 + 4x -7\n<\/pre>\n<p>se representa por<\/p>\n<pre lang=\"text\">\n   [(4,6),(2,-5),(1,4),(0,-7)]\n<\/pre>\n<p>En la representaci\u00f3n se supone que los primeros elementos de los pares forman una sucesi\u00f3n estrictamente decreciente y que los segundos elementos son distintos de cero.<\/p>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3ZUcwTz\">PolRepDispersa.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\n{-# LANGUAGE TemplateHaskell #-}\n{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}\n\nmodule TAD.PolRepDispersa\n  ( Polinomio,\n    polCero,   -- Polinomio a\n    esPolCero, -- Num a =>  Polinomio a -> Bool\n    consPol,   -- Num a => Int -> a -> Polinomio a -> Polinomio a\n    grado,     -- Polinomio a -> Int\n    coefLider, -- Num a => Polinomio a -> a\n    restoPol   -- Polinomio a -> Polinomio a\n  ) where\n\nimport Test.QuickCheck\n\nnewtype Polinomio a = Pol [(Int,a)]\n  deriving Eq\n\n-- (escribePol p) es la cadena correspondiente al polinomio p. Por\n-- ejemplo,\n--    \u03bb> escribePol (consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)))\n--    \"3*x^4 + -5*x^2 + 3\"\nescribePol :: (Num a, Show a, Eq a) => Polinomio a -> String\nescribePol pol\n  | esPolCero pol         = \"0\"\n  | n == 0 && esPolCero p = show a\n  | n == 0                = concat [show a, \" + \", escribePol p]\n  | n == 1 && esPolCero p = show a ++ \"*x\"\n  | n == 1                = concat [show a, \"*x + \", escribePol p]\n  | a == 1 && esPolCero p = \"x^\" ++ show n\n  | esPolCero p           = concat [show a, \"*x^\", show n]\n  | a == 1                = concat [\"x^\", show n, \" + \", escribePol p]\n  | otherwise             = concat [show a, \"*x^\", show n, \" + \", escribePol p]\n  where n = grado pol\n        a = coefLider pol\n        p = restoPol pol\n\n-- Procedimiento de escritura de polinomios.\ninstance (Num a, Show a, Eq a) => Show (Polinomio a) where\n  show = escribePol\n\n-- Ejemplos de polinomios con coeficientes enteros:\nejPol1, ejPol2, ejPol3 :: Polinomio Int\nejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\nejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\nejPol3 = consPol 4 6 (consPol 1 2 polCero)\n\n-- Comprobaci\u00f3n de escritura:\n--    > ejPol1\n--    3*x^4 + -5*x^2 + 3\n--    > ejPol2\n--    x^5 + 5*x^2 + 4*x\n--    > ejPol3\n--    6*x^4 + 2*x\n\n-- polCero es el polinomio cero. Por ejemplo,\n--    \u03bb> polCero\n--    0\npolCero :: Num a => Polinomio a\npolCero = Pol []\n\n-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,\n--    esPolCero polCero  ==  True\n--    esPolCero ejPol1   ==  False\nesPolCero :: Num a => Polinomio a -> Bool\nesPolCero (Pol []) = True\nesPolCero _        = False\n\n-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,\n--    ejPol2               ==  x^5 + 5*x^2 + 4*x\n--    consPol 3 0 ejPol2   ==  x^5 + 5*x^2 + 4*x\n--    consPol 3 2 polCero  ==  2*x^3\n--    consPol 6 7 ejPol2   ==  7*x^6 + x^5 + 5*x^2 + 4*x\n--    consPol 4 7 ejPol2   ==  x^5 + 7*x^4 + 5*x^2 + 4*x\n--    consPol 5 7 ejPol2   ==  8*x^5 + 5*x^2 + 4*x\nconsPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a\nconsPol _ 0 p = p\nconsPol n b p@(Pol xs)\n    | esPolCero p = Pol [(n,b)]\n    | n > m       = Pol ((n,b):xs)\n    | n < m       = consPol m c (consPol n b (Pol (tail xs)))\n    | b+c == 0    = Pol (tail xs)\n    | otherwise   = Pol ((n,b+c) : tail xs)\n    where\n      c = coefLider p\n      m = grado p\n\n-- (grado p) es el grado del polinomio p. Por ejemplo,\n--    ejPol3        ==  6*x^4 + 2*x\n--    grado ejPol3  ==  4\ngrado :: Polinomio a -> Int\ngrado (Pol [])        = 0\ngrado (Pol ((n,_):_)) = n\n\n-- (coefLider p) es el coeficiente l\u00edder del polinomio p. Por ejemplo,\n--    ejPol3            ==  6*x^4 + 2*x\n--    coefLider ejPol3  ==  6\ncoefLider :: Num t => Polinomio t -> t\ncoefLider (Pol [])        = 0\ncoefLider (Pol ((_,b):_)) = b\n\n-- (restoPol p) es el resto del polinomio p. Por ejemplo,\n--    ejPol3           ==  6*x^4 + 2*x\n--    restoPol ejPol3  ==  2*x\n--    ejPol2           ==  x^5 + 5*x^2 + 4*x\n--    restoPol ejPol2  ==  5*x^2 + 4*x\nrestoPol :: Num t => Polinomio t -> Polinomio t\nrestoPol (Pol [])     = polCero\nrestoPol (Pol [_])    = polCero\nrestoPol (Pol (_:xs)) = Pol xs\n\n-- Generador de polinomios                                          --\n-- =======================\n\n-- genPolinomio es un generador de polinomios. Por ejemplo,\n--    \u03bb> sample (genPol 1)\n--    7*x^9 + 9*x^8 + 10*x^7 + -14*x^5 + -15*x^2 + -10\n--    -4*x^8 + 2*x\n--    -8*x^9 + 4*x^8 + 2*x^6 + 4*x^5 + -6*x^4 + 5*x^2 + -8*x\n--    -9*x^9 + x^5 + -7\n--    8*x^10 + -9*x^7 + 7*x^6 + 9*x^5 + 10*x^3 + -1*x^2\n--    7*x^10 + 5*x^9 + -5\n--    -8*x^10 + -7\n--    -5*x\n--    5*x^10 + 4*x^4 + -3\n--    3*x^3 + -4\n--    10*x\ngenPol :: (Num a, Arbitrary a, Eq a) => Int -> Gen (Polinomio a)\ngenPol 0 = return polCero\ngenPol _ = do\n  n <- choose (0,10)\n  b <- arbitrary\n  p <- genPol (div n 2)\n  return (consPol n b p)\n\ninstance (Num a, Arbitrary a, Eq a) => Arbitrary (Polinomio a) where\n  arbitrary = sized genPol\n\n-- Propiedades de los polinomios\n-- =============================\n\n-- polCero es el polinomio cero.\nprop_polCero_es_cero :: Bool\nprop_polCero_es_cero =\n  esPolCero polCero\n\n-- Si n es mayor que el grado de p y b no es cero, entonces\n-- (consPol n b p) es un polinomio distinto del cero.\nprop_consPol_no_cero :: Int -> Int -> Polinomio Int -> Property\nprop_consPol_no_cero n b p =\n  n > grado p && b \/= 0  ==>\n  not (esPolCero (consPol n b p))\n\n-- (consPol (grado p) (coefLider p) (restoPol p)) es igual a p.\nprop_consPol :: Polinomio Int -> Bool\nprop_consPol p =\n  consPol (grado p) (coefLider p) (restoPol p) == p\n\n-- Si n es mayor que el grado de p y b no es cero, entonces\n-- el grado de (consPol n b p) es n.\nprop_grado :: Int -> Int -> Polinomio Int -> Property\nprop_grado n b p =\n  n > grado p && b \/= 0 ==>\n  grado (consPol n b p) == n\n\n-- Si n es mayor que el grado de p y b no es cero, entonces\n-- el coeficiente l\u00edder de (consPol n b p) es b.\nprop_coefLider :: Int -> Int -> Polinomio Int -> Property\nprop_coefLider n b p =\n  n > grado p && b \/= 0 ==>\n  coefLider (consPol n b p) == b\n\n-- Si n es mayor que el grado de p y b no es cero, entonces\n-- el resto de (consPol n b p) es p.\nprop_restoPol :: Int -> Int -> Polinomio Int -> Property\nprop_restoPol n b p =\n  n > grado p && b \/= 0 ==>\n  restoPol (consPol n b p) == p\n\n-- Verificaci\u00f3n\n-- ============\n\nreturn []\n\nverificaPol :: IO Bool\nverificaPol = $quickCheckAll\n\n-- La verificaci\u00f3n es\n--    \u03bb> verificaPol\n--    === prop_polCero_es_cero from \/home\/jalonso\/alonso\/estudio\/Exercitium\/Exercitium\/src\/TAD\/PolRepDispersa.hs:156 ===\n--    +++ OK, passed 1 test.\n--\n--    === prop_consPol_no_cero from \/home\/jalonso\/alonso\/estudio\/Exercitium\/Exercitium\/src\/TAD\/PolRepDispersa.hs:162 ===\n--    +++ OK, passed 100 tests; 264 discarded.\n--\n--    === prop_consPol from \/home\/jalonso\/alonso\/estudio\/Exercitium\/Exercitium\/src\/TAD\/PolRepDispersa.hs:168 ===\n--    +++ OK, passed 100 tests.\n--\n--    === prop_grado from \/home\/jalonso\/alonso\/estudio\/Exercitium\/Exercitium\/src\/TAD\/PolRepDispersa.hs:174 ===\n--    +++ OK, passed 100 tests; 266 discarded.\n--\n--    === prop_coefLider from \/home\/jalonso\/alonso\/estudio\/Exercitium\/Exercitium\/src\/TAD\/PolRepDispersa.hs:181 ===\n--    +++ OK, passed 100 tests; 251 discarded.\n--\n--    === prop_restoPol from \/home\/jalonso\/alonso\/estudio\/Exercitium\/Exercitium\/src\/TAD\/PolRepDispersa.hs:188 ===\n--    +++ OK, passed 100 tests; 254 discarded.\n--\n--    True\n<\/pre>\n<h3>3. Los polinomios en Python<\/h3>\n<h4>3.1. El tipo abstracto de los polinomios en Python<\/h4>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3mmFu0R\">Polinomio.py<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"python\">\n__all__ = [\n    'Polinomio',\n    'polCero',\n    'esPolCero',\n    'consPol',\n    'grado',\n    'coefLider',\n    'restoPol',\n    'polinomioAleatorio'\n]\n\nfrom src.TAD.PolRepDensa import (Polinomio, coefLider, consPol, esPolCero,\n                                 grado, polCero, polinomioAleatorio, restoPol)\n\n# from src.TAD.PolRepDispersa import (Polinomio, polCero, esPolCero,\n#                                     consPol, grado, coefLider,\n#                                     restoPol, polinomioAleatorio)\n<\/pre>\n<p>Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio, consideraremos las siguientes:<\/p>\n<ul>\n<li>mediante listas densas y<\/li>\n<li>mediante listas dispersas.<\/li>\n<\/ul>\n<h4>3.2. Implementaci\u00f3n de los polinomios mediante listas densas<\/h4>\n<p>Representaremos un polinomio por la lista de sus coeficientes ordenados en orden decreciente seg\u00fan el grado. Por ejemplo, el polinomio<\/p>\n<pre lang=\"text\">\n   6x^4 -5x^2 + 4x -7\n<\/pre>\n<p>se representa por<\/p>\n<pre lang=\"text\">\n   [6,0,-2,4,-7]\n<\/pre>\n<p>En la representaci\u00f3n se supone que, si la lista no es vac\u00eda, su primer elemento es distinto de cero.<\/p>\n<p>Se define la clase Polinomio con los siguientes m\u00e9todos:<\/p>\n<ul>\n<li>esPolCero() se verifica si es el polinomio cero.<\/li>\n<li>consPol(n, b) es el polinomio obtenido a\u00f1adiendo el t\u00e9rmiono bx^n<\/li>\n<li>grado() es el grado del polinomio.<\/li>\n<li>coefLider() es el coeficiente l\u00edder del polinomio.<\/li>\n<li>restoPol() es el resto del polinomio.<\/li>\n<\/ul>\n<p>Por ejemplo,<\/p>\n<pre lang=\"text\">\n   >>> Polinomio()\n   0\n   >>> ejPol1 = Polinomio().consPol(0,3).consPol(2,-5).consPol(4,3)\n   >>> ejPol1\n   3*x^4 + -5*x^2 + 3\n   >>> ejPol2 = Polinomio().consPol(1,4).consPol(2,5).consPol(5,1)\n   >>> ejPol2\n   x^5 + 5*x^2 + 4*x\n   >>> ejPol3 = Polinomio().consPol(1,2).consPol(4,6)\n   >>> ejPol3\n   6*x^4 + 2*x\n   >>> Polinomio().esPolCero()\n   True\n   >>> ejPol1.esPolCero()\n   False\n   >>> ejPol2\n   x^5 + 5*x^2 + 4*x\n   >>> ejPol2.consPol(3,0)\n   x^5 + 5*x^2 + 4*x\n   >>> Polinomio().consPol(3,2)\n   2*x^3\n   >>> ejPol2.consPol(6,7)\n   7*x^6 + x^5 + 5*x^2 + 4*x\n   >>> ejPol2.consPol(4,7)\n   x^5 + 7*x^4 + 5*x^2 + 4*x\n   >>> ejPol2.consPol(5,7)\n   8*x^5 + 5*x^2 + 4*x\n   >>> ejPol3\n   6*x^4 + 2*x\n   >>> ejPol3.grado()\n   4\n   >>> ejPol3.restoPol()\n   2*x\n   >>> ejPol2\n   x^5 + 5*x^2 + 4*x\n   >>> ejPol2.restoPol()\n   5*x^2 + 4*x\n<\/pre>\n<p>Adem\u00e1s se definen las correspondientes funciones. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   >>> polCero()\n   0\n   >>> ejPol1a = consPol(4,3,consPol(2,-5,consPol(0,3,polCero())))\n   >>> ejPol1a\n   3*x^4 + -5*x^2 + 3\n   >>> ejPol2a = consPol(5,1,consPol(2,5,consPol(1,4,polCero())))\n   >>> ejPol2a\n   x^5 + 5*x^2 + 4*x\n   >>> ejPol3a = consPol(4,6,consPol(1,2,polCero()))\n   >>> ejPol3a\n   6*x^4 + 2*x\n   >>> esPolCero(polCero())\n   True\n   >>> esPolCero(ejPol1a)\n   False\n   >>> ejPol2a\n   x^5 + 5*x^2 + 4*x\n   >>> consPol(3,9,ejPol2a)\n   x^5 + 9*x^3 + 5*x^2 + 4*x\n   >>> consPol(3,2,polCero())\n   2*x^3\n   >>> consPol(6,7,ejPol2a)\n   7*x^6 + x^5 + 5*x^2 + 4*x\n   >>> consPol(4,7,ejPol2a)\n   x^5 + 7*x^4 + 5*x^2 + 4*x\n   >>> consPol(5,7,ejPol2a)\n   8*x^5 + 5*x^2 + 4*x\n   >>> ejPol3a\n   6*x^4 + 2*x\n   >>> grado(ejPol3a)\n   4\n   >>> restoPol(ejPol3a)\n   2*x\n   >>> ejPol2a\n   x^5 + 5*x^2 + 4*x\n   >>> restoPol(ejPol2a)\n   5*x^2 + 4*x\n<\/pre>\n<p>Finalmente, se define un generador aleatorio de polinomios y se comprueba que los polinomios cumplen las propiedades de su especificaci\u00f3n.<\/p>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"http:\/\/bit.ly\/3Kvz8Es\">PolRepDensa.py<\/a> en el que se define la clase Conj con los siguientes m\u00e9todos:<\/p>\n<pre lang=\"python\">\nfrom __future__ import annotations\n\n__all__ = [\n    'Polinomio',\n    'polCero',\n    'esPolCero',\n    'consPol',\n    'grado',\n    'coefLider',\n    'restoPol',\n    'polinomioAleatorio'\n]\n\nfrom dataclasses import dataclass, field\nfrom itertools import dropwhile\nfrom typing import Generic, TypeVar\n\nfrom hypothesis import assume, given\nfrom hypothesis import strategies as st\n\nA = TypeVar('A', int, float, complex)\n\n# Clase de los polinomios mediante listas densas\n# ==============================================\n\n@dataclass\nclass Polinomio(Generic[A]):\n    _coeficientes: list[A] = field(default_factory=list)\n\n    def esPolCero(self) -> bool:\n        return not self._coeficientes\n\n    def grado(self) -> int:\n        if self.esPolCero():\n            return 0\n        return len(self._coeficientes) - 1\n\n    def coefLider(self) -> A:\n        if self.esPolCero():\n            return 0\n        return self._coeficientes[0]\n\n    def restoPol(self) -> Polinomio[A]:\n        xs = self._coeficientes\n        if len(xs) <= 1:\n            return Polinomio([])\n        if xs[1] == 0:\n            return Polinomio(list(dropwhile(lambda x: x == 0, xs[2:])))\n        return Polinomio(xs[1:])\n\n    def consPol(self, n: int, b: A) -> Polinomio[A]:\n        m = self.grado()\n        c = self.coefLider()\n        xs = self._coeficientes\n        if b == 0:\n            return self\n        if self.esPolCero():\n            return Polinomio([b] + ([0] * n))\n        if n > m:\n            return Polinomio([b] + ([0] * (n-m-1)) + xs)\n        if n < m:\n            return self.restoPol().consPol(n, b).consPol(m, c)\n        if b + c == 0:\n            return Polinomio(list(dropwhile(lambda x: x == 0, xs[1:])))\n        return Polinomio([b + c] + xs[1:])\n\n    def __repr__(self) -> str:\n        n = self.grado()\n        a = self.coefLider()\n        p = self.restoPol()\n        if self.esPolCero():\n            return \"0\"\n        if n == 0 and p.esPolCero():\n            return str(a)\n        if n == 0:\n            return str(a) + \" + \" + str(p)\n        if n == 1 and p.esPolCero():\n            return str(a) + \"*x\"\n        if n == 1:\n            return str(a) + \"*x + \" + str(p)\n        if a == 1 and p.esPolCero():\n            return \"x^\" + str(n)\n        if p.esPolCero():\n            return str(a) + \"*x^\" + str(n)\n        if a == 1:\n            return \"x^\" + str(n) + \" + \" + str(p)\n        return str(a) + \"*x^\" + str(n) + \" + \" + str(p)\n\n# Funciones del tipo polinomio\n# ============================\n\ndef polCero() -> Polinomio[A]:\n    return Polinomio([])\n\ndef esPolCero(p: Polinomio[A]) -> bool:\n    return p.esPolCero()\n\ndef grado(p: Polinomio[A]) -> int:\n    return p.grado()\n\ndef coefLider(p: Polinomio[A]) -> A:\n    return p.coefLider()\n\ndef restoPol(p: Polinomio[A]) -> Polinomio[A]:\n    return p.restoPol()\n\ndef consPol(n: int, b: A, p: Polinomio[A]) -> Polinomio[A]:\n    return p.consPol(n, b)\n\n# Generador de polinomios\n# =======================\n\n# normal(xs) es la lista obtenida eliminando los ceros iniciales de\n# xs. Por ejmplo,\n#    >>> normal([0,0,5,0])\n#    [5, 0]\n#    >>> normal([0,0,0,0])\n#    []\ndef normal(xs: list[A]) -> list[A]:\n    return list(dropwhile(lambda x: x == 0, xs))\n\n# polinomioAleatorio() genera polinomios aleatorios. Por ejemplo,\n#    >>> polinomioAleatorio().example()\n#    9*x^6 + -7*x^5 + 7*x^3 + x^2 + 7\n#    >>> polinomioAleatorio().example()\n#    -3*x^7 + 8*x^6 + 2*x^5 + x^4 + -1*x^3 + -6*x^2 + 8*x + -6\n#    >>> polinomioAleatorio().example()\n#    x^2 + 7*x + -1\ndef polinomioAleatorio() -> st.SearchStrategy[Polinomio[int]]:\n    return st.lists(st.integers(min_value=-9, max_value=9), max_size=10)\\\n             .map(lambda xs: normal(xs))\\\n             .map(Polinomio)\n\n# Comprobaci\u00f3n de las propiedades de los polinomios\n# =================================================\n\n# Las propiedades son\ndef test_esPolCero1() -> None:\n    assert esPolCero(polCero())\n\n@given(p=polinomioAleatorio(),\n       n=st.integers(min_value=0, max_value=10),\n       b=st.integers())\ndef test_esPolCero2(p: Polinomio[int], n: int, b: int) -> None:\n    assume(n > grado(p) and b != 0)\n    assert not esPolCero(consPol(n, b, p))\n\n@given(p=polinomioAleatorio())\ndef test_consPol(p: Polinomio[int]) -> None:\n    assume(not esPolCero(p))\n    assert consPol(grado(p), coefLider(p), restoPol(p)) == p\n\n@given(p=polinomioAleatorio(),\n       n=st.integers(min_value=0, max_value=10),\n       b=st.integers())\ndef test_grado(p: Polinomio[int], n: int, b: int) -> None:\n    assume(n > grado(p) and b != 0)\n    assert grado(consPol(n, b, p)) == n\n\n@given(p=polinomioAleatorio(),\n       n=st.integers(min_value=0, max_value=10),\n       b=st.integers())\ndef test_coefLider(p: Polinomio[int], n: int, b: int) -> None:\n    assume(n > grado(p) and b != 0)\n    assert coefLider(consPol(n, b, p)) == b\n\n@given(p=polinomioAleatorio(),\n       n=st.integers(min_value=0, max_value=10),\n       b=st.integers())\ndef test_restoPol(p: Polinomio[int], n: int, b: int) -> None:\n    assume(n > grado(p) and b != 0)\n    assert restoPol(consPol(n, b, p)) == p\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -v PolRepDensa.py\n#\n#    PolRepDensa.py::test_esPolCero1 PASSED\n#    PolRepDensa.py::test_esPolCero2 PASSED\n#    PolRepDensa.py::test_consPol PASSED\n#    PolRepDensa.py::test_grado PASSED\n#    PolRepDensa.py::test_coefLider PASSED\n#    PolRepDensa.py::test_restoPol PASSED\n#\n#    === 6 passed in 1.64s ===\n<\/pre>\n<h4>3.3. Implementaci\u00f3n de los polinomios mediante listas dispersas<\/h4>\n<p>Representaremos un polinomio mediante una lista de pares (grado,coef), ordenados en orden decreciente seg\u00fan el grado. Por ejemplo, el polinomio<\/p>\n<pre lang=\"text\">\n   6x^4 -5x^2 + 4x -7\n<\/pre>\n<p>se representa por<\/p>\n<pre lang=\"text\">\n   [(4,6),(2,-5),(1,4),(0,-7)]\n<\/pre>\n<p>En la representaci\u00f3n se supone que los primeros elementos de los pares forman una sucesi\u00f3n estrictamente decreciente y que los segundos elementos son distintos de cero.<\/p>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3UrnU8l\">PolRepDispersa.py<\/a> cuyo contenido es<\/p>\n<pre lang=\"python\">\nfrom __future__ import annotations\n\n__all__ = [\n    'Polinomio',\n    'polCero',\n    'esPolCero',\n    'consPol',\n    'grado',\n    'coefLider',\n    'restoPol',\n    'polinomioAleatorio'\n]\n\nfrom dataclasses import dataclass, field\nfrom typing import Generic, TypeVar\n\nfrom hypothesis import assume, given\nfrom hypothesis import strategies as st\n\nA = TypeVar('A', int, float, complex)\n\n# Clase de los polinomios mediante listas densas\n# ==============================================\n\n@dataclass\nclass Polinomio(Generic[A]):\n    _terminos: list[tuple[int, A]] = field(default_factory=list)\n\n    def esPolCero(self) -> bool:\n        return not self._terminos\n\n    def grado(self) -> int:\n        if self.esPolCero():\n            return 0\n        return self._terminos[0][0]\n\n    def coefLider(self) -> A:\n        if self.esPolCero():\n            return 0\n        return self._terminos[0][1]\n\n    def restoPol(self) -> Polinomio[A]:\n        xs = self._terminos\n        if len(xs) <= 1:\n            return Polinomio([])\n        return Polinomio(xs[1:])\n\n    def consPol(self, n: int, b: A) -> Polinomio[A]:\n        m = self.grado()\n        c = self.coefLider()\n        xs = self._terminos\n        if b == 0:\n            return self\n        if self.esPolCero():\n            return Polinomio([(n, b)])\n        if n > m:\n            return Polinomio([(n, b)] + xs)\n        if n < m:\n            return Polinomio(xs[1:]).consPol(n, b).consPol(m, c)\n        if b + c == 0:\n            return Polinomio(xs[1:])\n        return Polinomio([(n, b + c)] + xs[1:])\n\n    def __repr__(self) -> str:\n        n = self.grado()\n        a = self.coefLider()\n        p = self.restoPol()\n        if self.esPolCero():\n            return \"0\"\n        if n == 0 and p.esPolCero():\n            return str(a)\n        if n == 0:\n            return str(a) + \" + \" + str(p)\n        if n == 1 and p.esPolCero():\n            return str(a) + \"*x\"\n        if n == 1:\n            return str(a) + \"*x + \" + str(p)\n        if a == 1 and p.esPolCero():\n            return \"x^\" + str(n)\n        if p.esPolCero():\n            return str(a) + \"*x^\" + str(n)\n        if a == 1:\n            return \"x^\" + str(n) + \" + \" + str(p)\n        return str(a) + \"*x^\" + str(n) + \" + \" + str(p)\n\n# Funciones del tipo polinomio\n# ============================\n\ndef polCero() -> Polinomio[A]:\n    return Polinomio([])\n\ndef esPolCero(p: Polinomio[A]) -> bool:\n    return p.esPolCero()\n\ndef grado(p: Polinomio[A]) -> int:\n    return p.grado()\n\ndef coefLider(p: Polinomio[A]) -> A:\n    return p.coefLider()\n\ndef restoPol(p: Polinomio[A]) -> Polinomio[A]:\n    return p.restoPol()\n\ndef consPol(n: int, b: A, p: Polinomio[A]) -> Polinomio[A]:\n    return p.consPol(n, b)\n\n# Generador de polinomios\n# =======================\n\n# normal(ps) es la representaci\u00f3n dispersa de un polinomio.\ndef normal(ps: list[tuple[int, A]]) -> list[tuple[int, A]]:\n    xs = sorted(list({p[0] for p in ps}), reverse=True)\n    ys = [p[1] for p in ps]\n    return [(x, y) for (x, y) in zip(xs, ys) if y != 0]\n\n# polinomioAleatorio() genera polinomios aleatorios. Por ejemplo,\n#    >>> polinomioAleatorio().example()\n#    -4*x^8 + -5*x^7 + -4*x^6 + -4*x^5 + -8*x^3\n#    >>> polinomioAleatorio().example()\n#    -7*x^9 + -8*x^6 + -8*x^3 + 2*x^2 + -1*x + 4\ndef polinomioAleatorio() -> st.SearchStrategy[Polinomio[int]]:\n    return st.lists(st.tuples(st.integers(min_value=0, max_value=9),\n                              st.integers(min_value=-9, max_value=9)))\\\n             .map(lambda ps: normal(ps))\\\n             .map(Polinomio)\n\n# Comprobaci\u00f3n de las propiedades de los polinomios\n# =================================================\n\n# Las propiedades son\ndef test_esPolCero1() -> None:\n    assert esPolCero(polCero())\n\n@given(p=polinomioAleatorio(),\n       n=st.integers(min_value=0, max_value=10),\n       b=st.integers())\ndef test_esPolCero2(p: Polinomio[int], n: int, b: int) -> None:\n    assume(n > grado(p) and b != 0)\n    assert not esPolCero(consPol(n, b, p))\n\n@given(p=polinomioAleatorio())\ndef test_consPol(p: Polinomio[int]) -> None:\n    assume(not esPolCero(p))\n    assert consPol(grado(p), coefLider(p), restoPol(p)) == p\n\n@given(p=polinomioAleatorio(),\n       n=st.integers(min_value=0, max_value=10),\n       b=st.integers())\ndef test_grado(p: Polinomio[int], n: int, b: int) -> None:\n    assume(n > grado(p) and b != 0)\n    assert grado(consPol(n, b, p)) == n\n\n@given(p=polinomioAleatorio(),\n       n=st.integers(min_value=0, max_value=10),\n       b=st.integers())\ndef test_coefLider(p: Polinomio[int], n: int, b: int) -> None:\n    assume(n > grado(p) and b != 0)\n    assert coefLider(consPol(n, b, p)) == b\n\n@given(p=polinomioAleatorio(),\n       n=st.integers(min_value=0, max_value=10),\n       b=st.integers())\ndef test_restoPol(p: Polinomio[int], n: int, b: int) -> None:\n    assume(n > grado(p) and b != 0)\n    assert restoPol(consPol(n, b, p)) == p\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -v PolRepDispersa.py\n#\n#    PolRepDispersa.py::test_esPolCero1 PASSED\n#    PolRepDispersa.py::test_esPolCero2 PASSED\n#    PolRepDispersa.py::test_consPol PASSED\n#    PolRepDispersa.py::test_grado PASSED\n#    PolRepDispersa.py::test_coefLider PASSED\n#    PolRepDispersa.py::test_restoPol PASSED\n#\n#    === 6 passed in 1.74s ===\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>1. El tipo abstracto de datos de los polinomios Un polinomio es una expresi\u00f3n matem\u00e1tica compuesta por una suma de t\u00e9rminos, donde cada t\u00e9rmino es el producto de un coeficiente y una variable elevada a una potencia. Por ejemplo, el polinomio 3x^2+2x-1 tiene un t\u00e9rmino de segundo grado (3x^2), un t\u00e9rmino de primer grado (2x)&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","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":[581],"tags":[265],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8035"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=8035"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8035\/revisions"}],"predecessor-version":[{"id":8116,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8035\/revisions\/8116"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8035"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8035"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8035"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}