I1M2015: Ejercicios del cifrado César (1)
En la segunda parte de la clase de hoy del curso de Informática de 1º del Grado en Matemáticas se han comentado las soluciones de los 5 primeros ejercicios de la 4ª relación sobre el cifrado César.
Los ejercicios y su solución se muestran a continuación
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 |
-- --------------------------------------------------------------------- -- Introducción -- -- --------------------------------------------------------------------- -- En el tema 5, cuyas transparencias se encuentran en -- http://www.cs.us.es/~jalonso/cursos/i1m-15/temas/tema-5.pdf -- se estudió, como aplicación de las definiciones por comprennsión, el -- cifrado César. El objetivo de esta relación es modificar el programa -- de cifrado César para que pueda utilizar también letras -- mayúsculas. Por ejemplo, -- ghci> descifra "Ytit Ufwf Sfif" -- "Todo Para Nada" -- Para ello, se propone la modificación de las funciones correspondientes -- del tema 5. -- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Data.Char import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- minuscula2int :: Char -> Int -- tal que (minuscula2int c) es el entero correspondiente a la letra -- minúscula c. Por ejemplo, -- minuscula2int 'a' == 0 -- minuscula2int 'd' == 3 -- minuscula2int 'z' == 25 -- --------------------------------------------------------------------- minuscula2int :: Char -> Int minuscula2int c = ord c - ord 'a' -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- mayuscula2int :: Char -> Int -- tal que (mayuscula2int c) es el entero correspondiente a la letra -- mayúscula c. Por ejemplo, -- mayuscula2int 'A' == 0 -- mayuscula2int 'D' == 3 -- mayuscula2int 'Z' == 25 -- --------------------------------------------------------------------- mayuscula2int :: Char -> Int mayuscula2int c = ord c - ord 'A' -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- int2minuscula :: Int -> Char -- tal que (int2minuscula n) es la letra minúscula correspondiente al -- entero n. Por ejemplo, -- int2minuscula 0 == 'a' -- int2minuscula 3 == 'd' -- int2minuscula 25 == 'z' -- --------------------------------------------------------------------- int2minuscula :: Int -> Char int2minuscula n = chr (ord 'a' + n) -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la función -- int2mayuscula :: Int -> Char -- tal que (int2mayuscula n) es la letra minúscula correspondiente al -- entero n. Por ejemplo, -- int2mayuscula 0 == 'A' -- int2mayuscula 3 == 'D' -- int2mayuscula 25 == 'Z' -- --------------------------------------------------------------------- int2mayuscula :: Int -> Char int2mayuscula n = chr (ord 'A' + n) -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- desplaza :: Int -> Char -> Char -- tal que (desplaza n c) es el carácter obtenido desplazando n -- caracteres el carácter c. Por ejemplo, -- desplaza 3 'a' == 'd' -- desplaza 3 'y' == 'b' -- desplaza (-3) 'd' == 'a' -- desplaza (-3) 'b' == 'y' -- desplaza 3 'A' == 'D' -- desplaza 3 'Y' == 'B' -- desplaza (-3) 'D' == 'A' -- desplaza (-3) 'B' == 'Y' -- --------------------------------------------------------------------- desplaza :: Int -> Char -> Char desplaza n c | elem c ['a'..'z'] = int2minuscula ((minuscula2int c+n) `mod` 26) | elem c ['A'..'Z'] = int2mayuscula ((mayuscula2int c+n) `mod` 26) | otherwise = c -- --------------------------------------------------------------------- -- Ejercicio 6.1. Definir la función -- codifica :: Int -> String -> String -- tal que (codifica n xs) es el resultado de codificar el texto xs con -- un desplazamiento n. Por ejemplo, -- ghci> codifica 3 "En Todo La Medida" -- "Hq Wrgr Od Phglgd" -- ghci> codifica (-3) "Hq Wrgr Od Phglgd" -- "En Todo La Medida" -- --------------------------------------------------------------------- codifica :: Int -> String -> String codifica n xs = undefined -- --------------------------------------------------------------------- -- Ejercicio 6.2. Comprobar con QuickCheck que para cualquier entero n y -- cualquier cadena cs se tiene que (codifica (-n) (codifica n cs)) es -- igual a cs. -- --------------------------------------------------------------------- -- La propiedad es prop_codifica :: Int -> String -> Bool prop_codifica n cs = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 7. Definir la función -- tabla :: [Float] -- tal que tabla es la lista de la frecuencias de las letras en -- castellano, Por ejemplo, la frecuencia de la 'a' es del 12.53%, la de -- la 'b' es 1.42%. -- --------------------------------------------------------------------- tabla :: [Float] tabla = [12.53, 1.42, 4.68, 5.86, 13.68, 0.69, 1.01, 0.70, 6.25, 0.44, 0.01, 4.97, 3.15, 6.71, 8.68, 2.51, 0.88, 6.87, 7.98, 4.63, 3.93, 0.90, 0.02, 0.22, 0.90, 0.52] -- --------------------------------------------------------------------- -- Ejercicio 8. Definir la función -- porcentaje :: Int -> Int -> Float -- tal que (porcentaje n m) es el porcentaje de n sobre m. Por ejemplo, -- porcentaje 2 5 == 40.0 -- --------------------------------------------------------------------- porcentaje :: Int -> Int -> Float porcentaje n m = undefined -- --------------------------------------------------------------------- -- Ejercicio 9. Definir la función -- letras :: String -> String -- tal que (letras xs) es la cadena formada por las letras de la cadena -- xs. Por ejemplo, -- letras "Esto Es Una Prueba" == "EstoEsUnaPrueba" -- --------------------------------------------------------------------- letras :: String -> String letras xs = undefined -- --------------------------------------------------------------------- -- Ejercicio 10.1. Definir la función -- ocurrencias :: Eq a => a -> [a] -> Int -- tal que (ocurrencias x xs) es el número de veces que ocurre el -- elemento x en la lista xs. Por ejemplo, -- ocurrencias 'a' "Salamanca" == 4 -- --------------------------------------------------------------------- ocurrencias :: Eq a => a -> [a] -> Int ocurrencias x xs = undefined -- --------------------------------------------------------------------- -- Ejercicio 10.2. Comprobar con QuickCheck si el número de ocurrencias -- de un elemento x en una lista xs es igual que en su inversa. -- --------------------------------------------------------------------- -- La propiedad es prop_ocurrencia_inv :: Int -> [Int] -> Bool prop_ocurrencia_inv x xs = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 10.3. Comprobar con QuickCheck si el número de ocurrencias -- de un elemento x en la concatenación de las listas xs e ys es igual a -- la suma del número de ocurrencias de x en xs y en ys. -- --------------------------------------------------------------------- -- La propiedad es prop_ocurrencia_conc :: Int -> [Int] -> [Int] -> Bool prop_ocurrencia_conc x xs ys = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 12. Definir la función -- frecuencias :: String -> [Float] -- tal que (frecuencias xs) es la frecuencia de cada una de las letras -- de la cadena xs. Por ejemplo, -- ghci> frecuencias "En Todo La Medida" -- [14.3,0,0,21.4,14.3,0,0,0,7.1,0,0,7.1, -- 7.1,7.1,14.3,0,0,0,0,7.1,0,0,0,0,0,0] -- Nota: Se puede usar la función toLower (ver http://bit.ly/1vSxhhd ) -- --------------------------------------------------------------------- frecuencias :: String -> [Float] frecuencias xs = undefined -- --------------------------------------------------------------------- -- Ejercicio 13.1. Definir la función -- chiCuad :: [Float] -> [Float] -> Float -- tal que (chiCuad os es) es la medida chi cuadrado de las -- distribuciones os y es. Por ejemplo, -- chiCuad [3,5,6] [3,5,6] == 0.0 -- chiCuad [3,5,6] [5,6,3] == 3.9666667 -- --------------------------------------------------------------------- chiCuad :: [Float] -> [Float] -> Float chiCuad os es = sum [((o-e)^2)/e | (o,e) <- zip os es] -- --------------------------------------------------------------------- -- Ejercicio 13.2, Comprobar con QuickCheck que para cualquier par de -- listas xs e ys se verifica que (chiCuad xs ys) es 0 syss xs e ys son -- iguales. -- --------------------------------------------------------------------- -- La propiedad es prop_chiCuad_1 :: [Float] -> [Float] -> Bool prop_chiCuad_1 xs ys = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 13.3. A la vista de los contraejemplos del apartado -- anterior, qué condición hay que añadir para que se verifique la -- propiedad. -- --------------------------------------------------------------------- -- La propiedad es prop_chiCuad_2 :: [Float] -> [Float] -> Property prop_chiCuad_2 xs ys = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 13.3. A la vista del apartado anterior, el número de tests -- que ha pasado puede ser menor que 100. Reescribir la propiedad de -- forma que se verifique en los 100 tests. -- --------------------------------------------------------------------- -- La propiedad es prop_chiCuad_3 :: [Float] -> [Float] -> Bool prop_chiCuad_3 xs ys = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 14.1. Definir la función -- rota :: Int -> [a] -> [a] -- tal que (rota n xs) es la lista obtenida rotando n posiciones los -- elementos de la lista xs. Por ejemplo, -- rota 2 "manolo" == "noloma" -- rota 10 "manolo" == "lomano" -- [rota n "abc" | n <- [0..5]] == ["abc","bca","cab","abc","bca","cab"] -- --------------------------------------------------------------------- rota :: Int -> [a] -> [a] rota n xs = undefined -- --------------------------------------------------------------------- -- Ejercicio 14.2. Comprobar con QuickCkeck si para cualquier lista xs -- si se rota n veces y el resultado se rota m veces se obtiene lo mismo -- que rotando xs (n+m) veces, donde n y m son números no nulos. -- --------------------------------------------------------------------- -- La propiedad es prop_rota :: Int -> Int -> [Int] -> Property prop_rota n m xs = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 15.1. Definir la función -- descifra :: String -> String -- tal que (descifra xs) es la cadena obtenida descodificando la cadena -- xs por el anti-desplazamiento que produce una distribución de letras -- con la menor deviación chi cuadrado respecto de la tabla de -- distribución de las letras en castellano. Por ejemplo, -- ghci> codifica 5 "Todo Para Nada" -- "Ytit Ufwf Sfif" -- ghci> descifra "Ytit Ufwf Sfif" -- "Todo Para Nada" -- --------------------------------------------------------------------- descifra :: String -> String descifra xs = undefined |