Lista 2 - NI

Prévia do material em texto

Lista 2 – Natureza da Informação 
Glória Marcela de Barros Moraes 11201811297 
Turma A1 – Noturno 
 
1. A codificação run-length agrupa repetições de símbolos e sequências. O algoritmo 
garante economia de espaço apenas quando há sequencias e repetições de 
símbolos/códigos de forma linear e homogênea. 
 
2. a) A[3]B[6]Y[4]P[9]T[1]K[8] 
b) 1[5]2[3]3[5]1[1]2[6]1[7]3[9] 
 
3. a) 6/31 ~ 19% 
b) 7/36 ~ 19,4% 
 
4. a) Na primeira mensagem a compressão seria excelente, no entanto, a segunda 
mensagem não haveria um bom desempenho pois os símbolos estão embaralhados e 
não homogêneos. 
 b) As duas mensagens seriam bem comprimidas, em ambas há repetições em pares. 
 
5. a) ABAABCCABBBAC 
 b) 1 −
10×9
13×8
≅ 0.1346 ∴ 13.46% 
 
6. a) a[1]b[2]a[1]b[1]a[1]b[1]a[1]c[1] 
 b) 256 1 2 2 258 258 1 3 257 
 c) O algoritmo LZW foi mais eficiente, pois o código possui bastante conjuntos de 
repetições de modo que o algoritmo run-lenght não comprime. 
 
7. a) abcabca 
Entrada Nova_entrada 
dicionário 
9 bits Nova_entrada 
dicionário 
Saída 
97 a 256 (start) 
98 b 258 ab 97 a 258 ab a 
99 c 259 bc 98 b 259 bc b 
97 a 260 ca 99 c 260 ca c 
 
 
 
 
 
b) AABCBBABC 
 
 
 
 
 
 
 
 
 
c) banana barata 
 
 
 
 
 
 
 
 
 
 
 
 
 
98 b 258 Ab a 
99 c 261 abc 260 ca 261 abc b 
97 a 257 (stop) c 
 a 
Entrada Nova_entrada 
dicionário 
9 bits Nova_entrada 
dicionário 
Saída 
65 A 256 (start) 
65 A 258 AA 65 A 258 AA A 
66 B 259 AB 65 A 259 AB A 
67 C 260 BC 66 B 260 BC B 
66 B 261 BB 67 C 261 BB C 
66 B 262 BA 66 B 262 BA B 
65 A 66 B B 
66 B 259 AB A 
67 C 67 C B 
 267 (stop) C 
Entrada Nova_entrada 
dicionário 
9 bits Nova_entrada 
dicionário 
Saída 
98 b 256 (start) 
97 a 258 ba 98 b 258 ba b 
110 n 259 an 97 a 259 an a 
97 a 260 na 110 n 260 na n 
110 n 261 a 
(space) 
97 a 261 a 
(space) 
a 
97 a 262 (space) 
b 
260 na 262 (space) 
b 
n 
32 (space) 32 (space) a 
98 b 258 ba (space) 
97 a 114 r b 
114 r 97 a a 
97 a 116 t r 
116 t 97 a a 
97 a 257 (stop) t 
 a 
d) ABRACADABRA 
 
 
 
 
 
 
 
 
 
 
 
 
 
e) pipipi pop popopo 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Entrada Nova_entrada 
dicionário 
9 bits Nova_entrada 
dicionário 
Saída 
65 A 256 (start) 
66 B 258 AB 65 A 258 AB A 
82 R 259 BR 66 B 259 BR B 
65 A 260 RA 82 R 260 RA R 
67 C 261 AC 65 A 261 AC A 
65 A 262 CA 67 C 262 CA C 
68 D 263 AD 65 A 263 AD A 
65 A 264 DA 68 D 264 DA D 
66 B 265 DB 258 AB 265 DB A 
82 R 260 RA B 
65 A 257 (stop) R 
 A 
 
 
Entrada Nova_entrada 
dicionário 
9 bits Nova_entrada 
dicionário 
Saída 
112 p 256 (start) 
105 i 258 pi 112 p 258 pi p 
112 p 259 ip 105 i 259 ip i 
105 i 258 pi p 
112 p pip 258 pi pip i 
105 i pi(space) 32 (space) pi(space) p 
32 (space) 260 i(space) 112 p 260 i(space) i 
112 p 261 (space)p 111 o 261 (space)p 
111 o 262 po 112 p 262 po p 
112 p 263 op 261 (space)p 263 op o 
32 (space) 264 p(space) 263 op 264 p(space) p 
112 p 267 opo 
111 o 265 (space)po 265 (space)po p 
112 p 266 op(space) 266 op(space) o 
111 o 267 opo 267 opo p 
112 p o 
111 o p 
 o 
