{"id":5121,"date":"2015-10-23T14:43:47","date_gmt":"2015-10-23T12:43:47","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5121"},"modified":"2015-10-23T14:43:47","modified_gmt":"2015-10-23T12:43:47","slug":"i1m2015-ejercicios-del-cifrado-cesar","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-ejercicios-del-cifrado-cesar\/","title":{"rendered":"I1M2015: Ejercicios del cifrado C\u00e9sar"},"content":{"rendered":"<p>En la primera parte de la clase de hoy del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han comentado las soluciones de los ejercicios de la 4\u00aa relaci\u00f3n sobre el cifrado C\u00e9sar.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- En el tema 5, cuyas transparencias se encuentran en \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/temas\/tema-5.pdf\n-- se estudi\u00f3, como aplicaci\u00f3n de las definiciones por comprennsi\u00f3n, el\n-- cifrado C\u00e9sar. El objetivo de esta relaci\u00f3n es modificar el programa\n-- de cifrado C\u00e9sar para que pueda utilizar tambi\u00e9n letras\n-- may\u00fasculas. Por ejemplo,  \n--    ghci> descifra \"Ytit Ufwf Sfif\"\n--    \"Todo Para Nada\"\n-- Para ello, se propone la modificaci\u00f3n de las funciones correspondientes\n-- del tema 5.\n\n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas auxiliares                                --\n-- ---------------------------------------------------------------------\n\nimport Data.Char\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    minuscula2int :: Char -> Int\n-- tal que (minuscula2int c) es el entero correspondiente a la letra\n-- min\u00fascula c. Por ejemplo, \n--    minuscula2int 'a'  ==  0\n--    minuscula2int 'd'  ==  3\n--    minuscula2int 'z'  ==  25\n-- ---------------------------------------------------------------------\n\nminuscula2int :: Char -> Int\nminuscula2int c = ord c - ord 'a'\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    mayuscula2int :: Char -> Int\n-- tal que (mayuscula2int c) es el entero correspondiente a la letra\n-- may\u00fascula c. Por ejemplo, \n--    mayuscula2int 'A'  ==  0\n--    mayuscula2int 'D'  ==  3\n--    mayuscula2int 'Z'  ==  25\n-- ---------------------------------------------------------------------\n\nmayuscula2int :: Char -> Int\nmayuscula2int c = ord c - ord 'A'\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    int2minuscula :: Int -> Char\n-- tal que (int2minuscula n) es la letra min\u00fascula correspondiente al\n-- entero n. Por ejemplo, \n--    int2minuscula 0   ==  'a'\n--    int2minuscula 3   ==  'd'\n--    int2minuscula 25  ==  'z'\n-- ---------------------------------------------------------------------\n\nint2minuscula :: Int -> Char\nint2minuscula n = chr (ord 'a' + n)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    int2mayuscula :: Int -> Char\n-- tal que (int2mayuscula n) es la letra min\u00fascula correspondiente al\n-- entero n. Por ejemplo, \n--    int2mayuscula 0   ==  'A'\n--    int2mayuscula 3   ==  'D'\n--    int2mayuscula 25  ==  'Z'\n-- ---------------------------------------------------------------------\n\nint2mayuscula :: Int -> Char\nint2mayuscula n = chr (ord 'A' + n)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    desplaza :: Int -> Char -> Char\n-- tal que (desplaza n c) es el car\u00e1cter obtenido desplazando n\n-- caracteres el car\u00e1cter c. Por ejemplo, \n--    desplaza   3  'a'  ==  'd'\n--    desplaza   3  'y'  ==  'b'\n--    desplaza (-3) 'd'  ==  'a'\n--    desplaza (-3) 'b'  ==  'y'\n--    desplaza   3  'A'  ==  'D'\n--    desplaza   3  'Y'  ==  'B'\n--    desplaza (-3) 'D'  ==  'A'\n--    desplaza (-3) 'B'  ==  'Y'\n-- ---------------------------------------------------------------------\n\ndesplaza :: Int -> Char -> Char\ndesplaza n c \n    | elem c ['a'..'z'] = int2minuscula ((minuscula2int c+n) `mod` 26)\n    | elem c ['A'..'Z'] = int2mayuscula ((mayuscula2int c+n) `mod` 26)\n    | otherwise         = c\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.1. Definir la funci\u00f3n\n--    codifica :: Int -> String -> String\n-- tal que (codifica n xs) es el resultado de codificar el texto xs con\n-- un desplazamiento n. Por ejemplo, \n--    ghci> codifica   3  \"En Todo La Medida\" \n--    \"Hq Wrgr Od Phglgd\"\n--    ghci> codifica (-3) \"Hq Wrgr Od Phglgd\"\n--    \"En Todo La Medida\"\n-- ---------------------------------------------------------------------\n\ncodifica :: Int -> String -> String\ncodifica n xs = [desplaza n x | x <- xs]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.2. Comprobar con QuickCheck que para cualquier entero n y\n-- cualquier cadena cs se tiene que (codifica (-n) (codifica n cs)) es\n-- igual a cs.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_codifica :: Int -> String -> Bool\nprop_codifica n cs =\n    codifica (-n) (codifica n cs) == cs\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_codifica\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    tabla :: [Float]\n-- tal que tabla es la lista de la frecuencias de las letras en\n-- castellano, Por ejemplo, la frecuencia de la 'a' es del 12.53%, la de\n-- la 'b' es 1.42%. \n-- ---------------------------------------------------------------------\n\ntabla :: [Float]\ntabla = [12.53, 1.42, 4.68, 5.86, 13.68, 0.69, 1.01, \n          0.70, 6.25, 0.44, 0.01,  4.97, 3.15, 6.71, \n          8.68, 2.51, 0.88, 6.87,  7.98, 4.63, 3.93, \n          0.90, 0.02, 0.22, 0.90,  0.52]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    porcentaje :: Int -> Int -> Float\n-- tal que (porcentaje n m) es el porcentaje de n sobre m. Por ejemplo,\n--    porcentaje 2 5  ==  40.0  \n-- ---------------------------------------------------------------------\n\nporcentaje :: Int -> Int -> Float\nporcentaje n m = (fromIntegral n \/ fromIntegral m) * 100\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n\n--    letras :: String -> String\n-- tal que (letras xs) es la cadena formada por las letras de la cadena\n-- xs. Por ejemplo,  \n--    letras \"Esto Es Una Prueba\"  ==  \"EstoEsUnaPrueba\"\n-- ---------------------------------------------------------------------\n\nletras :: String -> String\nletras xs = [x | x <- xs, elem x (['a'..'z']++['A'..'Z'])]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10.1. Definir la funci\u00f3n\n--    ocurrencias :: Eq a => a -> [a] -> Int\n-- tal que (ocurrencias x xs) es el n\u00famero de veces que ocurre el\n-- elemento x en la lista xs. Por ejemplo, \n--    ocurrencias 'a' \"Salamanca\"  ==  4  \n-- ---------------------------------------------------------------------\n\nocurrencias :: Eq a => a -> [a] -> Int\nocurrencias x xs = length [x' | x' <- xs, x == x']  \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10.2. Comprobar con QuickCheck si el n\u00famero de ocurrencias\n-- de un elemento x en una lista xs es igual que en su inversa.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es \nprop_ocurrencia_inv :: Int -> [Int] -> Bool\nprop_ocurrencia_inv x xs =\n    ocurrencias x xs == ocurrencias x (reverse xs)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_ocurrencia_inv\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10.3. Comprobar con QuickCheck si el n\u00famero de ocurrencias\n-- de un elemento x en la concatenaci\u00f3n de las listas xs e ys es igual a\n-- la suma del n\u00famero de ocurrencias de x en xs y en ys.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_ocurrencia_conc :: Int -> [Int] -> [Int] -> Bool\nprop_ocurrencia_conc x xs ys =\n    ocurrencias x (xs++ys) == ocurrencias x xs + ocurrencias x ys\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_ocurrencia_conc\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    frecuencias :: String -> [Float]\n-- tal que (frecuencias xs) es la frecuencia de cada una de las letras\n-- de la cadena xs. Por ejemplo, \n--    ghci> frecuencias \"En Todo La Medida\"\n--    [14.3,0,0,21.4,14.3,0,0,0,7.1,0,0,7.1,\n--     7.1,7.1,14.3,0,0,0,0,7.1,0,0,0,0,0,0]\n-- ---------------------------------------------------------------------\n\nfrecuencias :: String -> [Float]\nfrecuencias xs = \n    [porcentaje (ocurrencias x xs') n | x <- ['a'..'z']]\n    where xs' = [toLower x | x <- xs]\n          n   = length (letras xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13.1. Definir la funci\u00f3n\n--    chiCuad :: [Float] -> [Float] -> Float\n-- tal que (chiCuad os es) es la medida chi cuadrado de las\n-- distribuciones os y es. Por ejemplo, \n--    chiCuad [3,5,6] [3,5,6]  ==  0.0\n--    chiCuad [3,5,6] [5,6,3]  ==  3.9666667\n-- ---------------------------------------------------------------------\n\nchiCuad :: [Float] -> [Float] -> Float\nchiCuad os es = sum [((o-e)^2)\/e | (o,e) <- zip os es]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13.2, Comprobar con QuickCheck que para cualquier par de\n-- listas xs e ys se verifica que (chiCuad xs ys) es 0 syss xs e ys son\n-- iguales. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_chiCuad_1 :: [Float] -> [Float] -> Bool\nprop_chiCuad_1 xs ys =\n    (chiCuad xs ys == 0) == (xs == ys)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_chiCuad_1\n--    *** Failed! Falsifiable (after 2 tests and 2 shrinks): \n--    [2.0]\n--    []\n-- En efecto, \n--    ghci> chiCuad [2] [] == 0\n--    True\n--    ghci> [2] == []\n--    False\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13.3. A la vista de los contraejemplos del apartado\n-- anterior, qu\u00e9 condici\u00f3n hay que a\u00f1adir para que se verifique la\n-- propiedad.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_chiCuad_2 :: [Float] -> [Float] -> Property\nprop_chiCuad_2 xs ys =\n    length xs == length ys ==> (chiCuad xs ys == 0) == (xs == ys)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_chiCuad_2\n--    *** Gave up! Passed only 47 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13.3. A la vista del apartado anterior, el n\u00famero de tests\n-- que ha pasado puede ser menor que 100. Reescribir la propiedad de\n-- forma que se verifique en los 100 tests.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_chiCuad_3 :: [Float] -> [Float] -> Bool\nprop_chiCuad_3 xs ys =\n    (chiCuad as bs == 0) == (as == bs)\n    where n  = min (length xs) (length ys)\n          as = take n xs\n          bs = take n ys\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_chiCuad_3\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14.1. Definir la funci\u00f3n\n--    rota :: Int -> [a] -> [a]\n-- tal que (rota n xs) es la lista obtenida rotando n posiciones los\n-- elementos de la lista xs. Por ejemplo, \n--    rota  2 \"manolo\"              ==  \"noloma\"  \n--    rota 10 \"manolo\"              ==  \"lomano\"\n--    [rota n \"abc\" | n <- [0..5]]  ==  [\"abc\",\"bca\",\"cab\",\"abc\",\"bca\",\"cab\"]\n-- ---------------------------------------------------------------------\n\nrota :: Int -> [a] -> [a]\nrota _ [] = []\nrota n xs = drop m xs ++ take m xs\n    where m = n `mod` length xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14.2. Comprobar con QuickCkeck si para cualquier lista xs\n-- si se rota n veces y el resultado se rota m veces se obtiene lo mismo\n-- que rotando xs (n+m) veces, donde n y m son n\u00fameros no nulos.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_rota :: Int -> Int -> [Int] -> Property\nprop_rota n m xs =\n    n \/= 0 && m \/= 0 ==> rota m (rota n xs) == rota (n+m) xs\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_rota\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15.1. Definir la funci\u00f3n\n--    descifra :: String -> String\n-- tal que (descifra xs) es la cadena obtenida descodificando la cadena\n-- xs por el anti-desplazamiento que produce una distribuci\u00f3n de letras\n-- con la menor deviaci\u00f3n chi cuadrado respecto de la tabla de\n-- distribuci\u00f3n de las letras en castellano. Por ejemplo, \n--    ghci> codifica 5 \"Todo Para Nada\"\n--    \"Ytit Ufwf Sfif\"\n--    ghci> descifra \"Ytit Ufwf Sfif\"\n--    \"Todo Para Nada\"\n-- ---------------------------------------------------------------------\n\ndescifra :: String -> String\ndescifra xs =  codifica (-factor) xs\n    where factor = head (posiciones (minimum tabChi) tabChi)\n          tabChi = [chiCuad (rota n tabla') tabla | n <- [0..25]]\n          tabla' = frecuencias xs\n\nposiciones :: Eq a => a -> [a] -> [Int]\nposiciones x xs = \n    [i | (x',i) <- zip xs [0..], x == x']\n<\/pre>\n<p>Al final de la clase se propusieron los siguientes ejercicios de autoevaluaci\u00f3n<\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Test.QuickCheck\nimport Data.Char\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n---   sumaCuadradosImpares :: Integer -> Integer\n-- tal que (sumaCuadradosImpares n) es la suma de los cuadrados de los\n-- n primeros n\u00fameros impares; es decir\n--    1^2 + 3^2 + 5^2 + \u00b7\u00b7\u00b7 + (2n-1)^2\n-- Por ejemplo,\n--    sumaCuadradosImpares 5  ==  165\n-- ---------------------------------------------------------------------\n\nsumaCuadradosImpares :: Integer -> Integer\nsumaCuadradosImpares n = sum [x^2 | x <- [1,3..2*n-1]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Comprobar con QuickCheck que, para cualquier n\u00famero\n-- natural n, (sumaCuadradosImpares n) es igual al cociente \n--    n*(2*n+1)*(2*n-1)\n--    -----------------\n--           3\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_sumaCuadradosImpares :: Integer -> Property\nprop_sumaCuadradosImpares n =\n    n >= 0 ==> sumaCuadradosImpares n == n*(2*n+1)*(2*n-1) `div` 3\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_sumaCuadradosImpares\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--   ocurrencias :: Char -> String -> Int\n-- tal que (ocurrencias x ys) es el n\u00famero de veces que aparece el\n-- car\u00e1cter x en la cadena ys sin distinguir entre may\u00fascula y\n-- min\u00fascula. Por ejemplo,\n--   ocurrencias 'e' \"En todo la medida\"  ==  2\n--   ocurrencias 'E' \"En todo la medida\"  ==  2\n--   ocurrencias 'L' \"En todo la medida\"  ==  1\n-- --------------------------------------------------------------------- \n\nocurrencias :: Char -> String -> Int\nocurrencias x ys = \n    length [y | y <- ys, toLower x == toLower y]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Comprobar con QuickCheck que la suma de las ocurrencias\n-- de cada una de las letras min\u00fasculas (de la 'a' a la 'z') en una\n-- cadena ys es igual a la de las letras may\u00fasculas (de la 'A' a la\n-- 'Z').\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_ocurrencias :: String -> Bool\nprop_ocurrencias ys =\n    sum [ocurrencias x ys | x <- ['a'..'z']] ==     \n    sum [ocurrencias x ys | x <- ['A'..'Z']]\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_ocurrencias\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p>El c\u00f3digo anterior se encuentra tambi\u00e9n en <a href=\"http:\/\/bit.ly\/1jYopE9\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>En la primera parte de la clase de hoy del curso de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han comentado las soluciones de los ejercicios de la 4\u00aa relaci\u00f3n sobre el cifrado C\u00e9sar. Los ejercicios y su soluci\u00f3n se muestran a continuaci\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":[250],"tags":[270,310],"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\/5121"}],"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=5121"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5121\/revisions"}],"predecessor-version":[{"id":5122,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5121\/revisions\/5122"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5121"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5121"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5121"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}