GabaritoSub_A

Prévia do material em texto

Gabarito – Prova Substitutiva
Questão 1
5D14 = 5*141+13*140 = 8310. Seja X a base de numeração dos
Meklars. Então temos que:
6BX = 6X1+11X0 = 8310 => 6X = 72 => X = 12
Portanto, a base de numeração dos Meklars é 12.
Questão 2
a) Frequência amostral de 0,5 Hz equivale a obter 1 amostra a cada 2 
segundos. Portanto, as amostras são obtidas nos instantes pares 
(0s, 2s, 4s, 6s, 8s, 10s, 12s, 14s, 16s). Para 8 níveis de 
quantização, o intervalo de valores de 0 a 16 deve ser dividido em 8 
intervalos iguais, sendo cada intervalo com codificação de 3 bits:
[0;2[ => 000 [2;4[ => 001 [4;6[ => 010 [6;8] => 011
[8;10[ => 100 [10;12[ => 101 [12;14[ => 110 [14;16] => 111
Assim, com base no gráfico, temos a sequência digital:
000 101 001 101 101 100 010 101 000
Questão 2 (cont)
b) Assumindo a enumeração binária pura, temos:
000(0) 001(1) 010(2) 011(3) 100(4) 101(5) 110(6) 111(7)
De acordo com a sequencia digital obtida no item a, temos as 
seguintes probabilidades:
P(0) = 2/9; P(1) = 1/9; P(2) = 1/9; P(3) = 0;
P(4) = 1/9; P(5) = 4/9; P(6) = 0; P(7) = 0
Sendo assim, a incerteza geral sobre esses níveis é dada pela 
entropia das probabilidades acima:
H = -2/9*log22/9 – 3*1/9*log21/9 – 4/9*log24/9 = 2,06 bits
Questão 2 (cont)
c) Uma possível codificação:
0: 100
1: 110
2: 101
4: 111
5: 0
Comprimento médio do código de Huffman (L):
L = 1*4/9+3*(3*1/9+2/9) = 2,11 bits
Eficiência entrópica = H/L = 2,06/2,11 = 0,975
Através da codificação acima, a mensagem digital fica:
100 0 110 0 0 111 101 0 100
9/9
4/9
(5)
5/9
3/9 2/9
2/9
(0)
1/9
(2)
1/9
(1)
1/9
(4)
0
0
0 0
1
1
11
Questão 2 (cont)
d) As 4 primeiras amostras estão codificadas no item c como:
100 0 110 0
Codificação de Hamming para os 8 bits de dados acima:
P1 P2 D1 P3 D2 D3 D4 P4 D5 D6 D7 D8
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100
1 1 1 1 0 0 0 1 1 1 0 0
Portanto, a mensagem codificada fica 111100011100. Como essa 
codificação usa 4 bits de paridade para proteger 8 bits de dados, a 
eficiência de redundância é de 8/(8+4) = 2/3 = 0,67.
Questão 3
a) Existem 3 X 6 X 5 = 90 objetivos possíveis. Como os objetivos 
são sorteados, eles são equiprováveis (probabilidade 1/90 
cada). Sendo assim, a incerteza inicial em relação aos objetivos 
é dada pela entropia da distribuição uniforme das 
probabilidades dos 90 objetivos: H0 = log290 = 6,49 bits. Como o 
envelope contém exatamente um dos objetivos, sabendo-se o 
seu conteúdo anula-se toda a incerteza inicial (o detetive que 
conhecer esse conteúdo primeiro ganha o jogo). Logo, o ganho 
de informação contido no envelope é igual a entropia inicial:
I = H0 - 0 = 6,49 bits
Questão 3 (cont)
b) O jogador que formulou a hipótese sabe que o criminoso não é
o Coronel Mostarda (o número de possibilidades de criminosos 
cai de 3 para 2). Portanto, ele sabe que agora o objetivo pode 
ser qualquer um de 2 X 6 X 5 = 60 possíveis. Sua incerteza 
sobre os objetivos após saber que a carta Coronel Mostarda 
não está no envelope é H1 = log260 = 5,91 bits. O ganho de informação foi:
I = H0-H1 = log290-log260 = 6,49-5,91 = 0,58 bit.
Os outros jogadores só sabem que um dos objetivos não está
no envelope (Coronel Mostarda, faca, quarto). Assim, eles ainda 
ficam em dúvida em relação a 89 dos 90 objetivos possíveis. 
Sendo assim, o ganho de informação dos outros jogadores foi:
I = log290-log289 = 6,49 – 6,476 = 0,014 bit
Questão 3 (cont)
c) De acordo com o item b, sabemos que ao revelar a carta Coronel 
Mostarda, o jogador obtém um ganho de informação de 0,58 bit. 
Falta obter os ganhos de informação para as outras cartas (faca 
e quarto):
- faca: sabendo que arma do crime não é a faca, o número de 
objetivos possíveis cai de 3 X 6 X 5 (90) para 3 X 5 X 5 (75). 
Assim o ganho de informação ao revelar a carta Coronel 
Mostarda é I = log290-log275 = 6,49-6,23=0,26 bit
- quarto: sabendo que o local do crime não é o quarto, o número 
de objetivos possíveis cai de 3 X 6 X 5 (90) para 3 X 6 X 4 (72). 
Assim o ganho de informação ao revelar a carta quarto é
I = log290-log272 = 6,49-6,17 = 0,32 bit.
Logo, a carta que minimiza o ganho de informação é a faca.