{"id":1392,"date":"2011-05-23T12:43:12","date_gmt":"2011-05-23T12:43:12","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1392"},"modified":"2011-06-01T16:23:06","modified_gmt":"2011-06-01T16:23:06","slug":"i1m2010-7%c2%ba-examen-de-la-evaluacion-continua","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2010-7%c2%ba-examen-de-la-evaluacion-continua\/","title":{"rendered":"I1M2010: 7\u00ba examen de la evaluacion continua"},"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> se ha realizado el 7\u00ba examen de la evaluaci\u00f3n continua.<\/p>\n<p>\nA continuaci\u00f3n se muestra el examen junto con su soluci\u00f3n:<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- Inform\u00e1tica (1\u00ba del Grado en Matem\u00e1ticas)\r\n-- 7\u00ba examen (23 de mayo de 2011)\r\n-- ---------------------------------------------------------------------\r\n \r\nimport Data.Array\r\nimport GrafoConVectorDeAdyacencia\r\nimport RecorridoEnAnchura\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. [2.5 puntos] Se considera que los puntos del plano se\r\n-- representan por pares de n\u00fameros como se indica a continuaci\u00f3n\r\n--    type Punto = (Double,Double) \r\n-- Definir la funci\u00f3n \r\n--    cercanos :: [Punto] -> [Punto] -> (Punto,Punto)\r\n-- tal que (cercanos ps qs) es un par de puntos, el primero de ps y el\r\n-- segundo de qs, que son los m\u00e1s cercanos (es decir, no hay otro par\r\n-- (p\u00b4,q') con p' en ps y q' en qs tales que la distancia entre p' y q'\r\n-- sea menor que la que hay entre p y q). Por ejemplo,\r\n--    ghci> cercanos [(2,5),(3,6)] [(4,3),(1,0),(7,9)]\r\n--    ((2.0,5.0),(4.0,3.0))\r\n-- ---------------------------------------------------------------------\r\n\r\ntype Punto = (Double,Double) \r\n\r\ncercanos :: [Punto] -> [Punto] -> (Punto,Punto)\r\ncercanos ps qs = (p,q)\r\n    where (d,p,q) = minimum [(distancia p q, p, q) | p <- ps, q <-qs]\r\n          distancia (x,y) (u,v) = sqrt ((x-u)^2+(y-v)^2)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. [2.5] Las relaciones binarias pueden representarse\r\n-- mediante conjuntos de pares de elementos. Definir la funci\u00f3n\r\n--    simetrica :: Eq a => [(a,a)] -> Bool\r\n-- tal que (simetrica r) se verifica si la relaci\u00f3n binaria r es\r\n-- sim\u00e9trica. Por ejemplo,\r\n--    simetrica [(1,3),(2,5),(3,1),(5,2)]  ==  True\r\n--    simetrica [(1,3),(2,5),(3,1),(5,3)]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nsimetrica :: Eq a => [(a,a)] -> Bool\r\nsimetrica [] = True\r\nsimetrica ((x,y):r) \r\n    | x == y    = True\r\n    | otherwise = elem (y,x) r && simetrica (borra (y,x) r)\r\n\r\nborra :: Eq a => a -> [a] -> [a]\r\nborra x ys = [y | y <- ys, y \/= x] \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. [2.5 puntos] Un grafo no dirigido G se dice conexo, si\r\n-- para cualquier par de v\u00e9rtices u y v en G, existe al menos una\r\n-- trayectoria (una sucesi\u00f3n de v\u00e9rtices adyacentes) de u a v. Definir\r\n-- la funci\u00f3n \r\n--    conexo :: (Ix a, Num p) => Grafo a p -> Bool\r\n-- tal que (conexo g) se verifica si el grafo g es conexo. Por ejemplo, \r\n--    conexo (creaGrafo False (1,3) [(1,2,0),(3,2,0)])  ==  True\r\n--    conexo (creaGrafo False (1,4) [(1,2,0),(3,4,0)])  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nconexo :: (Ix a, Num p) => Grafo a p -> Bool\r\nconexo g = length (recorridoEnAnchura i g) == n\r\n    where xs = nodos g\r\n          i  = head xs\r\n          n  = length xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. [2.5 puntos Se consideran los tipos de los vectores y\r\n-- de las matrices definidos por\r\n--    type Vector a = Array Int a\r\n--    type Matriz a = Array (Int,Int) a\r\n-- y, como ejemplo, la matriz q definida por\r\n--    q :: Matriz Int\r\n--    q = array ((1,1),(2,2)) [((1,1),1),((1,2),1),((2,1),1),((2,2),0)] \r\n-- Definir la funci\u00f3n\r\n--    potencia :: Num a => Matriz a -> Int -> Matriz a\r\n-- tal que (potencia p n) es la potencia n-\u00e9sima de la matriz cuadrada\r\n-- p. Por ejemplo,\r\n--    ghci> potencia q 2\r\n--    array ((1,1),(2,2)) [((1,1),2),((1,2),1),((2,1),1),((2,2),1)]\r\n--    ghci> potencia q 3\r\n--    array ((1,1),(2,2)) [((1,1),3),((1,2),2),((2,1),2),((2,2),1)]\r\n--    ghci> potencia q 4\r\n--    array ((1,1),(2,2)) [((1,1),5),((1,2),3),((2,1),3),((2,2),2)]\r\n-- \u00bfQu\u00e9 relaci\u00f3n hay entre las potencias de la matriz q y la sucesi\u00f3n de\r\n-- Fibonacci? \r\n-- ---------------------------------------------------------------------\r\n\r\ntype Vector a = Array Int a\r\ntype Matriz a = Array (Int,Int) a\r\n\r\nq :: Matriz Int\r\nq = array ((1,1),(2,2)) [((1,1),1),((1,2),1),((2,1),1),((2,2),0)] \r\n\r\npotencia :: Num a => Matriz a -> Int -> Matriz a\r\npotencia p 0 = identidad (numFilas p)\r\npotencia p (n+1) = prodMatrices p (potencia p n)\r\n\r\nidentidad :: Num a => Int -> Matriz a\r\nidentidad n =     \r\n    array ((1,1),(n,n))\r\n          [((i,j),f i j) | i <- [1..n], j <- [1..n]]\r\n    where f i j | i == j    = 1\r\n                | otherwise = 0\r\n\r\n-- (prodEscalar v1 v2) es el producto escalar de los vectores v1\r\n-- y v2.\r\nprodEscalar :: Num a => Vector a -> Vector a -> a\r\nprodEscalar v1 v2 = \r\n    sum [i*j | (i,j) <- zip (elems v1) (elems v2)]\r\n\r\n-- (filaMat i p) es el vector correspondiente a la fila i-\u00e9sima\r\n-- de la matriz p.\r\nfilaMat :: Num a => Int -> Matriz a -> Vector a\r\nfilaMat i p = array (1,n) [(j,p!(i,j)) | j <- [1..n]]\r\n    where n = numColumnas p\r\n\r\n-- (columnaMat j p) es el vector correspondiente a la columna\r\n-- j-\u00e9sima de la matriz p.\r\ncolumnaMat :: Num a => Int -> Matriz a -> Vector a\r\ncolumnaMat j p = array (1,m) [(i,p!(i,j)) | i <- [1..m]]\r\n    where m = numFilas p\r\n\r\n-- (numFilas m) es el n\u00famero de filas de la matriz m.\r\nnumFilas :: Num a => Matriz a -> Int\r\nnumFilas = fst . snd . bounds\r\n\r\n-- (numColumnas m) es el n\u00famero de columnas de la matriz\r\n-- m.\r\nnumColumnas:: Num a => Matriz a -> Int\r\nnumColumnas = snd . snd . bounds\r\n\r\n-- (prodMatrices p q) es el producto de las matrices p y q.\r\nprodMatrices :: Num a => Matriz a -> Matriz a -> Matriz a\r\nprodMatrices p q = \r\n    array ((1,1),(m,n))\r\n          [((i,j), prodEscalar (filaMat i p) (columnaMat j q)) |\r\n           i <- [1..m], j <- [1..n]]\r\n    where m = numFilas p\r\n          n = numColumnas q\r\n\r\n-- Los sucesi\u00f3n de Fibonacci es 0,1,1,2,3,5,8,13,... Se observa que los\r\n-- elementeos de (potencia q n) son los t\u00e9mninos de la sucesi\u00f3n en los\r\n-- lugares n+1, n, n y n-1.\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se ha realizado el 7\u00ba examen de la evaluaci\u00f3n continua. A continuaci\u00f3n se muestra el examen junto con su soluci\u00f3n:<\/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\/1392"}],"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=1392"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1392\/revisions"}],"predecessor-version":[{"id":1398,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1392\/revisions\/1398"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1392"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1392"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1392"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}