f) a arara arranha a aranha 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
8. a) Redução de 19.64% 
b) Redução de 0% 
c) Redução de 4.8% 
d) Redução de 7.95% 
e) Redução de 27.20% 
f) Redução de 29.69% 
 
9. A mensagem pode ser comprimida sem perda quando há repetições homogêneas, 
quando há padrões de bits não usados, ou símbolos mais usados que outros. Por outro 
Entrada Nova_entrada 
dicionário 
9 bits Nova_entrada 
dicionário 
Saída 
97 a 256 (start) 
32 (space) 258 a(space) 97 a 258 a(space) a 
97 a 259 (space)a 32 (space) 259 (space)a 
114 r 260 ar 97 a 260 ar a 
97 a 261 ra 114 r 261 ra r 
114 r 260 ar a 
97 a 258 a(space) r 
32 (space) 260 ar a 
97 a 261 ra 
114 r 110 n a 
114 r 262 rr 104 h 262 rr r 
97 a 266 a(space)a r 
110 n 263 an 259 (space)a 263 an a 
104 h 264 nh 261 ra 264 nh n 
97 a 265 ha 264 nh 265 ha h 
32 (space) 97 a a 
97 a 266 a(space)a 257 (stop) 266 a(space)a 
32 (space) a 
97 a 
114 r a 
97 a 267 ara 267 ara r 
110 n 268 arr 268 arr a 
104 h 269 ran 269 ran n 
97 a 270 nha 270 nha h 
 a 
lado, quando a informação final puder ser aproximada, tendo o dado exato perdido, 
usa-se a compressão com perdas. 
 
 
10. As quantizações são técnicas de compressão com perda. Na escalar o 
mapeamento é realizado de modo geral para individual, de forma a analisar cada entrada 
individualmente, linear ou não linearmente. Diferentemente do que ocorre na vetorial, 
em que o mapeamento é de todo o espaço multidimensional, a seleção dos elementos 
é em grupos tendo análise mais ampla e não particular. 
 
11. A quantização uniforme é linear e segue uma análise mais simples, na não linear, 
valores baixos são mais descartados. 
 
 
12. A técnica transforma as estradas em uma soma de funções que se aproximam 
do valor original 
 
13. a) ~(~(~A+B) + ~(~C○D)) ○ ~D 
 
 
 
 
 
 
 
b) Desligado 
c) 
A Ã B Ã+B C ~C D ~C○D ~(Ã+B) ~(~C○D) 
~(Ã+B)+ 
~(~C○D) 
~(~(Ã+B)+ 
~(~C○D)) 
~D X○~D 
F V V V V F V F F V V F F F 
F V V V V F F F F V V F V F 
F V V V F V V V F F F V F F 
F V V V F V F F F V V F V F 
F V F V V F V F F V V F F F 
F V F V V F F F F V V F V F 
F V F V F V V V F F F V F F 
F V F V F V F F F V V F V F 
V F V V V F V F F V V F F F 
V F V V V F F F F V V F V F 
V F V V F V V V F F F V F F 
V F V V F V F F F V V V V V 
A 
B 
C 
D 
V F F F V F V F V V V F F F 
V F F F V F F F V V V F V F 
V F F F F V V V V F V F F F 
V F F F F V F F V V V F V F 
 
14. a) ~((A○B) + (C○D)) 
 b) Ligado 
 c) Tabela verdade 
A B C D A○B C○D (A○B)+(C○D) ~(A○B)+(C○D) 
V V V V V V V F 
V V V F V F V F 
V V F V V F V F 
V V F F V F V F 
V F V V F V V F 
V F V F F F F V 
V F F V F F F V 
V F F F F F F V 
F V V V F V V F 
F V V F F F F V 
F V F V F F F V 
F V F F F F F V 
F F V V F V V F 
F F V F F F F V 
F F F V F F F V 
F F F F F F F V 
 
15. A=1, B=0, C=1 
 a) (A XOR B) + C = 1 
 b) A ○ (B + C) = 1 
 c) A XOR B XOR C = 0 
 d) ~A XOR C = 1 
 e) ~B ○ ~C = 0 
 
 
 
 
 
 
