{"id":3259,"date":"2013-04-25T16:47:47","date_gmt":"2013-04-25T16:47:47","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3259"},"modified":"2013-04-26T11:48:27","modified_gmt":"2013-04-26T11:48:27","slug":"i1m2012-division-y-factorizacion-de-polinomios-mediante-la-regla-de-ruffini-en-haskell","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\/","title":{"rendered":"I1M2012: 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 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 6 primeros 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 = undefined\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 = undefined\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 = undefined\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 = undefined\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 = undefined\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]\r\n--     raicesRuffini ejPol3 == [0]\r\n--     raicesRuffini ejPol4 == [-2,-1,1]\r\n-- ---------------------------------------------------------------------\r\n\r\nraicesRuffini :: Polinomio Int -> [Int]\r\nraicesRuffini p = undefined\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--    ghci> factorizacion (creaPol [1,0,0,0,-1])\r\n--    [x^2 + 1,1*x + 1,1*x + -1]\r\n-- ---------------------------------------------------------------------\r\n\r\nfactorizacion :: Polinomio Int -> [Polinomio Int]\r\nfactorizacion = undefined\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han explicado las soluciones de los 6 primeros 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&#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":[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\/3259"}],"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=3259"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3259\/revisions"}],"predecessor-version":[{"id":3260,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3259\/revisions\/3260"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3259"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3259"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3259"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}