MAC 110 - Introdução à Computação

Bacharelado em Matemática Computacional

Segundo semestre de 2008

Terceiro Exercício-Programa

(em revisão ainda...)

Data de entrega: 29 de junho de 2008

Objetivo

O objetivo deste exercício-programa é auxiliar no deciframento de textos que foram cifrados por um dos métodos utilizados em criptologia, a área da Ciência da Computação que estuda o ciframento e deciframento de informações com o objetivo de impedir espionagem.

Um tipo de ciframento, chamado de substituição monoalfabética, consiste em simplesmente trocar uma letra do alfabeto por outra, de acordo com uma permutação das letras do alfabeto. Letras maiúsculas e minúsculas não são diferenciadas. Nos textos cifrados, usualmente não há acentos, nem espaçamento ou pontuação.

Permutação das letras

Considere, por exemplo, a seguinte tabela de correspondência entre as letras:

Exemplo:

Texto: Que exercício-programa legal!

Texto cifrado: YJBBMBKNDNDGUKGCKIZIEBCIE

De fato, substituindo-se as letras da frase "Que exercício-programa legal!" de acordo com a permutação dada acima, obtemos "YJB BMBKNDNDG-UKGCKIZI EBCIE!". Removendo-se os espaços em branco e a pontuação, chegamos ao texto cifrado acima.

Agora você. Supondo que foi usada a permutação das letras dada acima, a que texto corresponde a seguinte mensagem cifrada?

Texto cifrado: WGJCGOXIKLBQIFBKBOXBBMBKNDNDGUKGCKIZI

Texto: ??????

Note que existem 26! (aproximadamente 4x10²⁶) permutações diferentes das letras do alfabeto. Assim, se a permutação usada não é conhecida, existem aproximadamente 4x10²⁶ ciframentos possíveis.

O exercício-programa

Nesse exercício-programa, resumidamente, você terá que escrever um programa em C que tenha como entrada um texto cifrado e ajude o usuário no processo de deciframento, assumindo que a cifra utilizada foi a substituição monoalfabética.

A técnica de deciframento que você deve utilizar é baseada no fato de que as letras do alfabeto não ocorrem todas com a mesma freqüência. Nos textos em português, a letra 'A' é a mais comum, 'E' é a segunda mais comum, e assim por diante, até 'K', 'W' e 'Y' que quase não ocorrem. Então, como um primeiro passo para decifrar o texto, você deve contar a ocorrência de cada letra no texto cifrado e tentar relacionar essas freqüências com a freqüência padrão conhecida das letras em português. Por exemplo, se 'Q' foi a letra que mais ocorreu no texto cifrado, é razoável desconfiar que 'Q' está substituindo no texto cifrado a letra 'A' do texto original. Logo, você trocará todas as ocorrências da letra 'Q' no texto cifrado pela letra 'A'. A mesma coisa para cada uma das 26 letras do alfabeto. Feito isso, o programa passará a uma fase de refinamento, em que auxiliará o usuário a determinar qual é a substituição correta que leva ao deciframento total do texto, fazendo as trocas de letras sugeridas pelo usuário.

Freqüência das letras em português

A ordem de freqüência padrão de ocorrência das letras em português é a seguinte: A E O S I R N D T C M U P L V G B F Q H J X Z K W Y No seu programa, você pode armazenar essa informação em um vetor de caracteres de nome, digamos, portugues. Mais exatamente, use a seguinte declaração no início da sua função principal:

char *portugues = "AEOSIRNDTCMUPLVGBFQHJXZKWY";

Tal declaração corresponde à declaração de um vetor de caracteres de nome portugues, com 26 posições, inicializado com as letras exibidas acima, ou seja, 'A' na posição 0, 'E' na posição 1, 'O' na posição 2 e assim por diante. Para facilitar, declare tal variável como uma variável global, fora da função main, antes de todas as funções que você tiver no seu programa.

Dados de entrada

O seu programa deve ler o texto cifrado de um arquivo texto, como no EP2. Deve armazenar o texto lido em um vetor de caracteres, digamos texto, com MAX posições, onde MAX é uma constante, por exemplo, 10000. Após ler o texto do arquivo, seu programa deve imprimi-lo.

Cálculo da freqüência das letras no texto cifrado

Primeiramente o seu programa deve determinar quantas vezes cada letra aparece no texto cifrado. Depois, o seu programa deve ordenar as letras em ordem não-crescente do número de aparições no texto cifrado.

Exemplo: Se o arquivo de entrada contiver o texto

O principal benefício de aprender e fazer matemática é que ela
desenvolve a habilidade de raciocinar sobre estruturas formalmente
definidas como aquelas em computação e suas aplicações.

que não está cifrado, mas é uma tradução da frase inicial do artigo "Why universities require computer science students to take math?" [Communications of the ACM, Volume 46, Number 9 (2003), Pages 36-39], o seu programa deve obter a seguinte ordem:

