Terceira prova_ Algoritmos e Estruturas de Dados III - Ciencia da Computacao - Campus Coracao Eucaristico - PMG - Tarde - G1_T1 - 2021_1

Prévia do material em texto

Terceira prova
Entrega 25 de jun de 2021 em 7:00 Pontos 16 Perguntas 8
Disponível 23 de jun de 2021 em 7:00 - 25 de jun de 2021 em 7:00 2 dias
Limite de tempo Nenhum
Instruções
Este teste não está mais disponível, pois o curso foi concluído.
Histórico de tentativas
Tentativa Tempo Pontuação
MAIS RECENTE Tentativa 1 69 minutos 8 de 16
Pontuação deste teste: 8 de 16
Enviado 23 de jun de 2021 em 8:17
Esta tentativa levou 69 minutos.
A terceira avaliação englobará os seguintes tópicos:
Criptografia (conceitos, métodos, técnicas e algoritmos)
Casamento exato de padrões (Força bruta, KMP, Boyer-Moore, Aho-Corasick)
Casamento aproximado de padrões (Distância de edição)
Você terá 48 horas para realizar a prova e contará com o horário oficial da aula para tirar dúvidas.
As questões envolvem alguma atividade de criação e isso deve ser entendido como algo pessoal. A prova,
portanto, é individual e a correção considerará a originalidade de cada resposta. Respostas semelhantes terão
os valores reduzidos. Se houver alguma dúvida no entendimento do que é para fazer, envie uma mensagem
para o professor.
A prova só permitirá uma tentativa. Assim, você pode realizar a prova e contar com o salvamento automático.
Só envie a prova, quando estiver com segurança sobre suas respostas.
Algumas questões podem ser resolvidas mais facilmente em papel ou usando algum software on-line. Se for o
caso, envie a foto ou imagem da sua solução na caixa de respostas.
2 / 2 ptsPergunta 1
Decifre a mensagem abaixo por meio da Cifra das Colunas:
VNJSOCIOIMRVNOALAAEEFS E IS LICA LOT
https://pucminas.instructure.com/courses/63791/quizzes/187745/history?version=1
Use a seguinte chave criptográfica: PRESO
Observações:
Os espaços entre as palavras devem ser incluídos na decifragem, isto é,
eles também mudarão de posição.
Use apenas letras maiúsculas e sem acentos na sua resposta.
Qualquer diferença será considerado resposta incorreta, pois a
correção é automática.
A VIOLENCIA JAMAIS RESOLVE CONFLITOS
Correto!Correto!
Respostas corretasRespostas corretas A VIOLENCIA JAMAIS RESOLVE CONFLITOS 
A chave PRESO nos retornará 5 colunas, que serão preenchidas
verticalmente:
3 4 1 5 2 
P R E S O 
A V I O 
L E N C I 
A J A M 
A I S R 
E S O L V 
E C O N 
F L I T O 
S
E, extraindo linha a linha, de cima para baixo, teremos a mensagem
decifrada:
A VIOLENCIA JAMAIS RESOLVE CONFLITOS
0 / 2 ptsPergunta 2
Considere um alfabeto de 27 caracteres que contém as letras A a Z, seguidas
do espaço em branco. Cada letra desse alfabeto tem um valor de acordo com
essa sequência: 
A=0, B=1, C=2, D=3, E=4, F=5, G=6, H=7, I=8, J=9, K=10, L=11, M=12, N=13,
O=14, P=15, Q=16, R=17, S=18, T=19, U=20, V=21, W=22, X=23, Y=24, Z=25,
␣=26 (onde ␣ representa o espaço em branco). 
Qual é o resultado da cifragem por meio da Cifra de Vigenère para a seguinte
mensagem:
LARANJA E A COR MAIS FELIZ
Use a seguinte chave criptográfica: FRANK
Observações:
Os espaços em branco devem ser cifrados também.
Use apenas letras maiúsculas e sem acentos na sua resposta.
Qualquer diferença será considerado resposta incorreta, pois a
correção é automática.
QRRNXOR E N MTI MNSX WEYSE
Você respondeuVocê respondeu
Respostas corretasRespostas corretas QRRNXOR RJFQCAAECAVBEWEYSD 
Para encontrarmos a resposta, precisamos encontrar o valor de cada
carácter (entre 0 e 26) - tanto da mensagem quanto da chave
criptográfica. Associaremos cada carácter da mensagem a um carácter
da chave. Quando eles se esgotarem, repetimos as chaves. 
Em seguida, basta somar os valores e, caso o resultado estoure o limite
numérico 26, devemos calcular o resto da divisão com 27. Finalmente,
convertemos esse resultado novamente em um carácter.
[ L (11) + F (05) ] % 27 = Q (16) 
[ A (00) + R (17) ] % 27 = R (17) 
[ R (17) + A (00) ] % 27 = R (17) 
[ A (00) + N (13) ] % 27 = N (13) 
[ N (13) + K (10) ] % 27 = X (23) 
[ J (09) + F (05) ] % 27 = O (14) 
[ A (00) + R (17) ] % 27 = R (17) 
[ ␣ (26) + A (00) ] % 27 = ␣ (26) 
[ E (04) + N (13) ] % 27 = R (17) 
[ ␣ (26) + K (10) ] % 27 = J (09) 
[ A (00) + F (05) ] % 27 = F (05) 
[ ␣ (26) + R (17) ] % 27 = Q (16) 
[ C (02) + A (00) ] % 27 = C (02) 
[ O (14) + N (13) ] % 27 = A (00) 
[ R (17) + K (10) ] % 27 = A (00) 
[ ␣ (26) + F (05) ] % 27 = E (04) 
[ M (12) + R (17) ] % 27 = C (02) 
[ A (00) + A (00) ] % 27 = A (00) 
[ I (08) + N (13) ] % 27 = V (21) 
[ S (18) + K (10) ] % 27 = B (01) 
[ ␣ (26) + F (05) ] % 27 = E (04) 
[ F (05) + R (17) ] % 27 = W (22) 
[ E (04) + A (00) ] % 27 = E (04) 
[ L (11) + N (13) ] % 27 = Y (24) 
[ I (08) + K (10) ] % 27 = S (18) 
[ Z (25) + F (05) ] % 27 = D (03)
E o resultado é:
QRRNXOR RJFQCAAECAVBEWEYSD
0 / 2 ptsPergunta 3
A assinatura digital é específica para um documento e um usuário, porque
 