16. Tabela verdade 
 a) (A XOR B) + C 
A B C A XOR B (A XOR B) 
+ C 
1 1 1 0 1 
1 1 0 0 0 
1 0 1 1 1 
1 0 0 1 1 
0 1 1 1 1 
0 1 0 1 1 
0 0 1 0 1 
0 0 0 0 0 
 
b) A○(B+C) 
A B C (B+C) A○(B+C) 
1 1 1 1 1 
1 1 0 1 1 
1 0 1 1 1 
1 0 0 0 0 
0 1 1 1 0 
0 1 0 1 0 
0 0 1 1 0 
0 0 0 0 0 
 
c) A XOR B XOR C 
A B C A XOR B (A XOR B) XOR 
C 
1 1 1 0 1 
1 1 0 0 0 
1 0 1 1 0 
1 0 0 1 1 
0 1 1 1 0 
0 1 0 1 1 
0 0 1 0 1 
0 0 0 0 0 
 
 d) ~A XOR C 
 
 
 
 
A Ã C Ã XOR 
C 
1 0 1 1 
1 0 0 0 
0 1 1 0 
0 1 0 1 
 e) ~B ○ ~C 
 
 
 
 
 
 
17. a) 
101101
+ 1111
111100
 
 
b) 
1000011
𝑥 110
 1000011+
1000011++
110010010
 
 
c) 
 1110
− 101
1000
 
 
d) 
1001
11
= 11 
e) 
1010111
+ 111111 
10010110
 
 
f) 
 11111
− 111
11000
 
 
g) 
10001
𝑥 100
1000100
 
 
h) 
11100010
1010
= 10110 
 
18. Com complemento de 2: 
 a) 1101 + 110, 
 
 1101
+ 110
10011
 .:. = 10011 
 
b) 1000 – 111, 111c2= 001 
 
 1000
+ 0001
 1001
 .:. = 0111 
 
c) 101011 + 101010, 
 
 101011
+ 101010
1010101
 .:. = 1010101 
 
d) 10100 – 1111, 1111c2=0001 
 10100
+ 00001
 10101
 .:. = 01011 
 
B ~B C ~C ~B ○ 
~C 
1 0 1 0 0 
1 0 0 1 0 
0 1 1 0 0 
0 1 0 1 1 
e) 1111 + 1, 
 1111
+ 0001
10000
 .:. = 10000 
 
f) 10001 – 01110, 01110c2= 10010 
 10001
+10010
100011
 .:. = 11 
 
g) 111 + 011, 
 111
+ 011
1010
 .:. = 1010 
 
h) 10101 – 1010, 1010c2= 0110 
 10101
+ 00110
 11011
 .:. = 00101 
 
19. I. A = 1100 e B = 0100; II. A= 10000 e B = 00010; III. A = 11110 e B = 
01111 
 a) A + B, A – B, A x B e A / B 
 I. 
 1100
+ 0100
10000
 
 1100
− 0100
1000
 
 1100
𝑥 0100
110000
 
1100
0100
= 11 
 II. 
 10000
+ 00010
10010
 
 10000
− 00010
01110
 
 10000
𝑥 00010
100000
 
10000
00010
= 1000 
 III. 
 11110
+ 01111
101101
 
 11110
− 01111
01111
 
 11110
𝑥 01111
 11110
 11110+
 11110++
11110+++
111000010
 
11110
01111
= 10 
 b) A AND B, A OR B e A XOR C 
 I. A AND B = 1100 ○ 0100 = 0100 A OR B = 1100 OR 0100 = 1100 
 A XOR B = 1100 XOR 0100 = 1000 
 II. A AND B = 10000 ○ 00010 = 00000 A OR B = 10000 OR 00010 = 10010 
 A XOR B = 10000 XOR 00010 = 10010 
 III. A AND B = 11110 ○ 01111 = 01110 A OR B = 11110 OR 01111 = 11111 
 A XOR B = 11110 XOR 01111 = 10001 
 
 
20. a) AB + A̅B + ABC + ABC̅ = 
B(A +A̅) + AB(C+C̅) = B1 + AB1= B(1+A) = B 
b) ABC + A̅BC + AB̅C + AB̅C̅ = BC(A+A̅) + AB̅(C+C̅) = BC1 + AB̅1 
 
 
c) A • (AB̅̅ ̅̅ ) • (A+B̅̅ ̅̅ ̅̅ ) = A(A̅+B̅)( A̅ • B̅) = 0 
 
A 
B 
C