{"id":1406,"date":"2011-06-01T18:07:24","date_gmt":"2011-06-01T18:07:24","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1406"},"modified":"2011-06-01T18:55:31","modified_gmt":"2011-06-01T18:55:31","slug":"i1m2010-i1m2010-programacion-dinamica-en-haskell-y-el-problema-del-producto-de-cadenas-de-matrices","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2010-i1m2010-programacion-dinamica-en-haskell-y-el-problema-del-producto-de-cadenas-de-matrices\/","title":{"rendered":"I1M2010: Programaci\u00f3n din\u00e1mica en Haskell y el problema del producto de cadenas de matrices"},"content":{"rendered":"<p>En la clase de hoy de <a  href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos estudiado el patr\u00f3n de programaci\u00f3n din\u00e1mica en Haskell.<\/p>\n<p>Comenzamos la clase analizando los inconvenientes de la t\u00e9cnica del divide y vencer\u00e1s en el c\u00e1lculo de la sucesi\u00f3n de Fibonacci y c\u00f3mo la corregirlos mediante programaci\u00f3n din\u00e1mica.<\/p>\n<p>A continuaci\u00f3n, se vi\u00f3 la implementaci\u00f3n del patr\u00f3n de programaci\u00f3n din\u00e1mica en Haskell y se aplic\u00f3 el patr\u00f3n a la sucesi\u00f3n de Fibonacci lo que permiti\u00f3 comprobar experimentalmente la ganancia en eficiencia respecto de la soluci\u00f3n mediante divide y vencer\u00e1s.<\/p>\n<p>Finalmente, se aplic\u00f3 el patr\u00f3n de programaci\u00f3n din\u00e1mica a la resoluci\u00f3n del <a href=\"http:\/\/en.wikipedia.org\/wiki\/Matrix_chain_multiplication\">problema del producto de cadenas de matrices<\/a> (en ingl\u00e9s, \u201cmatrix chain multiplication\u201d) que consiste en dada una sucesi\u00f3n de matrices encontrar la manera de multiplicarlas usando el menor n\u00famero de productos de elementos.<\/p>\n<p>Las transparencias usadas en la clase son las p\u00e1ginas 1-39 del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\/temas\/tema-24t.pdf\">tema 24<\/a>:<br \/>\n<!--more--><br \/>\n<div class=\"jetpack-video-wrapper\"><iframe src='https:\/\/www.slideshare.net\/slideshow\/embed_code\/8176465' width='1290' height='1057' sandbox=\"allow-popups allow-scripts allow-same-origin allow-presentation\" allowfullscreen webkitallowfullscreen mozallowfullscreen><\/iframe><\/div><\/p>\n<p>El c\u00f3digo se encuentra en<\/p>\n<ul>\n<li><a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\/codigos\/Dinamica.hs\">Dinamica<\/a>: Patr\u00f3n de la programaci\u00f3n din\u00e1mica.<\/li>\n<li><a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\/codigos\/Fibonacci.hs\">Fibonacci<\/a>: Fibonacci como ejemplo de programaci\u00f3n din\u00e1mica.<\/li>\n<li><a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\/codigos\/ProductoDeCadenaDeMatrices.hs\">ProductoDeCadenaDeMatrices<\/a>: Producto de cadenas de matrices.<\/li>\n<\/ul>\n<p>y las librer\u00edas auxiliares est\u00e1n en el directorio de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\/codigos\">c\u00f3digos<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos estudiado el patr\u00f3n de programaci\u00f3n din\u00e1mica en Haskell. Comenzamos la clase analizando los inconvenientes de la t\u00e9cnica del divide y vencer\u00e1s en el c\u00e1lculo de la sucesi\u00f3n de Fibonacci y c\u00f3mo la corregirlos mediante programaci\u00f3n din\u00e1mica. A continuaci\u00f3n, se vi\u00f3 la&#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":[133],"tags":[287],"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\/1406"}],"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=1406"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1406\/revisions"}],"predecessor-version":[{"id":1408,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1406\/revisions\/1408"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}