{"id":5409,"date":"2016-04-29T16:15:28","date_gmt":"2016-04-29T14:15:28","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5409"},"modified":"2016-04-30T06:16:38","modified_gmt":"2016-04-30T04:16:38","slug":"i1m2015-division-y-factorizacion-de-polinomios-mediante-la-regla-de-ruffini-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-division-y-factorizacion-de-polinomios-mediante-la-regla-de-ruffini-en-haskell\/","title":{"rendered":"I1M2015: Divisi\u00f3n y factorizaci\u00f3n de polinomios mediante la regla de Ruffini en Haskell"},"content":{"rendered":"<p>En la segunda parte de la clase de hoy del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones de los ejercicios de la relaci\u00f3n 34. 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-15\/temas\/temas-21.html\">tema 21<\/a>.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n de ejercicios es implementar la regla de\n-- Ruffini y sus aplicaciones utilizando las implementaciones del TAD de\n-- polinomio estudiadas en el tema 21 que se pueden descargar desde \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\/temas\/tema-21.html\n-- \n-- Para realizar los ejercicios hay que tener instalada la librer\u00eda I1M\n-- que contiene la implementaci\u00f3n de TAD de los polinomios. Los pasos\n-- para instalarla son los siguientes:\n-- + Descargar el paquete I1M desde http:\/\/bit.ly\/1pbnDqm\n-- + Descomprimirlo (y se crea el directorio I1M-master.zip).\n-- + Cambiar al directorio I1M-master.\n-- + Ejecutar cabal install I1M.cabal\n-- \n-- Otra forma es descargar, en el directorio de ejercicios, la\n-- implementaci\u00f3n del TAD de polinomios: \n-- + PolRepTDA      que est\u00e1 en http:\/\/bit.ly\/1WJnS93\n-- + PolRepDispersa que est\u00e1 en http:\/\/bit.ly\/1WJnUO8\n-- + PolRepDensa    que est\u00e1 en http:\/\/bit.ly\/1WJnV4E \n-- + PolOperaciones que est\u00e1 en http:\/\/bit.ly\/1WJnTd7\n\n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas                                           --\n-- ---------------------------------------------------------------------\n\nimport Test.QuickCheck\n\n-- Hay que elegir una librer\u00eda \nimport I1M.PolOperaciones \n-- import PolOperaciones \n\n-- ---------------------------------------------------------------------\n-- Ejemplos                                                           --\n-- ---------------------------------------------------------------------\n\n-- Adem\u00e1s de los ejemplos de polinomios (ejPol1, ejPol2 y ejPol3) que se\n-- encuentran en PolOperaciones, usaremos el siguiente ejemplo.\nejPol4 :: Polinomio Int\nejPol4 = consPol 3 1 \n                 (consPol 2 2 \n                          (consPol 1 (-1) \n                                   (consPol 0 (-2) polCero)))\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    divisores :: Int -> [Int]\n-- tal que (divisores n) es la lista de todos los divisores enteros de\n-- n. Por ejemplo,\n--    divisores 4     ==  [1,-1,2,-2,4,-4]\n--    divisores (-6)  ==  [1,-1,2,-2,3,-3,6,-6]\n-- ---------------------------------------------------------------------\n\ndivisores :: Int -> [Int]\ndivisores n = concat [[x,-x] | x <- [1..abs n], rem n x == 0]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    coeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a\n-- tal que (coeficiente k p) es el coeficiente del t\u00e9rmino de grado k en\n-- p. Por ejemplo:\n--     coeficiente 4 ejPol1 == 3\n--     coeficiente 3 ejPol1 == 0\n--     coeficiente 2 ejPol1 == -5\n--     coeficiente 5 ejPol1 == 0\n-- ---------------------------------------------------------------------\n\ncoeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a\ncoeficiente k p | k == gp      = coefLider p\n                | k > grado rp = 0\n                | otherwise    = coeficiente k rp\n    where gp = grado p\n          rp = restoPol p\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n \n--    terminoIndep :: (Num a, Eq a) => Polinomio  a -> a\n-- tal que (terminoIndep p) es el t\u00e9rmino independiente del polinomio\n-- p. Por ejemplo,\n--    terminoIndep ejPol1 == 3\n--    terminoIndep ejPol2 == 0\n--    terminoIndep ejPol4 == -2\n-- ---------------------------------------------------------------------\n\nterminoIndep :: (Num a, Eq a) => Polinomio  a -> a\nterminoIndep = coeficiente 0\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n \n--    coeficientes :: (Num a, Eq a) => Polinomio a -> [a]\n-- tal que (coeficientes p) es la lista de coeficientes de p, ordenada\n-- seg\u00fan el grado. Por ejemplo,\n--     coeficientes ejPol1 == [3,0,-5,0,3]\n--     coeficientes ejPol4 == [1,2,-1,-2]\n--     coeficientes ejPol2 == [1,0,0,5,4,0]\n-- ---------------------------------------------------------------------\n\ncoeficientes :: (Num a, Eq a) => Polinomio a -> [a]\ncoeficientes p = [coeficiente k p | k <- [n,n-1..0]]\n    where n = grado p\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n \n--    creaPol :: (Num a, Eq a) => [a] -> Polinomio a\n-- tal que (creaPol cs) es el polinomio cuya lista de coeficientes es\n-- cs. Por ejemplo,\n--     creaPol [1,0,0,5,4,0] == x^5 + 5*x^2 + 4*x\n--     creaPol [1,2,0,3,0]   == x^4 + 2*x^3 + 3*x\n-- ---------------------------------------------------------------------\n\ncreaPol :: (Num a, Eq a) => [a] -> Polinomio a\ncreaPol []     = polCero\ncreaPol (a:as) = consPol n a (creaPol as)\n    where n = length as\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Comprobar con QuickCheck que, dado un polinomio p, el\n-- polinomio obtenido mediante creaPol a partir de la lista de\n-- coeficientes de p coincide con p.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_coef:: Polinomio Int -> Bool\nprop_coef p =\n    creaPol (coeficientes p) == p\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_coef\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir una funci\u00f3n \n--    pRuffini:: Int -> [Int] -> [Int]\n-- tal que (pRuffini r cs) es la lista que resulta de aplicar un paso\n-- del regla de Ruffini al n\u00famero entero r y a la lista de coeficientes\n-- cs. Por ejemplo,\n--    pRuffini 2 [1,2,-1,-2] == [1,4,7,12]\n--    pRuffini 1 [1,2,-1,-2] == [1,3,2,0]\n-- ya que\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-- ---------------------------------------------------------------------\n\npRuffini :: Int -> [Int] -> [Int]\npRuffini r p@(c:cs) = \n    c : [x+r*y | (x,y) <- zip cs (pRuffini r p)]\n\n-- 2\u00aa definici\u00f3n\npRuffini2 :: Int -> [Int] -> [Int]\npRuffini2 r = scanl1 (\\s x -> s * r + x)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n \n--    cocienteRuffini:: Int -> Polinomio Int -> Polinomio Int\n-- tal que (cocienteRuffini r p) es el cociente de dividir el polinomio\n-- p por el polinomio x-r. Por ejemplo:\n--     cocienteRuffini 2 ejPol4    == x^2 + 4*x + 7\n--     cocienteRuffini (-2) ejPol4 == x^2 + -1\n--     cocienteRuffini 3 ejPol4    == x^2 + 5*x + 14\n-- ---------------------------------------------------------------------\n\ncocienteRuffini :: Int -> Polinomio Int -> Polinomio Int\ncocienteRuffini r p = creaPol (init (pRuffini r (coeficientes p)))\n\n-- 2\u00aa definici\u00f3n\ncocienteRuffini2 :: Int -> Polinomio Int -> Polinomio Int\ncocienteRuffini2 r = creaPol . pRuffini r . init . coeficientes\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n \n--    restoRuffini:: Int -> Polinomio Int -> Int\n-- tal que (restoRuffini r p) es el resto de dividir el polinomio p por\n-- el polinomio x-r. Por ejemplo, \n--     restoRuffini 2 ejPol4    == 12\n--     restoRuffini (-2) ejPol4 == 0\n--     restoRuffini 3 ejPol4    == 40\n-- ---------------------------------------------------------------------\n\nrestoRuffini :: Int -> Polinomio Int -> Int\nrestoRuffini r p = last (pRuffini r (coeficientes p))\n\n-- 2\u00aa definici\u00f3n\nrestoRuffini2 :: Int -> Polinomio Int -> Int\nrestoRuffini2 r = last . pRuffini r . coeficientes\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Comprobar con QuickCheck que, dado un polinomio p y un\n-- n\u00famero entero r, las funciones anteriores verifican la propiedad de\n-- la divisi\u00f3n eucl\u00eddea.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_diviEuclidea:: Int -> Polinomio Int -> Bool\nprop_diviEuclidea r p =\n    p == sumaPol (multPol coc div) res\n    where coc = cocienteRuffini r p\n          div = creaPol [1,-r]\n          res = creaTermino 0 (restoRuffini r p) \n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_diviEuclidea\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Definir la funci\u00f3n\n--     esRaizRuffini:: Int -> Polinomio Int -> Bool \n-- tal que (esRaizRuffini r p) se verifica si r es una raiz de p, usando\n-- para ello el regla de Ruffini. Por ejemplo,\n--     esRaizRuffini 0 ejPol3 == True\n--     esRaizRuffini 1 ejPol3 == False\n-- ---------------------------------------------------------------------\n\nesRaizRuffini:: Int -> Polinomio Int -> Bool \nesRaizRuffini r p = restoRuffini r p == 0\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n \n--     raicesRuffini :: Polinomio Int -> [Int]\n-- tal que (raicesRuffini p) es la lista de las raices enteras de p,\n-- calculadas usando el regla de Ruffini. Por ejemplo,\n--     raicesRuffini ejPol1              == []\n--     raicesRuffini ejPol2              == [0]\n--     raicesRuffini ejPol3              == [0]\n--     raicesRuffini ejPol4              == [-2,-1,1]\n--     raicesRuffini (creaPol [1,-2,1])  == [1,1]\n-- ---------------------------------------------------------------------\n\nraicesRuffini :: Polinomio Int -> [Int]\nraicesRuffini p     \n    | esPolCero p = []\n    | otherwise   = aux (0 : divisores (terminoIndep p))\n    where \n      aux [] = []\n      aux (r:rs) \n          | esRaizRuffini r p = r : raicesRuffini (cocienteRuffini r p) \n          | otherwise         = aux rs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la funci\u00f3n\n--    factorizacion :: Polinomio Int -> [Polinomio Int]\n-- tal que (factorizacion p) es la lista de la descomposici\u00f3n del\n-- polinomio p en factores obtenida mediante el regla de Ruffini. Por\n-- ejemplo, \n--  ejPol2                               ==  x^5 + 5*x^2 + 4*x\n--  factorizacion ejPol2                 == [1*x,1*x+1,x^3+-1*x^2+1*x+4]\n--  ejPol4                               == x^3 + 2*x^2 + -1*x + -2\n--  factorizacion ejPol4                 == [1*x + -1,1*x + 1,1*x + 2,1]\n--  factorizacion (creaPol [1,0,0,0,-1]) == [1*x + -1,1*x + 1,x^2 + 1]\n-- ---------------------------------------------------------------------\n\nfactorizacion :: Polinomio Int -> [Polinomio Int]\nfactorizacion p \n    | esPolCero p = [p]\n    | otherwise   = aux (0 : divisores (terminoIndep p))\n    where \n      aux [] = [p]\n      aux (r:rs)  \n          | esRaizRuffini r p = \n              creaPol [1,-r] : factorizacion (cocienteRuffini r p)\n          | otherwise = aux rs\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la segunda parte de la clase de hoy del curso de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han explicado las soluciones de los ejercicios de la relaci\u00f3n 34. 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&#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":[250],"tags":[270,310],"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\/5409"}],"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=5409"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5409\/revisions"}],"predecessor-version":[{"id":5410,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5409\/revisions\/5410"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5409"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5409"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5409"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}