NI13_Prova2_A

Prévia do material em texto

1 
 
 
Un ivers idade Federa l do ABC 
Disciplina: BC0504 (Natureza da Informação) Avaliação: P2 
Professor: David Correa Martins Jr Turma: A - Noturno – São Bernardo 
 
Instruções para a prova (leia antes de começar): 
 
A) Explique/Justifique suas respostas sempre! (questão que possua apenas resposta, sem 
apresentação do seu desenvolvimento ou qualquer justificativa, receberá nota zero mesmo 
se a resposta estiver correta!) 
B) Use a propriedade do logaritmo: log(A/B) = log(A)-log(B) 
 
Questões: 
 
1) [6,0 pt] O professor João da UFABC ministrou uma disciplina para uma turma de 11 alunos. 
Ao final do período letivo, com os conceitos dos alunos já definidos, resolveu enviar para a 
secretária Maria uma mensagem contendo os conceitos dos alunos. A mensagem encontra-se 
abaixo: 
ABFACADABFA 
 
Antes de enviar a mensagem, cujo alfabeto é composto pelos caracteres {A, B, C, D, F, O}, 
João aplicou o método LZW de compressão tendo como dicionário inicial os seguintes padrões 
de 3 bits: 
A: 000 B: 001 C: 010 D: 011 F:100 O: 101 
 
O primeiro padrão de dois caracteres será armazenado no dicionário com o código 1000, e os 
próximos padrões contendo mais de um caractere receberão um código seguindo a ordenação 
binária normal. Além disso, os códigos do dicionário inicial passam a receber um zero à 
esquerda adicional, transformando-os em códigos de 4 bits. 
 
a) [2,6 pt] Determine a codificação LZW passo a passo, desconsiderando os códigos de início 
e fim (START e STOP), para a mensagem dada acima, informando também os códigos 
binários associados a cada padrão gravado no dicionário e a cada padrão emitido na saída 
resultante. O LZW forneceu uma mensagem menor do que a codificação de tamanho fixo 
fornece para esse caso? Justifique. 
 
b) [1,0 pt] Após a codificação LZW obtida no item a, João decide aplicar um mecanismo de 
correção de um único erro para cada byte de dados antes de enviar para Maria. Para isso, ele 
tem duas opções de codificação: código retangular ou código de Hamming. Qual dos dois 
provê a melhor taxa de código (eficiência) para um byte de dados? Justifique. 
 
c) [1,2 pt] Suponha que João adotou o melhor esquema de detecção e correção de erro (de 
acordo com o item b) para que Maria possa identificar e corrigir 1 bit incorreto para cada byte 
da mensagem. Determine a mensagem binária resultante contendo essa proteção (assumindo 
paridade ímpar) para o primeiro byte da mensagem obtida no item a. 
 
d) [1,2 pt] 100001010000 é o conteúdo recebido por Maria referente ao terceiro byte da 
mensagem protegida pela codificação aplicada no item c. Essa mensagem está correta ou 
incorreta? Justifique. Caso esteja incorreta, corrija a mensagem se possível, obtendo o 
conteúdo original do referido byte. 
 
 
 2 
2) [2,6 pt] Dois neurônios A e B estão conectados por uma sinapse, onde o neurônio A é o pré-
sináptico e o neurônio B é o pós-sináptico. Cada neurônio tem apenas 3 modos de disparo: 
10Hz, 30Hz ou 60Hz. A tabela abaixo mostra qual a probabilidade do neurônio B disparar em 
cada frequência dada a frequência do neurônio A: 
 
F(A) P(F(B) = 10 Hz | F(A)) P(F(B)= 30 Hz | F(A)) P(F(B) = 60 Hz | F(A)) 
10 Hz 1/4 1/4 1/2 
30 Hz 1/4 1/2 1/4 
60 Hz 1/2 1/4 1/4 
 
a) [0,6 pt] A partir da tabela, a conexão entre os neurônios A e B é provavelmente uma 
conexão excitatória ou inibitória? Justifique. 
 
b) [0,8 pt] Você descobriu que o neurônio A está transmitindo com uma frequência de 10 Hz. 
Neste caso, qual a incerteza (em bits) sobre a frequência de disparo do neurônio B? 
 
c) [1.2 pt] Supondo que as freqüências do neurônio B são equiprováveis na ausência de 
estímulos do neurônio A, determine o ganho de informação (em bits) que você obtém ao saber 
que o neurônio A está transmitindo com freqüência 30 Hz. 
 
 
3) [2,4 pt] Seja o Jogo da Vida (Game of Life) descrito por um tabuleiro bi-dimensional em que 
cada elemento (célula) desse tabuleiro pode estar desligado (0) ou ligado (1). Para definir o 
próximo estado de um sistema, o Jogo da Vida possui 3 regras básicas: 
A - Célula ligada com menos de 2 vizinhos (verticais, horizontais ou diagonais) ligados 
no estado atual torna-se desligada no próximo estado 
 B - Célula ligada com mais de 3 vizinhos ligados no estado atual torna-se desligada no 
próximo estado 
 C – Célula desligada com exatamente 3 vizinhos ligados torna-se ligada no próximo 
estado 
 
a) [0,6 pt] Suponha um tabuleiro composto por 7 linhas e 7 colunas. Determine a quantidade 
de incerteza geral (em bits) sobre os estados iniciais, tendo em vista que qualquer estado 
possível poderia ser escolhido com a mesma probabilidade para ser o estado inicial. 
 
b) [0,6 pt] Sabendo-se que o estado inicial (iteração 0) é conhecido e dado na figura abaixo, 
determine a quantidade de incerteza geral (em bits) sobre os estados possíveis do sistema na 
iteração 1. 
 
 
c) [0,6 pt] Dado o mesmo estado inicial (iteração 0) da figura acima, determine a quantidade de 
incerteza (em bits) a respeito dos estados possíveis que o sistema pode estar na iteração 2. 
 
d) [0,6 pt] Supondo que você sabe que o estado inicial é o mesmo da figura acima, mas que 
você desconhece em qual iteração o sistema se encontra, determine a quantidade de incerteza 
geral (em bits) sobre os estados possíveis que você poderá observar em uma iteração 
qualquer.