A B C D E F G H I J K L M N O P Q R S T U V X Z


Hamming:
Propriedades do código de Hamming (7,4): minima / detectar / as pala tem comp 7 e 4
Familia Hamming: (15,x) (31,x)
Conta (3,1) c/ 0.19: (1-0.19)^3 + (1-0.19)^2 * 3 * 0.19
Conta (7,4) c/ 0.02: (1-0.02)^7 + (1-0.02)^6 * 7 * 0.02
Códigos de Hamming quantos bits: 2^m -1 - m
Códigos de Hamming total: 2^m-1


Capacidade de canais:
Propriedades da capacidade de canal: a cap é um num não neg / C <= log |X| /C <= log |Y| / Mede-se em bits, harleys ou nats
Capacidade de um canal calc: se for matrix grande é o pivot se for 2x2 1-(-val1*log2val1 - val2*log2val2)
Definição da capacidade de um canal: C = maxp(x) I(x,y)


Canais sem memória:
Class. canais: p[0.8 0.2 0.8 0.2] - simétrico
Class. canais: p[0.9 0 0.1 0.1 0 0.9] - canal com perdas (erasure channel)
Concate canais: a conc de canais apenas / Ps todos com Pn...P2P1 / Peq = Pn sem erasure
Caract de um canal OR: p[0.5 0 0.5 1]
Caract de um canal XOR: p[0.75 0.25 0.75 0.25]
Caract de um canal AND: p[1 0.5 0 0.5]
Carac. de um canal discreto sem memória: p(y | x)
Carac. de um canal discreto sem memória c/ matriz 2x3: card entra 3 e saida 2


Códificação aritmética:
Teórica: A,N e S (1/2), (1/3) e (1/6) / 10 bits (...) Fx / F(ANANAS) = p(AA) (...)
Teórica: a comp. é superior a do Huffman / O algo. consiste em det.uma unica palavra


Compressão Shannon-Fano-Elias:
Teórica: l(x) = [-log2p(x)] + 1 / Formula com o somatório




Código Lempel-Ziv:
Compressão LZ78 abccba:  (0,a), (0,b), (0,c) (3,b), (1,EOF)





Compressão de Dados
Códigos instantaneos: C1, nâo-singulares: C1,C2,C3 (instantaneos: 0 10 11, nâo-singulares: Não pode haver nums repetidos)
Comp. médio: p(A) * tam + p(B) * tam + p(C) * tam
Desigualdade de Kraft: E2^-l(x)<=1; Existe (...) 2,3,1,3 e frase grande
Formu. prob. compre: Minimizar Ep(x)l(x) com restricao E2^-l(x)<=1

Huffman adap:
Cod. huffman adap: "S0A00LL1111" -> SALAS
Téorica: (...) permite e (...) manipula

Cód. Shannon:
Teórica: (...) l(x) (...) F(x) e l(x) = [-log2p(x)] e ordem decrescente e F(x) = Ei<xp(i)

Téorica 2: CS não é ótimo (...)  e 2 passagens no ficheiro
Ineficiência: (...) D(p||q), onde q(x) = 2^-l(x) e p(x) é a dist. de prob. real dos simb do alfa.
H(x) <= L(c) < H(x) + 1



Cód Huffman:
Teórica: O cod. huffman é ótimo (...) e Para comprimir um file (...) 2 passagens
H(x) <= L(c) < H(x) + 1
Calc: quando: p(a) = 0.1, p(b) = 0.2, p(c) = 0.7, é o a = 00, b = 01, c = 1 aka C1

Cadeias de Markov:
Período de um est. de uma CM: Só pode ser visitado em instantes de tempo multiplos de N
Existência e unicidade da dist. estacio: Ser aperiódica e Ser irredutivel
Entropia cond. de uma CM: a prob trans: 0.6, logo, -0.6log2(0.6)-0.4log2(0.4) = 0.97
Dist. esta. de uma CM c/ uma unica dist.: P=0.5, 0.5, 0.5, 0.5
Dist. esta. de uma CM c/ infinitas dist.: P=1, 0, 0, 1
Dist. esta. de uma CM Não tem dist.: P=0, 1, 1, 0
Dist. esta. de uma CM calc: o val para onde vai / pela soma do val das transicoes
Dist. esta. de uma CM: Em geral uma CM pode ter 0, 1 ou infi. (...) e Formula
CM: on on e processo estocástico e cadeia de markov e binaria independente
CM estado de func de um serv: independente / formula / online, ausencia de mensagem
CM irredutivel: é possivel transitar (...)

Entropia e Informação:
Desiguadades: H(x|y) <= H(x) / 0 <= I(x,y) <= min(H(x), H(y)) / 0 <= H(x) <= log2|x|
Desigualdades var indep: I(x,y) = 0 / H(x,y) = H(x) + H(y) / H(x|y) = H(x)
Entropia: bits, harleys ou nats / medida da incerteza associada / moeda 2 faces é 0 bits / num real nao negativo / uma fonta info (...) 0 bits
Entropia cond: H(x,y) - H(y) / H(x) - I(x,y) / H(x,y) - I(x,y) - H(y|x)
Entro. cond e info mutua: H(x) + H(y) - I(x,y) / H(x) + H(y|x)
Informação mutua: I(x,x) (...) H(x) / mede o grau de dependencia / bits, harleys ou nats / num real não negativo
Surpresa alunos: reprovados: -log2(1-p(x)) / aprovados: -log2(p(x))