ela é emitida por uma autoridade certificadora para um documento e em nome
de um usuário.
Você respondeuVocê respondeu
 
ela é baseada em um código hash desse documento, que é cifrado com a chave
privada do usuário.
Resposta corretaResposta correta
 
ela contém imagens do documento e da assinatura real do usuário nesse
documento.
 ela contém todo o documento cifrado com a chave privada do usuário. 
A assinatura digital começa com a extração de um código hash do
documento. Assim, se esse documento sofrer qualquer alteração, esse
código hash será diferente. Em seguida, esse código hash é cifrado com
a chave privada de quem o assina. Assim, qualquer um pode decifrar a
assinatura digital e recuperar o código hash do documento, mas,
necessariamente, usando a chave pública de quem assinou.
2 / 2 ptsPergunta 4
Qual são os valores do vetor de transições de falhas para o padrão abaixo no
casamento pelo algoritmo KMP?
A B A C A B C A B A
Na sua resposta, coloque os valores do vetor como uma sequência de números
separados por um único espaço (exemplo: 0 0 1). Deve haver pelo menos um
número nessa sequência para cada caráter do padrão. Qualquer diferença
nessas regras levará a resposta ser considerada incorreta, pois a correção é
automática.
0 0 0 0 1 2 0 0 1 2 3 4 0 0 1 2 3 4 5
Você respondeuVocê respondeu
Respostas corretasRespostas corretas 0 0 1 0 1 2 0 1 2 3 
O vetor de transições de falhas indica para qual estado o controle deve
ser transferido, quando o próximo caráter não for reconhecido. O vetor é
calculado a partir do tamanho da repetição do prefixo do padrão.
Para calculá-lo, basta olhar, em cada posição, qual é a maior repetição
do início do padrão. 
No caso do padrão da questão a resposta é:
A B A C A B C A B A 
0 0 1 0 1 2 0 1 2 3
Não era para considerar os espaços em branco na mensagem original,
mas talvez você não estivesse na hora que comentei sobre isso. Ao
considerá-los, a sua resposta está correta.
2 / 2 ptsPergunta 5
Se criarmos um diagrama de estados para a busca dos termos abaixo por Aho-
Corasick, esse diagrama de estados conterá quantos estados?
REI
RIO
REU
REINO
Na sua resposta, lembre-se de considerar o estado 0 como um estado a ser
incluído na conta.
9
Correto!Correto!
Respostas corretasRespostas corretas 9 (com margem: 0)
Cada letra promove uma transição de um estado para outro. Quando os
termos tem o mesmo prefixo, eles compartilham os estados iniciais. 
Transições para os estados de acordo com as letras de cada termo:
R E I 
1 2 3
R I O 
1 4 5
R E U 
1 2 6
R E I N O 
1 2 3 7 8
Assim, no total, teremos 9 estados (0 a 8).
2 / 2 ptsPergunta 6
Considere o texto (1ª linha) e o padrão (2ª linha) abaixo representados. A
posição específica em que o padrão está posicionado em relação ao texto
indica o próximo teste de casamento de padrões a ser feito por Boyer-Moore.
EU VI A CAUDA DA CRIATURA ALADA 
 ALADA
