{"id":1564,"date":"2011-09-16T14:24:29","date_gmt":"2011-09-16T14:24:29","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1564"},"modified":"2011-09-24T14:27:45","modified_gmt":"2011-09-24T14:27:45","slug":"i1m2010-examen-de-septiembre-de-2011","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2010-examen-de-septiembre-de-2011\/","title":{"rendered":"I1M2010: Examen de septiembre de 2011"},"content":{"rendered":"

Hoy de se ha realizado el examen de la convocatoria de septiembre de la asignatura de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a>.<\/p>\n

\nA continuaci\u00f3n se muestra el examen junto con su soluci\u00f3n:
\n<\/p>\n

\r\n-- Inform\u00e1tica (1\u00ba del Grado en Matem\u00e1ticas)\r\n-- Examen del 16 de septiembre de 2011\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.List\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. [2 puntos] Definir la funci\u00f3n\r\n--    subsucesiones :: [Integer] -> [[Integer]]\r\n-- tal que (subsucesiones xs) es la lista de las subsucesiones\r\n-- crecientes de elementos consecutivos de xs. Por ejemplo, \r\n--    subsucesiones [1,0,1,2,3,0,4,5]  == [[1],[0,1,2,3],[0,4,5]]\r\n--    subsucesiones [5,6,1,3,2,7]      == [[5,6],[1,3],[2,7]]\r\n--    subsucesiones [2,3,3,4,5]        == [[2,3],[3,4,5]]\r\n--    subsucesiones [7,6,5,4]          == [[7],[6],[5],[4]]\r\n-- ---------------------------------------------------------------------\r\n \r\nsubsucesiones :: [Integer] -> [[Integer]]\r\nsubsucesiones []  = []\r\nsubsucesiones [x] = [[x]]\r\nsubsucesiones (x:y:zs)\r\n    | x < y     = (x:us):vss\r\n    | otherwise = [x]:p\r\n    where p@(us:vss) = subsucesiones (y:zs)\r\n \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. [2 puntos] Definir la funci\u00f3n\r\n--    menor :: Ord a => [[a]] -> a\r\n-- tal que (menor xss) es el menor elemento com\u00fan a todas las listas de\r\n-- xss, donde las listas de xss est\u00e1n ordenadas (de menor a mayor) y\r\n-- pueden ser infinitas. Por ejemplo,\r\n--    menor [[3,4,5]]                           ==  3\r\n--    menor [[1,2,3,4,5,6,7],[0.5,3\/2,4,19]]    ==  4.0\r\n--    menor [[0..],[4,6..],[2,3,5,7,11,13,28]]  ==  28\r\n-- ---------------------------------------------------------------------\r\n \r\nmenor :: Ord a => [[a]] -> a\r\nmenor (xs:xss) = \r\n    head [x | x <- xs, all (x `pertenece`) xss] \r\n\r\n-- (pertenece x ys) se verifica si x pertenece a la lista ys, donde ys\r\n-- es una lista ordenada de menor a mayor y, posiblemente, infinita. Por\r\n-- ejemplo, \r\n--    pertenece 6 [0,2..]  ==  True\r\n--    pertenece 7 [0,2..]  ==  False\r\npertenece :: Ord a => a -> [a] -> Bool\r\npertenece x [] = False\r\npertenece x (y:ys) | x < y  = False\r\n                   | x == y = True\r\n                   | x > y  = pertenece x ys\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. [2 puntos] Un conjunto A est\u00e1 cerrado respecto de una\r\n-- funci\u00f3n  f si para todo elemento x de A se tiene que f(x) pertenece a\r\n-- A. La clausura de un conjunto B respecto de una funci\u00f3n f es el menor \r\n-- conjunto A que contiene a B y es cerrado respecto de f. Por ejemplo,\r\n-- la clausura de {0,1,2] respecto del opuesto es {0,1,2,-1,-2}.\r\n-- \r\n-- Definir la funci\u00f3n  \r\n--    clausura :: Eq a => (a -> a) -> [a] -> [a]\r\n-- tal que (clausura f xs) es la clausura de xs respecto de f. Por\r\n-- ejemplo, \r\n--    clausura (\\x -> -x) [0,1,2]         ==  [0,1,2,-1,-2]\r\n--    clausura (\\x -> (x+1) `mod` 5) [0]  ==  [0,1,2,3,4]\r\n-- ---------------------------------------------------------------------\r\n\r\nclausura :: Eq a => (a -> a) -> [a] -> [a]\r\nclausura f xs = clausura' f xs xs\r\n    where clausura' f xs ys | null zs = ys\r\n                            | otherwise = clausura' f zs (ys++zs)\r\n              where zs = nuevosSucesores f xs ys\r\n\r\nnuevosSucesores :: Eq a => (a -> a) -> [a] -> [a] -> [a]\r\nnuevosSucesores f xs ys = nub ([f x | x <- xs]) \\\\ ys\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. [2 puntos] El problema del laberinto num\u00e9rico consiste\r\n-- en dados un par de n\u00fameros, encontrar la longitud del camino m\u00e1s\r\n-- corto entre ellos usando s\u00f3lo las siguientes operaciones:\r\n--    * multiplicar por 2,\r\n--    * dividir por 2 (s\u00f3lo para los pares) y\r\n--    * sumar 2.\r\n-- Por ejemplo,\r\n--    longitudCaminoMinimo 3 12  ==  2\r\n--    longitudCaminoMinimo 12 3  ==  2\r\n--    longitudCaminoMinimo 9 2   ==  8\r\n--    longitudCaminoMinimo 2 9   ==  5\r\n-- Unos caminos m\u00ednimos correspondientes a los ejemplos anteriores son\r\n-- [3,6,12], [12,6,3], [9,18,20,10,12,6,8,4,2] y [2,4,8,16,18,9].\r\n-- \r\n-- Ejercicio 4.1. Definir la funci\u00f3n\r\n--    orbita :: Int -> [Int] -> [Int]\r\n-- tal que (orbita n xs) es el conjunto de n\u00fameros que se pueden obtener\r\n-- aplicando como m\u00e1ximo n veces las operaciones a los elementos de\r\n-- xs. Por ejemplo, \r\n--    orbita 0 [12]  ==  [12]\r\n--    orbita 1 [12]  ==  [6,12,14,24]\r\n--    orbita 2 [12]  ==  [3,6,7,8,12,14,16,24,26,28,48]\r\n-- ---------------------------------------------------------------------\r\n\r\norbita :: Int -> [Int] -> [Int]\r\norbita 0 xs = sort xs\r\norbita (n+1) xs = sort (nub (ys ++ concat [sucesores x | x <- ys]))\r\n    where ys = orbita n xs\r\n          sucesores x | odd x     = [2*x, x+2]\r\n                      | otherwise = [2*x, x `div` 2, x+2]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4.2. Definir la funci\u00f3n\r\n--    longitudCaminoMinimo :: Int -> Int -> Int\r\n-- tal que (longitudCaminoMinimo x y) es la longitud del camino m\u00ednimo\r\n-- desde x hasta y en el laberinto num\u00e9rico. \r\n-- ---------------------------------------------------------------------\r\n\r\nlongitudCaminoMinimo :: Int -> Int -> Int\r\nlongitudCaminoMinimo x y = \r\n    head [n | n <- [1..], y `elem` (orbita n [x])] \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. [2 puntos] En este ejercicio se estudia las relaciones\r\n-- entre los valores de polinomios y los de sus correspondientes\r\n-- expresiones aritm\u00e9ticas.\r\n-- \r\n-- Ejercicio 5.1. Las expresiones aritm\u00e9ticas construidas con una\r\n-- variables, los n\u00fameros enteros y las operaciones de sumar y\r\n-- multiplicar se pueden representar mediante el tipo de datos Exp\r\n-- definido por   \r\n--    data Exp = Var | Const Int | Sum Exp Exp | Mul Exp  Exp\r\n--               deriving Show\r\n-- Por ejemplo, la expresi\u00f3n 3+5x^2 se puede representar por\r\n--    exp1 :: Exp\r\n--    exp1 = Sum (Const 3) (Mul Var (Mul Var (Const 5)))\r\n-- Definir la funci\u00f3n \r\n--    valorE :: Exp -> Int -> Int\r\n-- tal que (valorE e n) es el valor de la expresi\u00f3n e cuando se\r\n-- sustituye su variable por n. Por ejemplo,\r\n--    valorE exp1 2  ==  23\r\n-- ---------------------------------------------------------------------\r\n \r\ndata Exp = Var | Const Int | Sum Exp Exp | Mul Exp  Exp\r\n           deriving Show\r\n \r\nexp1 :: Exp\r\nexp1 = Sum (Const 3) (Mul Var (Mul Var (Const 5)))\r\n \r\nvalorE :: Exp -> Int -> Int\r\nvalorE Var         n = n\r\nvalorE (Const a)   n = a\r\nvalorE (Sum e1 e2) n = (valorE e1 n) + (valorE e2 n)\r\nvalorE (Mul e1 e2) n = (valorE e1 n) * (valorE e2 n)\r\n \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.2. Los polinomios se pueden representar por la lista de\r\n-- sus coeficientes. Por ejemplo, el polinomio 3+5x^2 se puede\r\n-- representar por [3,0,5].  \r\n-- \r\n-- Definir la funci\u00f3n\r\n--    expresion :: [Int] -> Exp\r\n-- tal que (expresion p) es una expresi\u00f3n aritm\u00e9tica equivalente al\r\n-- polinomio p. Por ejemplo,\r\n--    ghci> expresion [3,0,5]\r\n--    Sum (Const 3) (Mul Var (Sum (Const 0) (Mul Var (Const 5))))\r\n-- ---------------------------------------------------------------------\r\n \r\nexpresion :: [Int] -> Exp\r\nexpresion [a]   = Const a\r\nexpresion (a:p) = Sum (Const a) (Mul Var (expresion p))\r\n \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.3. Definir la funci\u00f3n\r\n--    valorP :: [Int] -> Int -> Int\r\n-- tal que (valorP p n) es el valor del polinomio p cuando se sustituye\r\n-- su variable por n. Por ejemplo,\r\n--    valorP [3,0,5] 2  ==  23\r\n-- ---------------------------------------------------------------------\r\n \r\nvalorP :: [Int] -> Int -> Int\r\nvalorP [a] _ = a\r\nvalorP (a:p) n = a + n * valorP p n\r\n \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.4. Comprobar con QuickCheck que, para todo polinomio p y\r\n-- todo entero n,\r\n--    valorP p n == valorE (expresion p) n\r\n-- ---------------------------------------------------------------------\r\n \r\n-- La propiedad es\r\nprop_valor :: [Int] -> Int -> Property\r\nprop_valor p n =\r\n    not (null p) ==> \r\n    valorP p n == valorE (expresion p) n\r\n \r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_valor\r\n--    +++ OK, passed 100 tests.\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Hoy de se ha realizado el examen de la convocatoria de septiembre de la asignatura de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas. 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\/1564"}],"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=1564"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1564\/revisions"}],"predecessor-version":[{"id":1567,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1564\/revisions\/1567"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1564"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1564"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1564"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}