1a Prova de Laboratório de Programação – 2014-01 (10/06/2014)
1a questão: Desenvolva um programa em C que receba uma cadeia de n caracteres distintos passada como
argumento na linha de comando e, através de uma função recursiva, forneça todas as permutações posíveis
desses n caracteres, imprimindo-as.
2a questão: Implemente em C o algoritmo BubleSort cujo pseudo-código (não otimizado) é fornecido a seguir.
Teste a sua implementação do algoritmo com o array {101,24,56,32,67,99,88,11,2,7,1,47}.
procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat swapped = false
for i = 1 to n­1 inclusive do
/* if this pair is out of order */
if A[i­1] > A[i] then
/* swap them and remember something changed */
swap( A[i­1], A[i] )
swapped = true
end if
end for
until not swapped
end procedure
3a questão: Nos dias de hoje muitos estão preocupados em salvaguardar a sua privacidade, em função das
denúncias formuladas por Edward Snowden sobre um esquema de vigilância eletrônica a nível mundial
colocado em ação pela National Security Agency (NSA), uma agência do governo dos EUA. Chefes de Estado
(Angela Merkel, Dilma Roussef, etc.), empresas (Petrobrás, etc.) e até cidadãos comuns, de diversas
nacionalidades, estariam sendo alvos desse esquema. Se todos os usuários da Internet começarem a
criptografar seus dados, mesmo com algoritmos de criptografia relativamente simples, essas tentativas de
controle global do indivíduo e da sociedade poderão ser neutralizadas.
Um esquema simples de criptografia é baseado na criptografia baseada no OU-EXCLUSIVO (EXCLUSIVE-OR).
Eis a tabela verdade entre os pares de bits A e B.
A
B
A XOR B
T
T
F
F
T
F
T
F
F
T
T
F
A idéia por trás da criptografia EXCLUSIVE-OR é muito simples. É impossível reverter-se a operação
(descriptografar) sem o conhecimento de um dos dois argumentos A (a mensagem a ser criptografada) ou B (a
chave utilizada para criptografar o texto). Todavia, de posse do texto criptografado e da chave B é possível
restaurar-se o texto original.
Usa-se a criptografia EXCLUSIVE-OR para criptografar um arquivo aplicando-a sucessivas vezes a segmentos
do arquivo, cada um deles com o mesmo número de caracteres da chave e armazenando-se os resultados na
mesma ordem em que foram gerados. Para cada bit adicionado ao comprimento da chave, dobra-se o número
de tentativas que seriam necessárias para se quebrar a criptografia por meio da força bruta.
A função void cript(char cadeia[], char chave[]) criptografa uma cadeia de caracteres com o mesmo número de
caracteres que a chave utilizada na criptografia.
//a cadeia a ser criptografada possui o mesmo número de caracteres que a chave.
void cript(char cadeia[], char chave[]){
int x;
for(x=0; chave[x] != '\0'; x++)
{
cadeia[x]=cadeia[x]^chave[x];
}
} Forneça o código da função void uncript(char cadeia[], char chave[]) que descriptografe o texto original
criptografado por cript.
4a questão: Altere o código da função void cript da 3a questão para adequar-se à situação em que os seus
parâmetros sejam apenas pointers para cadeias de caracteres.
5a questão: Desenvolva o programa cripttext que lê um texto da entrada padrão (teclado) de tamanho arbitrário
(desde que < 10.000), imprime-o e que use a criptografia EXCLUSIVE-OR para criptografá-lo. Utilize uma chave
com n=64 caracteres. Essa chave deve ser passada para seu programa como um argumento na linha de
comando. Armazene o texto criptografado em um array de caracteres, e o imprima. A seguir descriptografe o
texto criptografado usando a função uncript e imprima o resultado.
Atenção: Considere também a hipótese do texto a ser criptografado ser menor do que a chave. Nesse caso
para um texto de tamanho m < n, você usaria apenas os m caracteres iniciais da chave para criptografar o
texto.
Exemplo de uso: cripttext q/w.e,rmtnybuvicoxpz[a]s\dfgjk=l-;0'9|8}7{6*5!1#3&6^$45%+:”?<>~
Boa Sorte! Prof. Oscar Luiz Monteiro de Farias