Qual será o deslocamento por sufixo bom determinado a partir dessa
posição?
4
Correto!Correto!
Respostas corretasRespostas corretas 4 (com margem: 0)
Nesse caso, o sufixo bom será DA, mas não há uma repetição desse
sufixo bom no padrão. Porém, o A final do sufixo bom é repetido no
início do padrão, de tal forma que, para que o prefixo Aocupe o lugar do
sufixo A é necessário um deslocamento de 4 posições.
0 / 2 ptsPergunta 7
Considere o texto (1ª linha) e o padrão (2ª linha) abaixo representados. A
posição específica em que o padrão está posicionado em relação ao texto
indica o próximo teste de casamento de padrões a ser feito por Boyer-Moore.
NAQUELA HORA, ERA ANA QUEM ABANAVA O DOENTE 
 ABANA 
Qual será o deslocamento por caractere ruim determinado a partir dessa
posição?
4
Você respondeuVocê respondeu
Respostas corretasRespostas corretas 2 (com margem: 0)
O caractere do texto que não foi encontrado no padrão é o B, após o
casamento correto do A final. Esse caractere aparece no padrão duas
posições atrás, de tal forma que o deslocamento por caractere ruim
deve ser de 2 posições para alinhar um B com o outro.
0 / 2 ptsPergunta 8
Qual será o valor da célula destacada em vermelho, no quadro de casamento
aproximado de padrões abaixo, usando o cálculo de distância de Levenshtein?
S E S S A O
 
A
C
E
S
S
O
4
Você respondeuVocê respondeu
Respostas corretasRespostas corretas 3 (com margem: 0)
A tabela abaixo representa os valores de cada célula da matriz de
distância de edição:
 S E S S A O 
 0 1 2 3 4 5 6 
A 1 1 2 3 4 4 5 
C 2 2 2 3 4 5 5 
E 3 3 2 3 4 5 6 
S 4 3 3 2 3 4 5 
S 5 4 4 3 2 3 4 
O 6 5 5 4 3 3 3
 
Pontuação do teste: 8 de 16