E (que aparece 25 vezes)
A (aparece 22 vezes)
I (aparece 12 vezes)
O (aparece 11 vezes)
C (aparece 10 vezes)
R (aparece 10 vezes)
S (aparece 9 vezes)
D (aparece 8 vezes)
L (aparece 7 vezes)
M (aparece 7 vezes)
N (aparece 7 vezes)
T (aparece 6 vezes)
U (aparece 6 vezes)
P (aparece 5 vezes)
F (aparece 4 vezes)
B (aparece 3 vezes)
Q (aparece 2 vezes)
V (aparece 2 vezes)
H (aparece 1 vezes)
Z (aparece 1 vezes)
e as demais letras, que não aparecem nenhuma vez, numa ordem arbitrária.

Você pode supor que no texto não há acentos.

Digamos que o resultado de tal ordenação fique guardado no vetor permutacao, com 26 posições.

Primeira fase do deciframento

A primeira fase do deciframento consiste em trocar no texto cifrado a ocorrência da letra mais freqüente pela letra mais freqüente em português, a segunda letra mais freqüente pela segunda letra mais freqüente em português, e assim por diante.

Feito isso, o seu programa mostra o texto resultante das trocas sugeridas, substituindo (apenas na impressão) a letra permutacao[i] pela letra portugues[i], para cada i entre 0 e 25. O texto assim impresso é o resultado da primeira fase - a primeira tentativa de deciframento do texto.

Segunda fase do deciframento

Em geral o texto obtido depois desta primeira tentativa de deciframento não é a mensagem correta decifrada. Algumas letras não terão sido trocadas pelas letras corretas. O programa entra então em uma segunda fase, onde se inicia uma interação com o usuário.

Repetidamente, o programa imprime para o usuário a seguinte informação:

o texto parcialmente decifrado e
a permutação das letras usada no texto cifrado para obter o texto parcialmente decifrado; imprima essa permutação por ordem de freqüência das letras no texto cifrado, junto com a ordem do português, pois isso eventualmente ajuda o usuário a sugerir futuras trocas.

O programa então pergunta ao usúario se ele quer alterar a permutação corrente. Caso o usuário responda que quer alterar a permutação corrente, o programa deve pedir que o usuário digite um par de letras que deseja trocar no texto decifrado. Lido esse par de letras, efetua-se a troca correspondente na permutação usada, e repete-se o processo: o programa imprime novamente o texto e a permutação corrente, e pergunta se o usuário quer fazer uma nova troca, e assim sucessivamente...

Para que fique mais claro o que o seu programa deve fazer, aqui você encontra um programa executável que faz exatamente o que o seu programa deve fazer. Brinque com este programa, usando os vários textos cifrados abaixo, antes de começar a pensar em como escrever o seu programa.

Texto cifrado 1 [txt].
Texto cifrado 2 [txt].
Texto cifrado 3 [txt].
Texto cifrado 4 [txt].
Texto cifrado 5 [txt].
Texto cifrado 6 [txt].

Esses textos podem também ser usados nos testes do seu programa.

Caso você tenha problemas para executar o programa decifra, siga as seguintes instruções. Entre na sua conta da rede linux e execute o seguinte comando num diretório a sua escolha:

