{"id":3132,"date":"2013-03-19T16:21:37","date_gmt":"2013-03-19T16:21:37","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3132"},"modified":"2013-03-20T05:23:21","modified_gmt":"2013-03-20T05:23:21","slug":"i1m2012-resolucion-de-problemas-matematicos-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-resolucion-de-problemas-matematicos-con-haskell\/","title":{"rendered":"I1M2012: Resoluci\u00f3n de problemas matem\u00e1ticos con Haskell"},"content":{"rendered":"<p>En las clases de ayer y 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 12\u00aa relaci\u00f3n en  la que se plantea la resoluci\u00f3n de distintos problemas<br \/>\nmatem\u00e1ticos. En concreto,<\/p>\n<ul>\n<li>el problema de Ullman sobre la existencia de subconjunto del tama\u00f1o dado y con su suma acotada,\n<li>las descomposiciones de un n\u00famero como suma de dos cuadrados,\n<li>el problema 145 del proyecto Euler,\n<li>el grafo de una funci\u00f3n sobre los elementos que cumplen una propiedad,\n<li>los n\u00fameros semiperfectos,\n<li>el car\u00e1cter funcional de una relaci\u00f3n y\n<li> la identidad de Bezout.\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 auxiliares                                --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\nimport Data.List\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n \r\n--    ullman :: (Num a, Ord a) => a -> Int -> [a] -> Bool\r\n-- tal que (ullman t k xs) se verifica si xs tiene un subconjunto con k \r\n-- elementos cuya suma sea menor que t. Por ejemplo,\r\n--    ullman 9 3 [1..10] == True\r\n--    ullman 5 3 [1..10] == False\r\n-- ---------------------------------------------------------------------\r\n\r\n-- 1\u00aa soluci\u00f3n (corta y eficiente)\r\nullman :: (Ord a, Num a) => a -> Int -> [a] -> Bool\r\nullman t k xs = sum (take k (sort xs)) < t\r\n\r\n-- 2\u00aa soluci\u00f3n (larga e ineficiente)\r\nullman2 :: (Num a, Ord a) => a -> Int -> [a] -> Bool\r\nullman2 t k xs = \r\n    [ys | ys <- subconjuntos xs, length ys == k, sum ys < t] \/= []\r\n\r\n-- (subconjuntos xs) es la lista de los subconjuntos de xs. Por \r\n-- ejemplo,\r\n--    subconjuntos \"bc\"  ==  [\"\",\"c\",\"b\",\"bc\"]\r\n--    subconjuntos \"abc\" ==  [\"\",\"c\",\"b\",\"bc\",\"a\",\"ac\",\"ab\",\"abc\"]\r\nsubconjuntos :: [a] -> [[a]]\r\nsubconjuntos [] = [[]]\r\nsubconjuntos (x:xs) = zss++[x:ys | ys <- zss]\r\n    where zss = subconjuntos xs\r\n\r\n-- Los siguientes ejemplos muestran la diferencia en la eficencia:\r\n--    *Main> ullman 9 3 [1..20]\r\n--    True\r\n--    (0.02 secs, 528380 bytes)\r\n--    *Main> ullman2 9 3 [1..20]\r\n--    True\r\n--    (4.08 secs, 135267904 bytes)\r\n--    *Main> ullman 9 3 [1..100]\r\n--    True\r\n--    (0.02 secs, 526360 bytes)\r\n--    *Main> ullman2 9 3 [1..100]\r\n--      C-c C-cInterrupted.\r\n--    Agotado\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    sumasDe2Cuadrados :: Integer -> [(Integer, Integer)]\r\n-- tal que (sumasDe2Cuadrados n) es la lista de los pares de n\u00fameros\r\n-- tales que la suma de sus cuadrados es n y el primer elemento del par\r\n-- es mayor o igual que el segundo. Por ejemplo,\r\n--    sumasDe2Cuadrados 25  ==  [(5,0),(4,3)]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Primera definici\u00f3n:\r\nsumasDe2Cuadrados_1 :: Integer -> [(Integer, Integer)]\r\nsumasDe2Cuadrados_1 n = \r\n    [(x,y) | x <- [n,n-1..0],\r\n             y <- [0..x],\r\n             x*x+y*y == n]\r\n\r\n-- Segunda definici\u00f3n:\r\nsumasDe2Cuadrados_2 :: Integer -> [(Integer, Integer)]\r\nsumasDe2Cuadrados_2 n = \r\n    [(x,y) | x <- [a,a-1..0],\r\n             y <- [0..x],\r\n             x*x+y*y == n]\r\n    where a = ceiling (sqrt (fromIntegral n))\r\n\r\n-- Tercera definici\u00f3n:\r\nsumasDe2Cuadrados_3 :: Integer -> [(Integer, Integer)]\r\nsumasDe2Cuadrados_3 n = aux (ceiling (sqrt (fromIntegral n))) 0 where\r\n    aux x y | x < y          = [] \r\n            | x*x + y*y <  n = aux x (y+1)\r\n            | x*x + y*y == n = (x,y) : aux (x-1) (y+1)\r\n            | otherwise      = aux (x-1) y\r\n\r\n-- Comparaci\u00f3n\r\n--    +----------+---------------+---------------+---------------+\r\n--    | n        | 1\u00aa definici\u00f3n | 2\u00aa definici\u00f3n | 3\u00aa definici\u00f3n |\r\n--    +----------+---------------+---------------+---------------+\r\n--    |      999 | 2.17 segs     |   0.02 segs   | 0.01 segs     |  \r\n--    | 48612265 |               | 140.38 segs   | 0.13 segs     |\r\n--    +----------+---------------+---------------+---------------+\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. (Basado en el problema 145 del Proyecto Euler). Se dice\r\n-- que un n\u00famero n es reversible si su \u00faltima cifra es distinta de 0 y\r\n-- la suma de n y el n\u00famero obtenido escribiendo las cifras de n en\r\n-- orden inverso es un n\u00famero que tiene todas sus cifras impares. Por\r\n-- ejemplo, 36 es reversible porque 36+63=99 tiene todas sus cifras\r\n-- impares, 409 es reversible porque 409+904=1313 tiene todas sus cifras\r\n-- impares,  243 no es reversible porque 243+342=585 no tiene todas sus\r\n-- cifras impares. \r\n-- Definir la funci\u00f3n \r\n--    reversiblesMenores :: Int -> Int\r\n-- tal que (reversiblesMenores n) es la cantidad de n\u00fameros reversibles\r\n-- menores que n. Por ejemplo,\r\n--    reversiblesMenores 10   == 0\r\n--    reversiblesMenores 100  == 20\r\n--    reversiblesMenores 1000 == 120\r\n-- ---------------------------------------------------------------------\r\n\r\nreversiblesMenores :: Int -> Int\r\nreversiblesMenores n = length [x | x <- [1..n-1], esReversible x]\r\n\r\n-- (esReversible n) se verifica si n es reversible; es decir, si su\r\n-- \u00faltima cifra es distinta de 0 y la suma de n y el n\u00famero obtenido\r\n-- escribiendo las cifras de n en orden inverso es un n\u00famero que tiene\r\n-- todas sus cifras impares. Por ejemplo,\r\n--    esReversible 36  == True\r\n--    esReversible 409 == True\r\nesReversible :: Int -> Bool\r\nesReversible n = rem n 10 \/= 0 && impares (cifras (n + (inverso n)))\r\n\r\n-- (impares xs) se verifica si xs es una lista de n\u00fameros impares. Por\r\n-- ejemplo, \r\n--    impares [3,5,1] == True\r\n--    impares [3,4,1] == False\r\nimpares :: [Int] -> Bool\r\nimpares xs = and [odd x | x <- xs]\r\n\r\n-- (inverso n) es el n\u00famero obtenido escribiendo las cifras de n en\r\n-- orden inverso. Por ejemplo,\r\n--    inverso 3034 == 4303\r\ninverso :: Int -> Int\r\ninverso n = read (reverse (show n))\r\n\r\n-- (cifras n) es la lista de las cifras del n\u00famero n. Por ejemplo,\r\n--    cifras 3034 == [3,0,3,4]\r\ncifras :: Int -> [Int]\r\ncifras n = [read [x] | x <- show n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir, usando funciones de orden superior, la funci\u00f3n\r\n--    grafoReducido :: Eq a => (a -> b) -> (a -> Bool) -> [a] -> [(a,b)]\r\n-- tal que (grafoReducido f p xs) es la lista (sin repeticiones) de los\r\n-- pares formados por los elementos de xs que verifican el predicado p\r\n-- y sus im\u00e1genes. Por ejemplo, \r\n--    grafoReducido (^2) even [1..9]  ==  [(2,4),(4,16),(6,36),(8,64)]\r\n--    grafoReducido (+4) even (replicate 40 1) == []\r\n--    grafoReducido (*5) even (replicate 40 2) == [(2,10)]\r\n-- ---------------------------------------------------------------------\r\n\r\ngrafoReducido :: Eq a => (a -> b) -> (a -> Bool) -> [a] -> [(a,b)]\r\ngrafoReducido f p xs = [(x,f x) | x <- nub xs, p x]\r\n\r\n-- -------------------------------------------------------------------\r\n-- Ejercicio 5.1. Un n\u00famero natural n se denomina semiperfecto si es la\r\n-- suma de algunos de sus divisores propios. Por ejemplo, 18 es\r\n-- semiperfecto ya que sus divisores son 1, 2, 3, 6, 9 y se cumple que\r\n-- 3+6+9=18.  \r\n-- \r\n-- Definir la funci\u00f3n \r\n--    esSemiPerfecto :: Int -> Bool\r\n-- tal que (esSemiPerfecto n) se verifica si n es semiperfecto. Por\r\n-- ejemplo, \r\n--    esSemiPerfecto 18 == True\r\n--    esSemiPerfecto 9  == False\r\n--    esSemiPerfecto 24 == True\r\n-- ---------------------------------------------------------------------\r\n\r\nesSemiPerfecto :: Int -> Bool\r\nesSemiPerfecto n =\r\n    or [sum ys == n | ys <- subconjuntos (divisores n)]\r\n\r\n-- (divisores n) es la lista de los divisores propios de n. Por ejemplo,\r\n--    divisores 18 == [1,2,3,6,9]\r\ndivisores :: Int -> [Int]\r\ndivisores n = [x | x <- [1..n-1], mod n x == 0]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.2. Definir la constante primerSemiPerfecto tal que su\r\n-- valor es el primer n\u00famero semiperfecto. \r\n-- ---------------------------------------------------------------------\r\n\r\nprimerSemiPerfecto :: Int\r\nprimerSemiPerfecto = head [n | n <- [1..], esSemiPerfecto n]\r\n\r\n-- La evaluaci\u00f3n es\r\n--    *Main> primerSemiPerfecto\r\n--    6\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.3. Definir la funci\u00f3n \r\n--    semiPerfecto :: Int -> Int\r\n-- tal que (semiPerfecto n) es el n-\u00e9simo n\u00famero semiperfecto. Por\r\n-- ejemplo, \r\n--    semiPerfecto 1   == 6\r\n--    semiPerfecto 4   == 20\r\n--    semiPerfecto 100 == 414\r\n-- ---------------------------------------------------------------------\r\n\r\nsemiPerfecto :: Int -> Int\r\nsemiPerfecto n = semiPerfectos !! n\r\n\r\n-- semiPerfectos es la lista de los n\u00fameros semiPerfectos. Por ejemplo, \r\n--    take 4 semiPerfectos  ==  [6,12,18,20]\r\nsemiPerfectos = [n | n <- [1..], esSemiPerfecto n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Las relaciones finitas se pueden representar mediante\r\n-- listas de pares. Por ejemplo,\r\n--    r1, r2, r3 :: [(Int, Int)]\r\n--    r1 = [(1,3), (2,6), (8,9), (2,7)]\r\n--    r2 = [(1,3), (2,6), (8,9), (3,7)]\r\n--    r3 = [(1,3), (2,6), (8,9), (3,6)]\r\n-- Definir la funci\u00f3n \r\n--    esFuncion :: (Eq a, Eq b) => [(a,b)] -> Bool\r\n-- tal que (esFuncion r) se verifica si la relaci\u00f3n r es una funci\u00f3n (es\r\n-- decir, a cada elemento del dominio de la relaci\u00f3n r le corresponde un\r\n-- \u00fanico elemento). Por ejemplo, \r\n--    esFuncion r1 == False\r\n--    esFuncion r2 == True\r\n--    esFuncion r3 == True\r\n-- ---------------------------------------------------------------------\r\n\r\nr1, r2, r3 :: [(Int, Int)]\r\nr1 = [(1,3), (2,6), (8,9), (2,7)]\r\nr2 = [(1,3), (2,6), (8,9), (3,7)]\r\nr3 = [(1,3), (2,6), (8,9), (3,6)]\r\n\r\nesFuncion :: (Eq a, Eq b) => [(a,b)] -> Bool\r\nesFuncion [] = True\r\nesFuncion ((x,y):r) = \r\n    [y' | (x',y') <- r, x == x', y \/= y'] == [] &#038;&#038; esFuncion r \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7.1. [La identidad de Bezout] Definir la funci\u00f3n\r\n--    bezout :: Integer -> Integer -> (Integer, Integer)\r\n-- tal que (bezout a b) es un par de n\u00fameros x e y tal que a*x+b*y es el\r\n-- m\u00e1ximo com\u00fan divisor de a y b. Por ejemplo,\r\n--    bezout 21 15  ==  (-2,3)\r\n-- Indicaci\u00f3n: Se puede usar la funci\u00f3n quotRem tal que (quotRem x y) es\r\n-- el par formado por el cociente y el resto de dividir x entre y.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Ejemplo de c\u00e1lculo\r\n--    a  b   q r   \r\n--    36 21  1 15   (1)\r\n--    21 15  1  6   (2) \r\n--    15  6  2  3   (3)\r\n--     6  3  2  0\r\n--     3  0   \r\n-- Por tanto,\r\n--    3 = 15 - 6*2              [por (3)]\r\n--      = 15 - (21-15*1)*2      [por (2)]\r\n--      = 21*(-2) + 15*3        \r\n--      = 21*(-2)+ (36-21*1)*3  [por (1)]\r\n--      = 36*3 + 21*(-5)\r\n\r\n-- Sean p, r el cociente y el resto de a entre b, d el m\u00e1ximo com\u00fan\r\n-- divisor de a y b y (x,y) el valor de (bezout b r) . Entonces,\r\n--    a = bp+r\r\n--    d = bx+ry \r\n-- ya que mcd(a,b) = mcd(b,r). Por tanto,\r\n--    d = bx + (a-bp)y\r\n--      = ay + b(x-qy)\r\n-- Luego,\r\n--    bezout a b = (y,x-qy)\r\n\r\nbezout :: Integer -> Integer -> (Integer, Integer)\r\nbezout _ 0 = (1,0)\r\nbezout _ 1 = (0,1)\r\nbezout a b = (y, x-q*y)\r\n    where (q,r) = quotRem a b\r\n          (x,y) = bezout b r\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7.2. Comprobar con QuickCheck que si a>0, b>0 y \r\n-- (x,y) es el valor de (bezout a b), entonces a*x+b*y es igual al\r\n-- m\u00e1ximo com\u00fan divisor de a y b.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_Bezout :: Integer -> Integer -> Property\r\nprop_Bezout a b = a>0 && b>0 ==> a*x+b*y == gcd a b\r\n    where (x,y) = bezout a b          \r\n\r\n-- La comprobaci\u00f3n es\r\n--   Main> quickCheck prop_Bezout\r\n--   OK, passed 100 tests.\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En las clases de ayer y de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han explicado las soluciones de los ejercicios de la 12\u00aa relaci\u00f3n en la que se plantea la resoluci\u00f3n de distintos problemas matem\u00e1ticos. En concreto, el problema de Ullman sobre la existencia de subconjunto del tama\u00f1o dado y con&#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,126],"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\/3132"}],"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=3132"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3132\/revisions"}],"predecessor-version":[{"id":3133,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3132\/revisions\/3133"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3132"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3132"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3132"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}