{"id":4901,"date":"2015-05-06T13:34:50","date_gmt":"2015-05-06T11:34:50","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4901"},"modified":"2015-05-15T13:37:58","modified_gmt":"2015-05-15T11:37:58","slug":"i1m2014-programacion-dinamica-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-programacion-dinamica-en-haskell\/","title":{"rendered":"I1M2014: Programaci\u00f3n din\u00e1mica en Haskell"},"content":{"rendered":"<p>En la segunda parte de la clase de hoy del curso <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos estudiado la t\u00e9cnica de programaci\u00f3n din\u00e1mica.<\/p>\n<p>En primer lugar, se explic\u00f3 el patr\u00f3n de la programaci\u00f3n din\u00e1mica. A continuacin, se aplic\u00f3 al problema de la sucesi\u00f3n de Fibonacci y problema del producto de cadenas de matrices.<\/p>\n<p>Las transparencias usadas en la clase son las p\u00e1ginas 1-21 del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/temas\/tema-24t.pdf\">tema 24<\/a>:<br \/>\n<!--more--><\/p>\n<p>El c\u00f3digo del patr\u00f3n de programaci\u00f3n din\u00e1mica es<\/p>\n<pre lang=\"haskell\">\nmodule Dinamica (module Tabla, dinamica)  where\n\nimport Data.Array\nimport I1M.Tabla as Tabla\n\ndinamica :: Ix i => (Tabla i v -> i -> v) -> (i,i) -> Tabla i v\ndinamica calcula cotas = t\n    where t = tabla [(i,calcula t i) | i <- range cotas]\n<\/pre>\n<p>El c\u00f3digo de la sucesi\u00f3n de Fibonacci con programaci\u00f3n din\u00e1mica es<\/p>\n<pre lang=\"haskell\">\nimport I1M.Dinamica\n\n-- ---------------------------------------------------------------------\n-- Fibonacci como ejemplo de programaci\u00f3n din\u00e1mica.                   --\n-- ---------------------------------------------------------------------\n\n-- (fib n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de Fibonacci, calculado\n-- mediante programaci\u00f3n din\u00e1mica. Por ejemplo, \n--    fib 8  ==  21\nfib :: Int -> Int\nfib n = valor t n\n    where t = dinamica calculaFib (cotasFib n) \n\n-- (calculaFib t i) es el valor de i-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de\n-- Fibonacci calculado mediante la tabla t que contiene los\n-- anteriores. Por ejemplo,\n--    calculaFib (tabla []) 0                                     ==  0\n--    calculaFib (tabla [(0,0)]) 1                                ==  1\n--    calculaFib (tabla [(0,0),(1,1)]) 2                          ==  1\n--    calculaFib (tabla [(0,0),(1,1),(2,1)]) 3                    ==  2\n--    calculaFib (tabla [(0,0),(1,1),(2,1),(3,2)]) 4              ==  3\n--    calculaFib (tabla [(0,0),(1,1),(2,1),(3,2),(4,3)]) 5        ==  5\n--    calculaFib (tabla [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5)]) 6  ==  8\n-- Adem\u00e1s,\n--    ghci> dinamica calculaFib (0,8)\n--    Tbl [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8),(7,13),(8,21)]\ncalculaFib :: Tabla Int Int -> Int -> Int\ncalculaFib t i | i <= 1    = i\n               | otherwise = valor t (i-1) + valor t (i-2)\n\n-- (cotasFib n) son las cotas del vector que se necesita para calcular\n-- el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de Fibonacci mediante programaci\u00f3n\n-- din\u00e1mica. \ncotasFib :: Int -> (Int,Int)\ncotasFib n = (0,n)\n\n-- ---------------------------------------------------------------------\n-- Fibonacci mediante divide y vencer\u00e1s                               --\n-- ---------------------------------------------------------------------\n\n-- (fibR n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de Fibonacci calculado\n-- mediante divide y vencer\u00e1s. Por ejemplo, \n--    fibR 8  ==  21\nfibR :: Int -> Int\nfibR 0 = 0\nfibR 1 = 1\nfibR n = fibR (n-1) + fibR (n-2)\n\n-- Comparaci\u00f3n\n--    ghci> fib 20\n--    6765\n--    (0.01 secs, 524824 bytes)\n--    ghci> fibR 20\n--    6765\n--    (0.06 secs, 2165236 bytes)\n--    ghci> fib 30\n--    832040\n--    (0.01 secs, 0 bytes)\n--    ghci> fibR 30\n--    832040\n--    (6.46 secs, 222602404 bytes)\n\n-- ---------------------------------------------------------------------\n-- Fibonacci mediante programaci\u00f3n din\u00e1mica con listas infinitas      --\n-- ---------------------------------------------------------------------\n\n-- fibs es la lista de los t\u00e9rminos de la sucesi\u00f3n de Fibonacci. Por\n-- ejemplo, \n--    take 10 fibs  ==  [0,1,1,2,3,5,8,13,21,34]\nfibs :: [Int]\nfibs = 0:1:[x+y | (x,y) <- zip fibs (tail fibs)]\n\n-- (fib' n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de Fibonacci, calculado\n-- a partir de fibs. Por ejemplo, \n--    fib' 8  ==  21\nfib' :: Int -> Int\nfib' n = fibs!!n\n\n-- Comparaciones:\n--    ghci> fib 30\n--    832040\n--    (0.02 secs, 524808 bytes)\n--    ghci> fib' 30\n--    832040\n--    (0.01 secs, 542384 bytes)\n<\/pre>\n<p>El c\u00f3digo del problema del producto de cadenas de matrices es<\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Descripci\u00f3n del problema                                           --\n-- ---------------------------------------------------------------------\n\n-- Para multiplicar una matriz de orden m*p y otra de orden p*n se\n-- necesitan mnp multiplicaciones de elementos.\n\n-- El problema del producto de una cadena de matrices (en ingl\u00e9s,\n-- \"matrix chain multiplication\") consiste en dada una sucesi\u00f3n de\n-- matrices encontrar la manera de multiplicarlas usando el menor n\u00famero\n-- de productos de elementos.   \n\n-- Ejemplo: Dada la sucesi\u00f3n de matrices\n--    A (30 x 1), B (1 x 40), C (40 x 10), D (10 x 25)\n-- las productos necesarios en las posibles asociaciones son\n--    ((AB)C)D  30 x  1 x 40 + 30 x 40 x 10 + 30 x 10 x 25 = 20700\n--    A{B{CD))  40 x 10 x 25 +  1 x 40 x 25 + 30 x  1 x 25 = 11750\n--    (AB)(CD)  30 x  1 x 40 + 40 x 10 x 25 + 30 x 40 x 25 = 41200\n--    A((BC)D)   1 x 40 x 10 +  1 x 10 x 25 + 30 x  1 x 25 =  1400 \n--    (A(BC))D  1  x 40 x 10 + 30 x  1 x 10 + 30 x 10 x 25 =  8200 \n\n-- ---------------------------------------------------------------------\n-- El algoritmo                                                       --\n-- ---------------------------------------------------------------------\n\n-- Sea ds=[d_0,...,d_n)] una sucesi\u00f3n de n\u00fameros naturales.\n\n-- A_1,...,A_n es una cadena de matrices de tipo ds si para cada i, A_i es\n-- una matriz de orden d_(i-1)xd_i.\n\n-- c(i,j) es el m\u00ednimo n\u00famero de multiplicaciones para multiplicar la\n-- cadena Ai,...,Aj (1<=i<=j<=n).\n\n-- Relaci\u00f3n de recurrencia de c(i,j):\n-- * c(i,i) = 0\n-- * c(i,j) = min { c(i,k)+c(k+1,j)+d_(i-1)*d_k*d_j | i<=k<=j}\n\n-- La soluci\u00f3n del problema es c(1,n).\n\n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas auxiliares                                --\n-- ---------------------------------------------------------------------\n\nimport I1M.Dinamica\n\n-- ---------------------------------------------------------------------\n-- Soluci\u00f3n mediante programaci\u00f3n din\u00e1mica                            --\n-- ---------------------------------------------------------------------\n\n-- Cadena representa el producto de una cadena de matrices. Por ejemplo,\n--    ghci> P (A 1) (P (A 2) (A 3))\n--    (A1*(A2*A3))\n--    ghci> P (P (A 1) (A 2)) (A 3)\n--    ((A1*A2)*A3)\ndata Cadena = A Int \n            | P Cadena Cadena\n\ninstance Show Cadena where\n    show (A x)     = \"A\" ++ show x\n    show (P p1 p2) = concat [\"(\", show p1, \"*\", show p2, \")\"]\n\n-- Los \u00edndices de la matriz de c\u00e1lculo son de la forma (i,j) y sus\n-- valores (v,k) donde v es el m\u00ednimo n\u00famero de multiplicaciones\n-- necesarias para multiplicar la cadena Ai,...,Aj y k es la posici\u00f3n\n-- donde dividir la cadena de forma \u00f3ptima.\ntype IndicePCM = (Int,Int)\ntype ValorPCM  = (Int,Int)\n\n-- (pcm ds) es la el par formado por el n\u00famero de multiplicaciones\n-- elementales de la cadena \u00f3ptima para multiplicar las matrices A1, A2, ...\n-- tales que sus dimensiones son (d1*d2), (d2*d3), ... donde [d1,d2,...]\n-- es ds y la cadena. Por ejemplo,  \n--    ghci> pcm [30,1,40,10,25]\n--    (1400,(A1*((A2*A3)*A4)))\npcm :: [Int] -> (Int, Cadena)\npcm ds = (v, cadena t 1 n)\n    where n     = length ds - 1\n          t     = dinamica (calculaPCM ds) (cotasPCM n)\n          (v,_) = valor t (1,n)\n\n-- (calculaPCM ds t (i,j)) es el valor del \u00edndice (i,j) calculado a\n-- partir de la lista ds de dimensiones de las matrices y la tabla t de\n-- valores previamente calculados.\ncalculaPCM :: [Int] -> Tabla IndicePCM ValorPCM -> IndicePCM -> ValorPCM\ncalculaPCM ds t (i,j) \n    | i == j    = (0,i)\n    | otherwise = minimum [(fst(valor t (i,k)) \n                            + fst(valor t (k+1,j)) \n                            + ds!!(i-1) * ds!!k * ds!!j, k) \n                           | k <- [i..j-1]]\n\n-- (cotasPCM n) son las cotas de los \u00edndices para el producto de una\n-- cadena de n matrices.\ncotasPCM :: Int -> (IndicePCM,IndicePCM)\ncotasPCM n = ((1,1),(n,n)) \n\n-- (cadena t i j) es la cadena que resultar de agrupar las matrices\n-- Ai,...,Aj seg\u00fan los valores de la tabla t.\ncadena :: Tabla IndicePCM ValorPCM -> Int -> Int -> Cadena\ncadena t i j \n    | i == j-1  = P (A i) (A j)\n    | k == i    = P (A i) (cadena t (i+1) j)\n    | k == j-1  = P (cadena t i (j-1)) (A j)\n    | otherwise = P (cadena t i (k-1)) (cadena t k j)\n    where (_,k) = valor t (i,j)\n\n-- (pcm' ds) es la lista de los \u00edndices y valores usados en el c\u00e1lculo\n-- de la cadena \u00f3ptima para multiplicar las matrices A1, A2, ... tales\n-- que sus dimensiones son (d1*d2), (d2*d3), ... donde [d1,d2,...] es\n-- ds. Por ejemplo,   \n--    ghci> pcm' [30,1,40,10,25]\n--    [((1,1),(0,1)),((1,2),(1200,1)),((1,3),(700,1)),((1,4),(1400,1)),\n--     ((2,2),(0,2)),((2,3),(400,2)),((2,4),(650,3)),\n--     ((3,3),(0,3)),((3,4),(10000,3)),\n--     ((4,4),(0,4))]\npcm' :: [Int] -> [((Int, Int), ValorPCM)]\npcm' ds = [((i,j),valor t (i,j)) | i <- [1..n], j <- [i..n]] \n    where n = length ds - 1\n          t = dinamica (calculaPCM ds) (cotasPCM n)\n\n-- ---------------------------------------------------------------------\n-- Soluci\u00f3n mediante divide y vencer\u00e1s                                --\n-- ---------------------------------------------------------------------\n\n-- (pcmDyV ds) es la el par formado por el n\u00famero de multiplicaciones\n-- elementales de la cadena \u00f3ptima para multiplicar las matrices \n-- A1, A2, ...tales que sus dimensiones son (d1*d2), (d2*d3), ... donde\n-- [d1,d2,...] es ds y la cadena, calculada mediante divide y\n-- vencer\u00e1s. Por ejemplo,   \n--    ghci> pcmDyV [30,1,40,10,25]\n--    (1040,(A1*((A2*A3)*A4)))\npcmDyV :: [Int] -> (Int, Cadena)\npcmDyV ds = cadenaDyV ds 1 n\n    where n = length ds - 1\n         \n-- (cadenaDyV ds i j) es el par formado por el n\u00famero de\n-- multiplicaciones elementales de la cadena \u00f3ptima para multiplicar las\n-- matrices  Ai, ..., Aj tales que sus dimensiones son \n-- (di*d_(i+1)), ... (d_(j-1)*dj), donde [d1,d2,...] es ds y la cadena,\n-- calculada mediante divide y vencer\u00e1s. Por ejemplo,   \n--    cadenaDyV [30,1,40,10,25] 1 4  ==  (1040,(A1*((A2*A3)*A4)))\n--    cadenaDyV [30,1,40,10,25] 2 4  ==  (290,((A2*A3)*A4))\n-- cadenaDyV :: [Int] -> Int -> Int -> (Int, Cadena)\n-- cadenaDyV ds i j \ncadenaDyV :: [Int] -> Int -> Int -> (Int, Cadena)\ncadenaDyV ds i j \n    | i == j    = (0, A i)\n    | i == j-1  = (ds!!(i-1)*ds!!i*ds!!j, P (A i) (A j))\n    | k == i    = (v, P (A i) (subcadena (i+1) j))\n    | k == j-1  = (v, P (subcadena i (j-1)) (A j))\n    | otherwise = (v, P (subcadena i (k-1)) (subcadena k j))\n    where (v,k) = minimum [((valor i k) \n                            + (valor (k+1) j) \n                            + ds!!(i-1) * ds!!k * ds!!j, k) \n                           | k <- [i..j-1]]\n          valor p q     = fst (cadenaDyV ds p q)\n          subcadena p q = snd (cadenaDyV ds p q)\n\n-- ---------------------------------------------------------------------\n-- Comparaci\u00f3n de las soluciones                                      --\n-- ---------------------------------------------------------------------\n\n--    ghci> :set +s\n--    ghci> fst (pcm [1..20])\n--    2658\n--    (0.04 secs, 4144552 bytes)\n--    ghci> fst (pcmDyV [1..20])\n--    2658\n--    (1582.60 secs, 340414297896 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la segunda parte de la clase de hoy del curso Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos estudiado la t\u00e9cnica de programaci\u00f3n din\u00e1mica. En primer lugar, se explic\u00f3 el patr\u00f3n de la programaci\u00f3n din\u00e1mica. A continuacin, se aplic\u00f3 al problema de la sucesi\u00f3n de Fibonacci y problema del producto de cadenas de matrices&#8230;.<\/p>\n","protected":false},"author":2,"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":[238],"tags":[244,270,305],"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\/4901"}],"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=4901"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4901\/revisions"}],"predecessor-version":[{"id":4903,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4901\/revisions\/4903"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4901"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4901"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4901"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}