{"id":3302,"date":"2013-05-02T14:24:32","date_gmt":"2013-05-02T14:24:32","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3302"},"modified":"2013-05-05T04:25:05","modified_gmt":"2013-05-05T04:25:05","slug":"i1m2012-division-y-factorizacion-de-polinomios-mediante-la-regla-de-ruffini-en-haskell-2","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-division-y-factorizacion-de-polinomios-mediante-la-regla-de-ruffini-en-haskell-2\/","title":{"rendered":"I1M2012: Divisi\u00f3n y factorizaci\u00f3n de polinomios mediante la regla de Ruffini en Haskell (2)"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones de los ejercicios de la relaci\u00f3n 25. El objetivo de la relaci\u00f3n es implementar la regla de Ruffini y sus aplicaciones utilizando las implementaciones del TAD de polinomio estudiadas en el <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\/temas\/temas-21.pdf\">tema 21<\/a>.<\/p>\n<p>En los ejercicios se usan las siguientes librer\u00edas:<\/p>\n<ul>\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\/codigos\/PolRepTDA.hs\">PolRepTDA<\/a>: Implementaci\u00f3n de los polinomios mediante tipos de datos algebraicos.\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\/codigos\/PolRepDispersa.hs\">PolRepDispersa<\/a>: Implementaci\u00f3n de los polinomios mediante listas dispersas.\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\/codigos\/PolRepDensa.hs\">PolRepDensa<\/a>: Implementaci\u00f3n de los polinomios mediante listas densas.\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\/codigos\/PolOperaciones.hs\">PolOperaciones<\/a>: Operaciones con el TAD de los polinomios.\n<\/ul>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas                                           --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport PolOperaciones\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejemplos                                                           --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Adem\u00e1s de los ejemplos de polinomios (ejPol1, ejPol2 y ejPol3) que se\r\n-- encuentran en PolOperaciones, usaremos el siguiente ejemplo.\r\nejPol4 :: Polinomio Int\r\nejPol4 = consPol 3 1 \r\n                 (consPol 2 2 \r\n                          (consPol 1 (-1) \r\n                                   (consPol 0 (-2) polCero)))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--    divisores :: Int -> [Int]\r\n-- tal que (divisores n) es la lista de todos los divisores enteros de\r\n-- n. Por ejemplo,\r\n--    divisores 4     ==  [1,-1,2,-2,4,-4]\r\n--    divisores (-6)  ==  [1,-1,2,-2,3,-3,6,-6]\r\n-- ---------------------------------------------------------------------\r\n\r\ndivisores :: Int -> [Int]\r\ndivisores n = concat [[x,-x] | x <- [1..abs n], rem n x == 0]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    coeficiente :: Num a => Int -> Polinomio a -> a\r\n-- tal que (coeficiente k p) es el coeficiente del t\u00e9rmino de grado k en\r\n-- p. Por ejemplo:\r\n--     coeficiente 4 ejPol1 == 3\r\n--     coeficiente 3 ejPol1 == 0\r\n--     coeficiente 2 ejPol1 == -5\r\n--     coeficiente 5 ejPol1 == 0\r\n-- ---------------------------------------------------------------------\r\n\r\ncoeficiente :: Num a => Int -> Polinomio a -> a\r\ncoeficiente k p | k == gp      = coefLider p\r\n                | k > grado rp = 0\r\n                | otherwise    = coeficiente k rp\r\n                where gp = grado p\r\n                      rp = restoPol p\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n \r\n--    terminoIndep :: Num a => Polinomio  a -> a\r\n-- tal que (terminoIndep p) es el t\u00e9rmino independiente del polinomio\r\n-- p. Por ejemplo,\r\n--    terminoIndep ejPol1 == 3\r\n--    terminoIndep ejPol2 == 0\r\n--    terminoIndep ejPol4 == -2\r\n-- ---------------------------------------------------------------------\r\n\r\nterminoIndep :: Num a => Polinomio  a -> a\r\nterminoIndep p = coeficiente 0 p\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n \r\n--    coeficientes :: Num a => Polinomio a -> [a]\r\n-- tal que (coeficientes p) es la lista de coeficientes de p, ordenada\r\n-- seg\u00fan el grado. Por ejemplo,\r\n--     coeficientes ejPol1 == [3,0,-5,0,3]\r\n--     coeficientes ejPol4 == [1,2,-1,-2]\r\n--     coeficientes ejPol2 == [1,0,0,5,4,0]\r\n-- ---------------------------------------------------------------------\r\n\r\ncoeficientes :: Num a => Polinomio a -> [a]\r\ncoeficientes p = [coeficiente k p | k <- [n,n-1..0]]\r\n    where n = grado p\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n \r\n--    creaPol :: Num a => [a] -> Polinomio a\r\n-- tal que (creaPol cs) es el polinomio cuya lista de coeficientes es\r\n-- cs. Por ejemplo,\r\n--     creaPol [1,0,0,5,4,0] == x^5 + 5*x^2 + 4*x\r\n--     creaPol [1,2,0,3,0]   == x^4 + 2*x^3 + 3*x\r\n-- ---------------------------------------------------------------------\r\n\r\ncreaPol :: Num a => [a] -> Polinomio a\r\ncreaPol []     = polCero\r\ncreaPol (a:as) = consPol n a (creaPol as)\r\n    where n = length as\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Comprobar con QuickCheck que, dado un polinomio p, el\r\n-- polinomio obtenido mediante creaPol a partir de la lista de\r\n-- coeficientes de p coincide con p.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_coef:: Polinomio Int -> Bool\r\nprop_coef p =\r\n    creaPol (coeficientes p) == p\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_coef\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir una funci\u00f3n \r\n--    pRuffini:: Int -> [Int] -> [Int]\r\n-- tal que (pRuffini r cs) es la lista que resulta de aplicar un paso\r\n-- del regla de Ruffini al n\u00famero entero r y a la lista de coeficientes\r\n-- cs. Por ejemplo,\r\n--    pRuffini 2 [1,2,-1,-2] == [1,4,7,12]\r\n--    pRuffini 1 [1,2,-1,-2] == [1,3,2,0]\r\n-- ya que\r\n--      | 1  2  -1  -2           | 1  2  -1  -2\r\n--    2 |    2   8  14         1 |    1   3   2\r\n--    --+--------------        --+-------------\r\n--      | 1  4   7  12           | 1  3   2   0\r\n-- ---------------------------------------------------------------------\r\n\r\npRuffini :: Int -> [Int] -> [Int]\r\npRuffini r p@(c:cs) = \r\n    c : [x+r*y | (x,y) <- zip cs (pRuffini r p)]\r\n\r\n-- Otra forma:\r\npRuffini' :: Int -> [Int] -> [Int]\r\npRuffini' r = scanl1 (\\s x -> s * r + x)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir la funci\u00f3n \r\n--    cocienteRuffini:: Int -> Polinomio Int -> Polinomio Int\r\n-- tal que (cocienteRuffini r p) es el cociente de dividir el polinomio\r\n-- p por el polinomio x-r. Por ejemplo:\r\n--     cocienteRuffini 2 ejPol4    == x^2 + 4*x + 7\r\n--     cocienteRuffini (-2) ejPol4 == x^2 + -1\r\n--     cocienteRuffini 3 ejPol4    == x^2 + 5*x + 14\r\n-- ---------------------------------------------------------------------\r\n\r\ncocienteRuffini :: Int -> Polinomio Int -> Polinomio Int\r\ncocienteRuffini r p = creaPol (init (pRuffini r (coeficientes p)))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Definir la funci\u00f3n \r\n--    restoRuffini:: Int -> Polinomio Int -> Int\r\n-- tal que (restoRuffini r p) es el resto de dividir el polinomio p por\r\n-- el polinomio x-r. Por ejemplo, \r\n--     restoRuffini 2 ejPol4    == 12\r\n--     restoRuffini (-2) ejPol4 == 0\r\n--     restoRuffini 3 ejPol4    == 40\r\n-- ---------------------------------------------------------------------\r\n\r\nrestoRuffini :: Int -> Polinomio Int -> Int\r\nrestoRuffini r p = last (pRuffini r (coeficientes p))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Comprobar con QuickCheck que, dado un polinomio p y un\r\n-- n\u00famero entero r, las funciones anteriores verifican la propiedad de\r\n-- la divisi\u00f3n eucl\u00eddea.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_diviEuclidea:: Int -> Polinomio Int -> Bool\r\nprop_diviEuclidea r p =\r\n    p == sumaPol (multPol coc div) res\r\n    where coc = cocienteRuffini r p\r\n          div = creaPol [1,-r]\r\n          res = creaTermino 0 (restoRuffini r p) \r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_diviEuclidea\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Definir la funci\u00f3n\r\n--     esRaizRuffini:: Int -> Polinomio Int -> Bool \r\n-- tal que (esRaizRuffini r p) se verifica si r es una raiz de p, usando\r\n-- para ello el regla de Ruffini. Por ejemplo,\r\n--     esRaizRuffini 0 ejPol3 == True\r\n--     esRaizRuffini 1 ejPol3 == False\r\n-- ---------------------------------------------------------------------\r\n\r\nesRaizRuffini:: Int -> Polinomio Int -> Bool \r\nesRaizRuffini r p = restoRuffini r p == 0\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Definir la funci\u00f3n \r\n--     raicesRuffini :: Polinomio Int -> [Int]\r\n-- tal que (raicesRuffini p) es la lista de las raices enteras de p,\r\n-- calculadas usando el regla de Ruffini. Por ejemplo,\r\n--    raicesRuffini ejPol1  == []\r\n--    raicesRuffini ejPol2  == [0,-1]\r\n--    raicesRuffini ejPol3  == [0]\r\n--    raicesRuffini ejPol4  == [1,-1,-2]\r\n--    raicesRuffini polCero == []\r\n-- ---------------------------------------------------------------------\r\n\r\nraicesRuffini :: Polinomio Int -> [Int]\r\nraicesRuffini p     \r\n    | esPolCero p = []\r\n    | otherwise   = aux (0 : divisores (terminoIndep p))\r\n    where \r\n      aux [] = []\r\n      aux (r:rs) \r\n          | esRaizRuffini r p = r : raicesRuffini (cocienteRuffini r p) \r\n          | otherwise         = aux rs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Definir la funci\u00f3n\r\n--    factorizacion :: Polinomio Int -> [Polinomio Int]\r\n-- tal que (factorizacion p) es la lista de la descomposici\u00f3n del\r\n-- polinomio p en factores obtenida mediante el regla de Ruffini. Por\r\n-- ejemplo, \r\n--  ejPol2                               ==  x^5 + 5*x^2 + 4*x\r\n--  factorizacion ejPol2                 == [1*x,1*x+1,x^3+-1*x^2+1*x+4]\r\n--  ejPol4                               == x^3 + 2*x^2 + -1*x + -2\r\n--  factorizacion ejPol4                 == [1*x + -1,1*x + 1,1*x + 2,1]\r\n--  factorizacion (creaPol [1,0,0,0,-1]) == [1*x + -1,1*x + 1,x^2 + 1]\r\n-- ---------------------------------------------------------------------\r\n\r\nfactorizacion :: Polinomio Int -> [Polinomio Int]\r\nfactorizacion p \r\n    | esPolCero p = [p]\r\n    | otherwise   = aux (0 : divisores (terminoIndep p))\r\n    where \r\n      aux [] = [p]\r\n      aux (r:rs)  \r\n          | esRaizRuffini r p = \r\n              (creaPol [1,-r]) : factorizacion (cocienteRuffini r p) \r\n          | otherwise = aux rs\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han explicado las soluciones de los ejercicios de la relaci\u00f3n 25. El objetivo de la relaci\u00f3n es implementar la regla de Ruffini y sus aplicaciones utilizando las implementaciones del TAD de polinomio estudiadas en el tema 21. En los ejercicios se&#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":[1],"tags":[270,298],"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\/3302"}],"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=3302"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3302\/revisions"}],"predecessor-version":[{"id":3303,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3302\/revisions\/3303"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3302"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3302"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3302"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}