GabaritoP2_A

Prévia do material em texto

Gabarito – Prova 2
Questão 1
a)
Entrada Dicionário Transmissão
0000 A
0001 B 1000 AB 0000 A
0100 F 1001 BF 0001 B
0000 A 1010 FA 0100 F
0010 C 1011 AC 0000 A
0000 A 1100 CA 0010 C
0011 D 1101 AD 0000 A
0000 A 1110 DA 0011 D
0001 B
0100 F 1111 ABF 1000 AB
0000 A
1010 FA
Codificação de tamanho fixo: 11 X 3 = 33 bits
Codificação LZW: 9 X 4 = 36 bits
LZW não forneceu mensagem menor que cod. tam. fixo
Questão 1
b) O melhor retângulo em termos de eficiência para o 
código retangular para proteger 1 byte (8 bits) é o 2 X 
4 (mais próximo de um quadrado perfeito). Nesse 
caso são necessários 7 bits de paridade adicionais (2 
para proteger as linhas, 4 para proteger as colunas e 
1 para proteger os bits de paridade). Portanto, a 
eficiência do código retangular para esse caso é de 
8/(8+7) = 0,53.
Já o código de Hamming necessita de apenas 4 bits 
de paridade para proteger 8 bits de dados, pois 4 bits 
de paridade testa por 1 erro em até 15 localizações 
diferentes da mensagem, sendo que esta terá
apenas 4 paridades + 8 dados = 12 bits. Portanto, a 
eficiência do código de Hamming nesse caso é de 
8/(8+4) = 0,67. Sendo assim, o código de Hamming é
mais eficiente.
Questão 1
c) 
P1 P2 D1 P3 D2 D3 D4 P4 D5 D6 D7 D8
1 2 3 4 5 6 7 8 9 10 11 12
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100
1 1 0 0 0 0 0 0 0 0 0 1
Mensagem obtida: 110000000001
d)
P1 P2 D1 P3 D2 D3 D4 P4 D5 D6 D7 D8
1 2 3 4 5 6 7 8 9 10 11 12
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100
1 0 0 0 0 1 0 1 0 0 0 0
P1 não acusa erro (ímpar) => 0
P2 não acusa erro (ímpar) => 0
P3 não acusa erro (impar) => 0
P4 não acusa erro (ímpar) => 0
Mensagem correta
Byte original: 00100000
Questão 2
a) A possui uma tendência de inibir B, já que a probabilidade de B 
ter 60 Hz (frequência rápida) é a maior de todas quando a 
frequência de A é de 10 Hz (lenta). Por outro lado, a 
probabilidade de B ter 10 Hz (lenta) é a maior de todas quando 
a frequência de A é 60 Hz (frequência rápida). E quando a 
frequência de A é 30 Hz (média), a probabilidade de B ter 30 Hz 
(média) é a maior de todas. Portanto, a tendência é que quanto 
maior a frequência de A, menor é a frequência de B e vice-
versa, o que caracteriza uma tendência de inibição.
b) Incerteza é dada pela entropia da distribuição das 
probabilidades condicionais da primeira linha (A = 10 Hz):
H(B|A=10Hz) = - 2*1/4*log21/4 – 1/2*log21/2 = 1,5 bit
Questão 2 (cont)
c) Como as três respostas do neurônio B são equiprováveis, as 
probabilidades das respostas são de 1/3 cada. Assim, a 
incerteza inicial sobre as respostas do neurônio B é dada pela 
entropia sobre essas probabilidades:
H(B) = -3*1/3*log21/3 = -log21/3 = 1,58 bit
Já a incerteza após sabermos que A está disparando a 30 Hz é
dada pela entropia da distribuição da segunda linha da tabela:
H(B|A=30Hz) = -2*1/4*log21/4 – 1/2*log21/2 = 1,5 bit
Logo, o ganho de informação que temos sobre as respostas de 
B ao saber que A = 30 Hz é:
I = H(B) – H(B|A=30Hz) = 1,58 – 1,5 = 0,08 bit.
Questão 3
a) Como há 7 X 7 = 49 variáveis binárias (cada célula podendo assumir 2 
valores possíveis), temos que o número de estados possíveis que o 
sistema pode assumir é 249. Como os estados são equiprováveis 
(probabilidade 1/249 cada) para serem escolhidos como estado inicial, 
temos que a incerteza sobre o estado inicial é dada pela entropia:
H = log2(249) = 49 bits
b) Como o sistema é determinístico e conhecemos o estado inicial, temos 
certeza absoluta de qual é o próximo estado (iteração 1), pois basta 
aplicar as regras para obtê-lo. Portanto a incerteza a respeito do 
próximo estado é nula (0 bit).
c) Como sabemos qual é o estado na iteração 1 quando o estado inicial 
(iteração 0) é conhecido (ver justificativa no item b), então também 
temos certeza absoluta de qual é o próximo estado (iteração 2), 
bastando aplicar as regras para obtê-lo. Portanto a incerteza a respeito 
do estado na iteração 2 também é nula (0 bit).
Questão 3 (cont)
d) Apesar de sabermos qual é o estado inicial, não sabemos nada 
a respeito de qual iteração o sistema se encontra. Então, para 
obter a incerteza sobre o estado do sistema observado em uma 
iteração qualquer, precisamos primeiro saber por quantos 
estados o sistema poderá passar. Aplicando as regras do Jogo 
da Vida temos:
Como existe apenas um único estado no qual o sistema fica 
(imutável), a incerteza a respeito do estado do sistema em uma 
iteração qualquer desconhecida é nula (0 bit).
iteração 0 iteração 1