{"id":6709,"date":"2019-06-05T07:47:34","date_gmt":"2019-06-05T05:47:34","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6709"},"modified":"2019-06-09T07:48:06","modified_gmt":"2019-06-09T05:48:06","slug":"i1m2018-programacion-dinamica-apilamiento-de-barriles","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2018-programacion-dinamica-apilamiento-de-barriles\/","title":{"rendered":"I1M2018: Programaci\u00f3n din\u00e1mica: Apilamiento de barriles"},"content":{"rendered":"<p>En la segunda parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-18\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han resuelto ejercicios de la relaci\u00f3n 46, en el que se comparan distintas soluciones del problema del apilamiento de barriles. Se ha mostrado como transformar las definiciones recursivas en definiciones con programaci\u00f3n din\u00e1mica. Adem\u00e1s, se han comparado experimentalmente la eficiencia de las distintas definiciones.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- \u00a7 Introducci\u00f3n                                                     --\n-- ---------------------------------------------------------------------\n\n-- Un mont\u00f3n de barriles se construye apilando unos encima de otros por\n-- capas, de forma que en cada capa todos los barriles est\u00e1n apoyados\n-- sobre dos de la capa inferior y todos los barriles de una misma capa\n-- est\u00e1n pegados unos a otros. Por ejemplo, los siguientes montones son\n-- v\u00e1lidos:  \n--       _          _   _                   _\n--      \/ \\        \/ \\ \/ \\                 \/ \\\n--     _\\_\/_      _\\_\/_\\_\/_   _       _   _\\_\/_   _\n--    \/ \\ \/ \\    \/ \\ \/ \\ \/ \\ \/ \\     \/ \\ \/ \\ \/ \\ \/ \\\n--    \\_\/ \\_\/    \\_\/ \\_\/ \\_\/ \\_\/     \\_\/ \\_\/ \\_\/ \\_\/\n--\n-- y los siguientes no son v\u00e1lidos:\n--     _   _          _       _               _   _\n--    \/ \\ \/ \\        \/ \\     \/ \\             \/ \\ \/ \\\n--    \\_\/_\\_\/_      _\\_\/_   _\\_\/_       _   _\\_\/_\\_\/\n--      \/ \\ \/ \\    \/ \\ \/ \\ \/ \\ \/ \\     \/ \\ \/ \\ \/ \\\n--      \\_\/ \\_\/    \\_\/ \\_\/ \\_\/ \\_\/     \\_\/ \\_\/ \\_\/\n--\n-- Se puede comprobar que el n\u00famero M(n) de formas distintas de\n-- construir montones con n barriles en la base viene dado por la\n-- siguiente f\u00f3rmula: \n--               n-1\n--              -------\n--               \\\n--                \\\n--    M(n) = 1 +   )    (n-j) * M(j)\n--                \/\n--               \/\n--              -------\n--               j = 1\n--\n-- El objetivo de esta relaci\u00f3n es estudiar la transformaci\u00f3n de\n-- definiciones recursivas en otras con programaci\u00f3n din\u00e1mica y comparar\n-- su eficiencia.\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Data.Array\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Ejercicios                                                       --\n-- ---------------------------------------------------------------------\n\n-- --------------------------------------------------------------------- \n-- Ejercicio 1. Definir, por recursi\u00f3n, la funci\u00f3n\n--    montonesR :: Integer -> Integer\n-- tal que (montonesR n) es el n\u00famero de formas distintas de construir \n-- montones con n barriles en la base. Por ejemplo,\n--    montonesR 1   ==  1\n--    montonesR 5   ==  34\n--    montonesR 10  ==  4181\n--    montonesR 15  ==  514229\n--    montonesR 20  ==  63245986\n-- ---------------------------------------------------------------------\n\nmontonesR :: Integer -> Integer\nmontonesR 1 = 1\nmontonesR n = 1 + sum [(n-j) * montonesR j | j <- [1..n-1]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir, por programaci\u00f3n din\u00e1mica, la funci\u00f3n\n--    montonesPD :: Integer -> Integer\n-- tal que (montonesPD n) es el n\u00famero de formas distintas de construir \n-- montones con n barriles en la base. Por ejemplo,\n--    montonesR 1   ==  1\n--    montonesR 5   ==  34\n--    montonesR 10  ==  4181\n--    montonesR 15  ==  514229\n--    montonesR 20  ==  63245986\n--    length (show (montonesPD 1000))  ==  418\n-- ---------------------------------------------------------------------\n\nmontonesPD :: Integer -> Integer\nmontonesPD n = (vectorMontones n) ! n\n\nvectorMontones :: Integer -> Array Integer Integer\nvectorMontones n = v where\n  v = array (1,n) [(i,f i) | i <- [1..n]]\n  f 1 = 1\n  f k = 1 + sum [(k-j)*v!j | j <- [1..k-1]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Comparar la eficiencia calculando el tiempo necesario\n-- para evaluar las siguientes expresiones\n--    montonesR  23\n--    montonesPD 23\n-- ---------------------------------------------------------------------\n\n-- La comparaci\u00f3n es\n--    \u03bb> montonesR 23\n--    1134903170\n--    (16.76 secs, 2,617,836,192 bytes)\n--    \u03bb> montonesPD 23\n--    1134903170\n--    (0.01 secs, 724,248 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Operando con las ecuaciones de M(n) se observa que\n--    M(1) = 1                          = 1\n--    M(2) = 1 + M(1)                   = M(1) + M(1)   \n--    M(3) = 1 + 2*M(1) + M(2)          = M(2) + (M(1) + M(2))\n--    M(4) = 1 + 3*M(1) + 2*M(2) + M(3) = M(3) + (M(1) + M(2) + M(3))\n-- En general,\n--    M(n) = M(n-1) + (M(1) + ... + M(n-1))\n--\n-- Unsando la ecuaci\u00f3n anterior, definir por recursi\u00f3n la funci\u00f3n\n--    montonesR2 :: Integer -> Integer\n-- tal que (montonesR2 n) es el n\u00famero de formas distintas de construir \n-- montones con n barriles en la base. Por ejemplo,\n--    montonesR2 1   ==  1\n--    montonesR2 5   ==  34\n--    montonesR2 10  ==  4181\n--    montonesR2 15  ==  514229\n--    montonesR2 20  ==  63245986\n-- ---------------------------------------------------------------------\n\nmontonesR2 :: Integer -> Integer\nmontonesR2 = fst . montonesR2Aux \n\n-- (montonesR2Aux n) es el par formado por M(n) y la suma\n-- M(1)+...+M(n). Por ejemplo, \n--    montonesR2Aux 10                  ==  (4181,6765)\n--    montonesR 10                      ==  4181\n--    sum [montonesR k | k <- [1..10]]  ==  6765\nmontonesR2Aux :: Integer -> (Integer,Integer)\nmontonesR2Aux 1 = (1,1)\nmontonesR2Aux n = (x+y,y+x+y)\n  where (x,y) = montonesR2Aux (n-1)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Comparar la eficiencia calculando el tiempo necesario\n-- para evaluar las siguientes expresiones\n--    montonesR  23\n--    montonesR2 23\n--    length (show (montonesPD 1000))\n--    length (show (montonesR2 1000))\n-- ---------------------------------------------------------------------\n\n-- La comparaci\u00f3n es\n--    \u03bb> montonesR 23\n--    1134903170\n--    (16.76 secs, 2,617,836,192 bytes)\n--    \u03bb> montonesR2 23\n--    1134903170\n--    (0.01 secs, 602,104 bytes)\n--    \u03bb> length (show (montonesPD 1000))\n--    418\n--    (2.29 secs, 349,208,304 bytes)\n--    \u03bb> length (show (montonesR2 1000))\n--    418\n--    (0.01 secs, 1,600,192 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Usando la ecuaci\u00f3n anterior y programaci\u00f3n din\u00e1mica,\n-- definir la funci\u00f3n \n--    montonesPD2 :: Integer -> Integer\n-- tal que (montonesPD2 n) es el n\u00famero de formas distintas de construir \n-- montones con n barriles en la base. Por ejemplo,\n--    montonesPD2 1   ==  1\n--    montonesPD2 5   ==  34\n--    montonesPD2 10  ==  4181\n--    montonesPD2 15  ==  514229\n--    montonesPD2 20  ==  63245986\n-- ---------------------------------------------------------------------\n\nmontonesPD2 :: Integer -> Integer\nmontonesPD2 n = fst ((vectorMontones2 n) ! n)\n\nvectorMontones2 :: Integer -> Array Integer (Integer,Integer)\nvectorMontones2 n = v where\n  v = array (1,n) [(i,f i) | i <- [1..n]]\n  f 1 = (1,1)\n  f k = (x+y,y+x+y)\n    where (x,y) = v!(k-1)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Comparar la eficiencia calculando el tiempo necesario\n-- para evaluar las siguientes expresiones\n--    length (show (montonesR2  40000))\n--    length (show (montonesPD2 40000))\n-- ---------------------------------------------------------------------\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (show (montonesR2 40000))\n--    16719\n--    (2.04 secs, 452,447,664 bytes)\n--    \u03bb> length (show (montonesPD2 40000))\n--    16719\n--    (2.12 secs, 466,528,472 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir, usando scanl1, la lista\n--    sucMontones :: [Integer]\n-- cuyos elementos son los n\u00fameros de formas distintas de construir \n-- montones con n barriles en la base, para n = 1, 2, .... Por ejemplo,\n--    take 10 sucMontones  ==  [1,2,5,13,34,89,233,610,1597,4181]\n-- ---------------------------------------------------------------------\n\nsucMontones :: [Integer]\nsucMontones = 1 : zipWith (+) sucMontones (scanl1 (+) sucMontones)\n\n-- El c\u00e1lculo es\n--    | sucMontones        | scanl1 (+) sucMontones |\n--    | 1:...              | 1:...                  |\n--    | 1:2:...            | 1:3:...                |\n--    | 1:2:5:...          | 1:3:8:...              |\n--    | 1:2:5:13:...       | 1:3:8:21:...           |\n--    | 1:2:5:13:34:...    | 1:3:8:21:55:...        |\n--    | 1:2:5:13:34:89:... | 1:3:8:21:55:144:...    |\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Usando la sucesci\u00f3n anterior, definir la funci\u00f3n \n--    montonesS :: Integer -> Integer\n-- tal que (montonesS n) es el n\u00famero de formas distintas de construir \n-- montones con n barriles en la base. Por ejemplo,\n--    montonesS 1   ==  1\n--    montonesS 5   ==  34\n--    montonesS 10  ==  4181\n--    montonesS 15  ==  514229\n--    montonesS 20  ==  63245986\n-- ---------------------------------------------------------------------\n\nmontonesS :: Int -> Integer\nmontonesS n = sucMontones !! (n-1)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Comparar la eficiencia calculando el tiempo necesario\n-- para evaluar las siguientes expresiones\n--    length (show (montonesR2  40000))\n--    length (show (montonesPD2 40000))\n--    length (show (montonesS   40000))\n-- ---------------------------------------------------------------------\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (show (montonesR2 40000))\n--    16719\n--    (2.04 secs, 452,447,664 bytes)\n--    \u03bb> length (show (montonesPD2 40000))\n--    16719\n--    (2.12 secs, 466,528,472 bytes)\n--    \u03bb> length (show (montonesS 40000))\n--    16719\n--    (0.72 secs, 298,062,216 bytes)\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 resuelto ejercicios de la relaci\u00f3n 46, en el que se comparan distintas soluciones del problema del apilamiento de barriles. Se ha mostrado como transformar las definiciones recursivas en definiciones con programaci\u00f3n din\u00e1mica. Adem\u00e1s, se han comparado&#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":[320],"tags":[],"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\/6709"}],"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=6709"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6709\/revisions"}],"predecessor-version":[{"id":6710,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6709\/revisions\/6710"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6709"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6709"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6709"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}