progra




Hoja de Repaso – Listas y cadenas

CC2005 – Semestre I 2013
Facultad de Ingeniería
Departamento de Ciencias de la Computación




Instrucciones
El propósito de esta hoja de trabajo es consolidar y practicar los conceptos adquiridos sobre los temas tratados acerca de listas y cadenas en conjunto con los temas anteriores.

Antecedentes

Criptograma
Un criptograma es unmensaje cifrado cuyo significado resulta ininteligible hasta que es descifrado. Generalmente, el contenido del mensaje inteligible es modificado siguiendo un determinado patrón, de manera que sólo es posible comprender el significado original tras conocer el patrón seguido en el cifrado.
Por lo general, el cifrado utilizado para cifrar el texto es lo suficientemente simple como para que elcriptograma pueda resolverse manualmente. El cifrado más utilizado en estos casos es el llamado cifrado por sustitución, en el que cada letra es remplazada por una diferente o por un número. Para resolver el criptograma, se debe recuperar el alfabeto original utilizado. En sus inicios fue concebido para aplicaciones más serias, pero en la actualidad es utilizado por lo general como entretenimiento enrevistas y diarios.
También se pueden crear criptogramas utilizando otros métodos de cifrado clásico. Por ejemplo, el libro de cifrado, donde un libro o artículo es utilizado para cifrar un mensaje.











Frecuencia de aparición de letras
El cálculo de la frecuencia de letras en una lengua es difícil y está sujeto a la interpretación. Se cuenta la frecuencia de las letras de un textoarbitrariamente largo, pero en los resultados influyen varios parámetros:

1. El estilo narrativo. Si hay muchos verbos en infinitivo, habrá muchas "R".

2. El vocabulario específico del documento. Si se habla de ríos, habrá muchas "Í"; si uno de los protagonistas se llama Wenceslao, aumentará el número de "W".

3. El tipo de documento. En pequeños anuncios se pueden encontrar muchossímbolos de monedas (€, $, Bs, etc), que es posible que estén ausentes en la mayor parte de otro tipo de documentos.

4. En el diccionario de la RAE la letra más frecuente es la A, pero en cualquier texto castellano, la frecuencia de las partículas "que", "el", "se", "me", etc. hace que la "e" sea más frecuente.

5. Los parámetros técnicos. Se pueden calcular fácilmente estadísticas sobre textosinformatizados, pero a menudo, éstos no implican el uso de mayúsculas acentuadas (que a veces resultan complicadas de teclear). Además, algunos autores omiten las tildes.

6. La presencia de caracteres no alfabéticos (signos de puntuación, cifras, paréntesis, símbolos matemáticos corrientes, etc.) pueden o no tenerse en cuenta. La coma, puntos son por ejemplo más frecuentes que más de la mitad de lasletras.
Si estos parámetros tienen un impacto espectacular en los símbolos menos frecuentes, es también sensible incluso para las letras más frecuentes.
El porcentaje de aparición de letras en español se muestra en la siguiente tabla:
Tabla No. 1. Frecuencia de aparición de las letras en el español.
Letra
Porcentaje
A
12,53
B
1,42
C
4,68
D
5,86
E
13,68
F
0,69
G
1,01
H
0,70
I6,25
J
0,44
K
0,01
L
4,97
M
3,15
N
6,71
Ñ
0,31
O
8,68
P
2,51
Q
0,88
R
6,87
S
7,98
T
4,63
U
3,93
V
0,90
W
0,02
X
0,22
Y
0,90
Z
0,52
A partir de los datos anteriores, se puede decir que:
1. Las vocales ocuparán alrededor del 45% del texto.
2. La E y la A son identificables fácilmente dado su porcentaje de aparición.
3. Las consonantes más frecuentes son:S,R,N,D,L,C (aparecen con una frecuencia de un 37%)
4. Las seis letras menos frecuentes son: Z,J,Ñ,X,W,K (sumadas tienen una frecuencia que apenas supera el 1,5%)

El problema
A usted como programador le envían un mensaje cifrado. La encriptación consiste en cambiar las letras normales del mensaje con un patrón definido. El reto está en desarrollar un programa que sea capaz de descifrar el...