cp ~cris/mac110/* .

Feito isso, nesse seu diretório você deve ter o arquivo decifra e os 6 arquivos cifrados acima. Execute o decifra, dando como entrada qualquer um destes arquivos e teste o programa!

Em algumas situações, quando o programa faz leitura de caracteres do teclado, alguns problemas são comuns, como você já observou no EP2. O mais comum e mais chato é o programa ignorar um comando de leitura simplesmente. Isso tem a ver com o programa fazer a leitura de um buffer intermediário, e só apenas quando o buffer está vazio, ele faz a leitura do teclado mesmo. Para que o programa não leia caracteres indesejáveis que estejam no buffer, basta utilizar como formato de leitura
" %c", com um caractere branco antes do %c.

`Funções obrigatórias`

O seu programa deve conter pelo menos as duas funções abaixo: void leitura (char texto[], int *n); que lê de um arquivo cujo nome é dado pelo usuário um arquivo texto, e o armazena no vetor texto, devolvendo em *n o número de caracteres do texto. Além disso, a função também imprime o texto lido. int letra (char ch); que recebe um caractere como parâmetro e devolve 1 se o caractere for uma letra, 0 caso contrário. void contaletras (char texto[], int n, int cont[]); que tem como parâmetro de entrada um vetor texto onde as primeiras n posições armazenam um texto, e como parâmetro de saída um vetor cont, com 26 posições, onde a função deve armazenar o número de vezes que cada letra aparece no texto dado no vetor texto. Para fazer isso, use a função anterior. void ordenaletras (int cont[], char perm[]); que recebe como parâmetro de entrada um vetor cont, de 26 posições, com o número de aparições de cada letra do alfabeto, e devolve no parâmetro de saída perm uma permutação das letras do alfabeto em ordem não-crescente de número de aparições. int posicao (char v[], char letra); devolve o índice onde letra aparece no vetor v, que armazena uma permutação das letras do alfabeto. void decodificaemostra (char texto[], int n, char perm[]); imprime na tela os n caracteres armazenados no vetor texto (ou parte deles, se o usuário não quiser ver todo o texto), convertidos de acordo com a ordem das letras em perm e a ordem das letras por freqüência em português. Para fazer isso, use a função anterior. char maiuscula (char ch); devolve o próprio caractere ch, se ele não for uma letra minúscula, ou a maiúscula correspondente, se ele for uma letra minúscula. void trocaletra (char perm[], char l1, char l2); devolve a permutação perm do alfabeto ajustada, de forma que as letras l1 e l2 sejam trocadas no momento da decodificação do texto. Preste atenção aqui! O que você deve fazer para isso é trocar no vetor perm as letras correspondentes a l1 e l2 no vetor portugues. Use a função posição para isso. void imprimearquivo (char texto[], int n, char perm[]); imprime em um arquivo cujo nome é escolhido pelo usuário o texto decifrado. Essa função é semelhante a função decodificaemostra, mas imprime o texto todo, sem interrupções. Utilize para isso novamente a função posicao. Sintam-se a vontade para implementar outras funções que vocês achem conveniente. Arquivos texto Para fazer a leitura de um arquivo de entrada, utilize a seguinte receita no seu programa, dentro da função main(): /* Declaração das variáveis para leitura e gravação em arquivos */ char nome[40]; /* para o nome do arquivo de entrada */ FILE *entrada; /* Primeiros comandos do seu programa */ /* Abertura do arquivo de entrada */ printf("Digite o nome do arquivo de entrada: "); scanf("%s", nome); if ((entrada = fopen(nome, "r")) == NULL) { printf("Arquivo de entrada nao encontrado!\n"); exit(0); } /* Último comando do seu programa (exceto pelo return) */ fclose(entrada); No miolo do seu programa, toda vez que você quiser ler alguma coisa do arquivo de entrada, utilize a função fscanf. Esta função funciona de forma semelhante ao scanf, exceto que ela possue um parâmetro a mais: o nome do arquivo de onde está sendo feita a leitura. Numa primeira fase, escreva apenas um programa que leia um texto de um arquivo de entrada e o imprima na tela. No EP, você vai precisar detectar quando o arquivo terminou para concluir a leitura dos dados. Para tanto, utilize a função feof, que tem como parâmetro um identificador de arquivo, e devolve 1 se o arquivo terminou, 0 em caso contrário. (Veja a adição no exemplo abaixo.) Exemplos: /* Leitura de três números inteiros do arquivo de entrada */ fscanf(entrada, "%d %d %d ", &n, &p, &m); /* Leitura de um caractere do arquivo de entrada */ fscanf(entrada, "%c", &ch); /* Leitura de um número real do arquivo de entrada */ fscanf(entrada, "%f ", &x); /* enquanto o arquivo entrada ainda tem dados a serem lidos... */ while (!feof(entrada)) { ... } Para criar um arquivo de entrada, você pode utilizar o próprio lcc. Para tanto, apenas crie um arquivo novo, dando-lhe o nome, por exemplo, de entrada.txt, e digite nele, por exemplo, o texto acima (sem os acentos, se for o caso). Grave o arquivo. Não compile este arquivo, claro, já que ele não é um programa em C. O lcc, quando você dá como nome do arquivo simplesmente entrada.txt, procura o arquivo no chamado diretório padrão. Assim, certifique-se de que o seu arquivo de entrada encontra-se neste diretório, ou ele não será encontrado. Uma outra alternativa é dar, quando o seu programa pedir para você digitar o nome do arquivo, o nome completo do arquivo, isto é, o nome incluindo os diretórios todos onde ele se encontra. Cuidado no entanto com as "\" no nome do arquivo. Observações Só é permitido usar os recursos dados nas aulas até o dia de entrega do exercício-programa. O EP deve ser feito INDIVIDUALMENTE: não o faça em grupo nem empreste para um colega. Exercícios "equivalentes" receberão nota zero. Não serão aceitos exercícios-programas atrasados. Todos os exercícios-programas devem ter um cabeçalho do seguinte tipo: /********************************************************/ /* Fulano de Tal */ /* Exercicio-Programa xx */ /* Curso yy - Turma zz -- Professor: Ciclano de Tal */ /********************************************************/ Exercícios com erros de sintaxe (ou seja, erros de compilação) ou que não compilem no LCC receberão nota ZERO. É muito importante que seu programa tenha comentários e esteja bem indentado, ou seja, digitado de maneira a ressaltar a estrutura de subordinação dos comandos do programa (conforme visto em aula). A avaliação dos exercícios-programa levará isto em conta. Você deve entregar o seu EP por meio do sistema Paca. Guarde com você até o final do semestre os arquivos de seus programas, pois eles podem ser solicitados pelo professor caso surja alguma dúvida.