{"id":4526,"date":"2014-10-27T17:41:46","date_gmt":"2014-10-27T16:41:46","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4526"},"modified":"2014-10-28T07:43:27","modified_gmt":"2014-10-28T06:43:27","slug":"i1m2014-ejercicios-del-cifrado-cesar","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-ejercicios-del-cifrado-cesar\/","title":{"rendered":"I1M2014: Ejercicios del cifrado C\u00e9sar"},"content":{"rendered":"<p>En la clase de hoy del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos 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","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy del curso de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos 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":[238],"tags":[270,305,126],"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\/4526"}],"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=4526"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4526\/revisions"}],"predecessor-version":[{"id":4527,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4526\/revisions\/4527"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4526"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4526"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4526"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}