aula06_entropia

Prévia do material em texto

BC-0504: Natureza da Informação
 
Introdução a Teoria da Informação
Slides baseados no material do
Prof. Fabrício Olivetti e Profa. Mirtha Lina
Teoria da Informação
• Em 1948, um engenheiro-matemático mostrou que a 
informação poderia ser medida e quantificada.
 
Claude E. Shannon (1916-2001), considerado o pai da Teoria da Informação, 
e seu livro publicado em 1949, Teoria Matemática da Comunicação.
Introdução
• Após terminar o seu doutorado no MIT, em 1940, 
Shannon foi trabalhar na Bell Labs.
 
• Bell Laboratories: pesquisa da AT&T 
(American Telephone and Telegraph Company)
• Fundada em 1920s para pesquisa em comunicações.
• Busca de alta-qualidade de som (gravação), 
transmissão de TV, telefonia e diferentes canais de 
comunicação.
Introdução
• Perguntas: 
• Como representar e transmitir informação de forma 
eficiente?
• Quais são os limites teóricos para sua representação 
e transmissão através de um canal com ruído?
Introdução
• Respostas satisfatórias e surpreendentes:
• Medida de informação (entropia)
• Medida da capacidade de um canal para transmitir 
informação
• A codificação para utilizar o canal em toda sua 
capacidade:
 Codificação da fonte (representação compacta)
 Codificação do canal (detecção e correção de 
erros)
Unidade Fundamental de 
Informação
 A quantidade de informação de uma fonte ou um 
receptor está associada com a incerteza com 
que a informação é gerada ou recebida
 A incerteza pode ser mensurada usando a 
probabilidade de ocorrência dos símbolos da 
mensagem
Unidade Fundamental de 
Informação
 A saída de uma fonte discreta poder modelada 
como uma variável aleatória discreta S = {s
1
, 
s
2
, …, s
k
} e uma função de distribuição de 
probabilidades p : S → [0, 1] tal que
 Portanto a incerteza de cada símbolo deve ser 
uma função da sua probabilidade, i.e.
 I(s) = f(p(s)) e se p(s) = 1, I (s) = 0
∑
s�S
p ( s )=1
Unidade Fundamental de 
Informação
 A quantidade de informação é uma grandeza não 
negativa
� I(s)≥0, evento produz informação ou não, 
mas nunca uma perda de informação
 A medida de informação deve ser uma função 
contínua (na verdade, monótona) da função de 
probabilidade
� Pequenas alterações na probabilidade devem 
resultar em pequenas alterações na 
quantidade de informação
Unidade Fundamental de 
Informação
 O símbolo "menos provável de ocorrer" 
transmite mais informação, i.e. p(s
j
) < p(s
k
) 
⟹ I (s
j
) > I (s
k
)
 Se s
j
 e s
k
 são independentes I (s
j
s
k
) = I (s
j
) 
+ I (s
k
)
� A informação associada à ocorrência de dois 
eventos independentes é a soma da 
informação de cada um
Unidade Fundamental de 
Informação
 A base b determina a unidade de medida de 
informação
� Usualmente b = 2 (pode ser omitida) e a 
unidade é bits
 I(s) pode ser interpretada como o número 
mínimo de símbolos na base b necessários para 
codificar um símbolo, mensagem, evento, 
informação s
I ( s )=− logb p (s )=log b( 1p ( s ) )
BIT
 Considere o seguinte experimento:
 Lançamento de uma moeda honesta
 2 resultados: cara ou coroa
BIT
 Considere o seguinte experimento:
 Lançamento de uma moeda honesta
 2 resultados: cara ou coroa
 Pergunta
 Como podemos transmitir o resultado (da maneira 
mais compacta possível)?
BIT
 Considere o seguinte experimento:
 Lançamento de uma moeda honesta
 2 resultados: cara ou coroa
 Pergunta
 Como “Alice” poderia transmitir o resultado 
observado no experimento para “Bob”?
BIT
 Considere o seguinte experimento:
 Lançamento de uma moeda honesta
 2 resultados: cara ou coroa
 Pergunta
 Como “Alice” poderia transmitir o resultado 
observado no experimento para “Bob”?
.Cara / Coroa
-> 1 / 0
-> 1 bit
1
BIT
 Considere o seguinte experimento:
 2 lançamentos de uma moeda honesta
BIT
 Considere o seguinte experimento:
 2 lançamentos de uma moeda honesta
 4 possíveis resultados:
(1 = Cara, 0 = Coroa)
.11
.10
.01
.00
BIT
 Considere o seguinte experimento:
 2 lançamentos de uma moeda honesta
 4 possíveis resultados:
 “Alice” transmite o resultado observado para 
“Bob”:
(1 = Cara, 0 = Coroa)
.11
.10
.01
.00
2 bits
10
BIT
 Similarmente, o resultado de um experimento 
com 8 possíveis resultados equiprováveis...
 “Alice” transmite o resultado observado para 
“Bob”:
3 bits
(1 = Cara, 0 = Coroa)
.111
.110
.101
.100
...
101
BIT
 Similarmente, o resultado de um experimento 
com 2n possíveis resultados equiprováveis...
 “Alice” transmite o resultado observado para 
“Bob”:n bits
1011...
BIT
 Similarmente, o resultado de um experimento 
com 2n possíveis resultados equiprováveis...
 “Alice” transmite o resultado observado para 
“Bob”:
n bits
#res #bits
2 1
4 2
8 3
... ...
2n n
BIT
 Propriedades da função “log”
log(2^n) = n*log(2)
 = n
BIT
 Nos exemplos anteriores,
 A quantidade de informação é o logaritmo na base 
2 do número de resultados equiprováveis.
#res #bits
2 log(2) = 1
4 log(4) = 2
8 log(8) = 3
... ...
2n log(2n) = n
BIT
 Nos exemplos anteriores,
 A quantidade de informação é o logaritmo na base 
2 do número de resultados equiprováveis.
#res #bits
2 log(2) = 1
4 log(4) = 2
8 log(8) = 3
... ...
2n log(2n) = n
p log(1/p)
1/2 log(1/(1/2)) = 1
1/4 log(1/(1/4)) = 2
1/8 log(1/(1/8)) = 3
... ...
1/(2n) log(1/(1/2n)) = n
Valor Esperado
Digamos que eu faça uma aposta: em um jogo de 
cara ou coroa, se der cara eu ganho R$ 1,00; se 
der coroa, não ganho nada.
Estatisticamente posso dizer que espero ganhar 
R$ 0,50.
Isso porque eu tenho igual probabilidade de 
ganhar ou não.
Valor Esperado
O valor esperado é calculado como:
p(cara)*valor(cara) + p(coroa)*valor(coroa) =
= 0.5*1 + 0.5*0 = 0.5
Isso significa que, ao participar do jogo várias 
vezes, espero ganhar em média 50 centavos por 
jogo (mas em uma jogada não vou ganhar isso).
Valor Esperado
Se temos uma variável aleatória R, podemos 
definir seu valor esperado como:
H (R )=E=∑
x�R
x p (R=x )
Medindo Informação
Digamos que temos uma fita colorida
Medindo Informação
Digamos que temos uma variável aleatória que é 
um ponto nessa fita (mediremos apenas a 
coordenada do eixo horizontal).
Medindo Informação
A única informação que temos desse ponto é a cor 
da posição que ele se encontra.
Medindo Informação
Digamos que podemos representar o estado como 
uma sequência de 0s e 1s da seguinte forma:
Se o primeiro bit for 0, o ponto está na 
primeira metade, se for 1, está na segunda 
metade
Medindo Informação
001
Medindo Informação
Digamos que nosso ponto resultou na cor verde. 
Sabemos que os 2 primeiros bits dele deve ser 
com certeza 00.
Medindo Informação
Se a cor for vermelha: 010.
Medindo Informação
Se a cor for amarela: 011.
Medindo Informação
Se a cor for azul: 1
Medindo Informação
Dependendo da cor de nossa variável aleatória, 
podemos ter de 1 a 3 bits de informação!!
Medindo Informação
Qual o Valor Esperado de bits de informação de 
uma variável aleatória R, dado os 4 valores 
possíveis?
Verde = 2 bits
Vermelho = 3 bits
Amarelo = 3 bits
Azul = 1 bit
Medindo Informação
Qual o Valor Esperado de bits de informação de 
uma variável aleatória R, dado os 4 valores 
possíveis?
P(Verde) = 1/4
P(Vermelho) = 1/8
P(Amarelo) = 1/8
P(Azul) = 1/2
Medindo Informação
Qual o Valor Esperado de bits de informação de 
uma variável aleatória R, dado os 4 valores 
possíveis?
E(R) = 2 . 1/4 + 3 . 1/8 + 3 . 1/8 + 1 . 1/2
 = 1/2 + 3/4 + 1/2 
 = 1,75
Medindo Informação
Reparem que quanto menor a área de uma cor, 
maior a informação e menor a probabilidade da 
variável cair nela.
A cada divisão da área por 2:
Aumentamos a informação em 1 bit
Reduzimos a probabilidade em um fator de 1/2
Medindo Informação
Se temos uma única cor, temos que cada medição 
não nos dá nenhum bit de informação.
Se criarmos uma novacor, dividindo a fita ao 
meio, temos que cada cor nos informa 1 bit de 
informação.
Se dividirmos uma das cores em duas novas cores, 
cada uma delas informa 2 bits.
Medindo Informação
1 bit representa 21 = 2 possibilidades.
2 bits representam 22 = 4 possibilidades.
...
Se uma cor tem chance de ser escolhida com 
probabilidade = 1/4, temos que ela representa 
uma entre quatro possibilidades, ou 2 bits.
Medindo Informação
De forma geral:
2b = 1/P(R=x)
Ou, o número de bits é igual ao inverso da 
probabilidade de obtermos um certo valor.
Medindo Informação
log
2
(2b) = b
I(R=x)= log
2
(1/P(R=x))
A quantidade de informação (bits) de uma 
variável aleatória é o logaritmo na base 2 do 
inverso da probabilidade de ela dar certo valor 
x.
Medindo Informação
•  
Medindo Informação
A entropia dessa fita é:
E(R) = -(¼.log(1/4) + 1/8.log(1/8) + 
1/8.log(1/8) + ½.log(1/2) = 1.75
ou o valor esperado de bits!
Entropia: propriedades
No caso de eventos binários, a informação por 
símbolo é dada por:
H
Maior entropia 
para casos 
equiprováveis
p
p
p
p
p
pH
ii
i 

1
1
log*)1(
1
log*
1
log*
Entropia: propriedades
H
.Moeda honesta:
 p = 1/2 = 1-p
 H = 1/2*log2(1/(1/2)) + 1/2*log2(1/(1/2))
 = log2(2)
 = 1 bit por símbolo
Entropia: propriedades
H
.Moeda viesada:
 p = 0.6; 1-p = 0.4
 H = 0.6*log2(1/0.6) + 0.4*log2(1/0.4)
 = 0.971 bit por símbolo
Entropia: propriedades
H
.Moeda viesada:
 p = 0.9
 H = 0.9*log2(1/0.9) + 0.1*log2(1/0.1)
 = 0.469 bit por símbolo
Entropia: propriedades
• Observações
• Para casos equiprováveis, H é máximo.
• A incerteza é máxima.
H
p
Entropia: propriedades
• Observações
• Para casos equiprováveis, H é máximo.
• A incerteza é máxima.
• Para p = 0 ou p = 1, H = 0
• Nestes casos, o resultado é certo: 
não há incerteza, nem informação a ser “aprendida”.
H
p
Entropia Alta
Entropia Baixa
JOGO DAS 20 
PERGUNTAS
20 Perguntas
• Jogo que envolve duas pessoas
• Uma pessoa pensa em um objeto
• A outra pessoa pode fazer 20 perguntas de “sim 
ou não” para tentar adivinhar qual é esse objeto
20 Perguntas
Vamos ver uma maneira estúpida de jogar o jogo:
É um 
sapato?
20 Perguntas
Vamos ver uma maneira estúpida de jogar o jogo:
É um 
óculos?
20 Perguntas
Vamos ver uma maneira estúpida de jogar o jogo:
É um 
livro?
20 Perguntas
Podemos fazer melhor que isso...
É um 
livro?
Vamos jogar 20 questões
Uma forma mais racional de jogar esse jogo é 
escolher as questões com maior Entropia, ou seja, 
aquelas que te dão 1 bit de informação!
Essas questões são aquelas que tem a maior 
incerteza, ou seja, 50% de chances de ter uma das 
respostas (sim ou não).
Vamos jogar 20 questões
Na prática é difícil saber quais perguntas dividem 
nossas dúvidas pela metade, mas podemos intuir!
20 Perguntas
Vamos escolher melhor as perguntas!
Você 
veste no 
corpo?
20 Perguntas
Vamos escolher melhor as perguntas!
Você usa 
na 
faculdade?
20 Perguntas
Vamos escolher melhor as perguntas!
Usa 
bateria?
20 Perguntas
Vamos escolher melhor as perguntas!
Posso 
fazer 
contas 
nela?
20 Perguntas
Mesmo assim nem sempre acertaremos...
É um 
celular?
20 Perguntas
Vamos pensar nesse jogo de outra maneira! 
Quantas perguntas temos que fazer para descobrir 
qual animal dentre os abaixo eu estou pensando?
20 Perguntas
O objetivo é defnir o menor conjunto de perguntas 
possível que me traga a certeza da resposta.
20 Perguntas
Vamos jogar da maneira burra! Precisamos de 
quantas perguntas para descobrir o animal?
 É uma vaca?
 É uma baleia?
 É um pinguim?
 É um morcego?
 É um cachorro?
 É um ornitorrinco?
20 Perguntas
Não sejamos tão burros!
 É uma vaca?
 É uma baleia?
 É um pinguim?
 É um morcego?
 É um cachorro?
 É um ornitorrinco?
20 Perguntas
Precisamos de 5 perguntas para determinar o 
animal que estamos pensando! Ou seja, precisamos 
de no máximo 5 bits para ganhar o jogo!
 É uma vaca?
 É uma baleia?
 É um pinguim?
 É um morcego?
 É um cachorro?
20 Perguntas
Cada bit representa uma pergunta!
 É uma vaca?
 É uma baleia?
 É um pinguim?
 É um morcego?
 É um cachorro?
20 Perguntas
Qual a probabilidade de acertamos a resposta 
usando apenas 1 bit??
 É uma vaca? 
 É uma baleia?
 É um pinguim?
 É um morcego?
 É um cachorro?
20 Perguntas
Na verdade, para todas as perguntas temos 1/6 de 
chance de acertar a resposta. Exceto na última 
pergunta (por que?):
 É uma vaca? P(1 bit) = 1/6
 É uma baleia? P(2 bits) = 1/6
 É um pinguim? P(3 bits) = 1/6
 É um morcego? P(4 bits) = 1/6
 É um cachorro? P(5 bits) = 2/6
20 Perguntas
•  
20 Perguntas
•  
20 Perguntas
E se pensarmos em perguntas melhores?
 Bota ovo?
 Tem asas?
 É carnívoro?
 Nada?
20 Perguntas
Qual a probabilidade do animal escolhido botar 
ovo?
bota ovo?
0 1
4/6 2/6
20 Perguntas
Sabendo disso, qual a probabilidade de ele ter asas 
também?
bota ovo?
0 1
4/6 2/6
1/6
3/6
1/61/6
20 Perguntas
Daqueles que não tem asas e nem botam ovos, 
quais são carnívoros?
bota ovo?
0 1
4/6 2/6
1/6
3/6
1/61/6
1/6
2/6
20 Perguntas
Finalmente, quais nadam?
bota ovo?
0 1
4/6 2/6
1/6
3/6
1/61/6
1/6 2/6
1/6 1/6
20 Perguntas
Apenas com a primeira pergunta, não podemos 
descobrir o animal!
bota ovo?
0 1
4/6 2/6
1/6
3/6
1/61/6
1/6 2/6
1/6 1/6
20 Perguntas
Mas na segunda pergunta temos 3 situações que 
encontra a resposta: 3.1/6.2bits
bota ovo?
0 1
4/6 2/6
1/6
3/6
1/61/6
1/6 2/6
1/6 1/6
20 Perguntas
Na terceira pergunta temos mais uma situação que 
encontra a resposta: 3.1/6.2bits + 1/6.3bits
bota ovo?
0 1
4/6 2/6
1/6
3/6
1/61/6
1/6 2/6
1/6 1/6
20 Perguntas
Na quarta pergunta temos a resposta fnal: 
3.1/6.2bits + 1/6.3bits + 2.1/6.4bits
bota ovo?
0 1
4/6 2/6
1/6
3/6
1/61/6
1/6 2/6
1/6 1/6
20 Perguntas
Em média precisaremos de:
3.1/6.2bits + 1/6.3bits + 2.1/6.4bits
=
1/6 . (6 + 3 + 8) = 17/6 = 2,83 bits
20 Perguntas
Reparem que a cada pergunta as chances de 
descobrirmos a resposta aumenta 
signifcativamente: bota ovo?
0 1
4/6 2/6
1/4
2/4
1/21/2
1/3 2/3
1/2 1/2
Efciência
•  
Efciência
•  
Efciência e Redundância
•  
20 Perguntas
Precisamos encontrar a estratégia de perguntas 
que nos traga o maior rendimento ou a menor 
redundância.
Entropia Condicional
Para escolhermos perguntas interessantes temos 
que saber qual pergunta transforma o nosso 
sistema em um de entropia alta (incerteza) para um 
de entropia baixa (certeza).
A pergunta que queremos fazer é: se soubermos a 
resposta da pergunta X, quão incerto será nosso 
sistema Y?
H(Y|X) = se soubermos o estado da variável X, o 
que podemos afrmar sobre a variável Y?
Entropia Condicional
•  
Entropia Condicional
•  
Entropia Condicional
•  
Entropia Condicional
•  
Entropia Condicional
•  
Entropia Condicional
•  
Entropia Condicional
•  
Entropia Condicional
•  
bota ovo?
1/4 1/2
p(x=0)=2/3 p(x=1)=1/3
Entropia Condicional
•  
Entropia Condicional
•  
Entropia Condicional
•  
Entropia Condicional
•  
Entropia Condicional
•  
nada?
1/3 1/3
p(x=0)=1/2 p(x=1)=1/2
Entropia Condicional
•  
Entropia Condicional
Saber que o animal bota ovo ou não deixa nosso 
sistema com entropia 1,67.
Saber se o animal nada ou não deixa nosso sistema 
com entropia 1,58.
Fica claro que a segunda pergunta reduz mais a 
incerteza do nosso sistema.
Ganho de Informação (Inf. Mútua)
Vamos defnir então a medida de ganho de 
informação:
GI(X,Y) = H(Y) – H(Y|X)
ou seja, em quanto a entropia do sistema é 
reduzida ao conhecer a variável X.
Essa medida também é conhecida como Informação 
Mútua ( I(X,Y) ) que mede a dependência de duas 
variáveis.
Ganho de Informação (Inf. Mútua)
Com a defnição do ganho de informação, vamos 
escolher, em sequência, as perguntas que nos 
trazem o maior GI.
Bota ovo?
Tem asas?
É carnívoro?
É mamífero?
Ele nada?
Ganho de Informação (Inf.Mútua)
Com a defnição do ganho de informação, vamos 
escolher, em sequência, as perguntas que nos 
trazem o maior GI.
H(Y) = 2,58
Bota ovo? H(Y|X) = 1,67
Tem asas? H(Y|X) = 1,67
É carnívoro? H(Y|X) = 1,67
É mamífero? H(Y|X) = 1,93
Ele nada? H(Y|X) = 1,58
Ganho de Informação (Inf. Mútua)
Com a defnição do ganho de informação, vamos 
escolher, em sequência, as perguntas que nos 
trazem o maior GI.
H(Y) = 2,58
Bota ovo? H(Y|X) = 1,67GI(X,Y)=0,91
Tem asas? H(Y|X) = 1,67 GI(X,Y)=0,91
É carnívoro? H(Y|X) = 1,67 GI(X,Y)=0,91
É mamífero? H(Y|X) = 1,93GI(X,Y)=0,64
Ele nada? H(Y|X) = 1,58 GI(X,Y)=0,99
Ganho de Informação (Inf. Mútua)
Com a defnição do ganho de informação, vamos 
escolher, em sequência, as perguntas que nos 
trazem o maior GI.
H(Y) = 2,58
Bota ovo? H(Y|X) = 1,67GI(X,Y)=0,91
Tem asas? H(Y|X) = 1,67 GI(X,Y)=0,91
É carnívoro? H(Y|X) = 1,67 GI(X,Y)=0,91
É mamífero? H(Y|X) = 1,93GI(X,Y)=0,64
Ele nada? H(Y|X) = 1,58 GI(X,Y)=0,99
Ganho de Informação (Inf. Mútua)
A primeira pergunta que devemos fazer é se ele 
nada! Qual a próxima pergunta?
H(Y) = 2,58
Bota ovo? H(Y|X) = 1,67GI(X,Y)=0,91
Tem asas? H(Y|X) = 1,67 GI(X,Y)=0,91
É carnívoro? H(Y|X) = 1,67 GI(X,Y)=0,91
É mamífero? H(Y|X) = 1,93GI(X,Y)=0,64
Ele nada? H(Y|X) = 1,58 GI(X,Y)=0,99
Ganho de Informação (Inf. Mútua)
A primeira pergunta que devemos fazer é se ele 
nada! Qual a próxima pergunta?
nada?
ovo? ovo?
p(~x)=1/2
p(~x) = 1/6
p(y|x) = 1/3 1 1/2
p(x) = 1/3
Ganho de Informação (Inf. Mútua)
A primeira pergunta que devemos fazer é se ele 
nada! Qual a próxima pergunta?
nada?
ovo? ovo?
p(~x)=1/2
p(~x) = 1/6
p(y|x) = 1/3 1 1/2
p(x) = 1/3
~x = não 
nada e nem 
bota ovo
~x = nada 
e não bota 
ovo
x = nada e 
bota ovo
Ganho de Informação (Inf. Mútua)
•  
nada?
ovo? ovo?
p(y|x) = 1/3 1 1/2
p(~x)=1/2
p(~x) = 1/6 p(x) = 1/3
Ganho de Informação (Inf. Mútua)
Note que:
p(x) representa a probabilidade de todas as 
perguntas já feitas. Ex.: probabilidade do animal 
escolhido não nadar e não botar ovo.
As ramifcações que tem apenas uma escolha 
podem ser desconsideradas da soma, pois p(Y|X)=1 
e log(p(Y|X)) = 0.
Ganho de Informação (Inf. Mútua)
A primeira pergunta que devemos fazer é se ele 
nada! Qual a próxima pergunta?
H(Y) = 1,58 (já sabemos se nada ou não)
Bota ovo? H(Y|X) = 1,12GI(X,Y)=0,46
Tem asas? H(Y|X) = 0,67 GI(X,Y)=0,91
É carnívoro? H(Y|X) = 1,12 GI(X,Y)=0,46
É mamífero? H(Y|X) = 1,12GI(X,Y)=0,46
Ganho de Informação (Inf. Mútua)
nada?
asas? asas?
1 1/2 11/2
Ganho de Informação (Inf. Mútua)
E agora? (dica: já teremos certeza se é morcego ou 
pinguim)
H(Y) = 0,67 (já sabemos se nada ou não)
Bota ovo? H(Y|X) = 0,33 GI(X,Y)=0,33
É carnívoro? H(Y|X) = 0,33 GI(X,Y)=0,33
É mamífero? H(Y|X) = 0,67 GI(X,Y)=0,0
Ganho de Informação (Inf. Mútua)
E agora? (dica: só não sabemos quando ele não 
bota ovo, não nada e não voa)
H(Y) = 0,33
É carnívoro? H(Y|X) = 0,00GI(X,Y)=0,33
É mamífero? H(Y|X) = 0,33GI(X,Y)=0,0
Ganho de Informação (Inf. Mútua)
E nada se ganha em saber se é mamífero ou não.
H(Y) = 0,33
É carnívoro? H(Y|X) = 0,00GI(X,Y)=0,33
É mamífero? H(Y|X) = 0,33GI(X,Y)=0,0
Ganho de Informação (Inf. Mútua)
A ordem das perguntas fcou:
Ele nada?
Ele tem asas?
Ele bota ovos?
Ele é carnívoro?
Ele é mamífero?
Ganho de Informação (Inf. Mútua)
Note que as possibilidades de representação fca:
01 - morcego
0000 - vaca
0001 - cachorro
100 - baleia
101 - ornitorrinco
11 – pinguim
Ganho de Informação (Inf. Mútua)
•  
Ganho de Informação (Inf. Mútua)
Resumindo:
Nossa primeira estratégia deu uma média de 3,33 
bits.
A segunda estratégia deu uma média de 2,83 bits.
A estratégia de ganho de informação deu 3 bits.
A entropia nos diz que não podemos fazer melhor 
que 2,58 bits.
Ganho de Informação (Inf. Mútua)
asas? asas?
ovo?
carnívoro?
nada?
1
1
1
1
0
00
0
0
ovo?
1
0
Bibliografa
• C. Seife. Decoding the Universe. Penguin Books. 2006.
• Notas de aula do curso de Informação e Entropia do 
MIT. http://ocw.mit.edu/courses/electrical-engineering-
and-computer-science/6-050j-information-and-entropy-
spring-2008/
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. 
Introduction to Algorithms. The MIT Press. 3rd Edition. 
2009.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70
	Slide 71
	Slide 72
	Slide 73
	Slide 74
	Slide 75
	Slide 76
	Slide 77
	Slide 78
	Slide 79
	Slide 80
	Slide 81
	Slide 82
	Slide 83
	Slide 84
	Slide 85
	Slide 86
	Slide 87
	Slide 88
	Slide 89
	Slide 90
	Slide 91
	Slide 92
	Slide 93
	Slide 94
	Slide 95
	Slide 96
	Slide 97
	Slide 98
	Slide 99
	Slide 100
	Slide 101
	Slide 102
	Slide 103
	Slide 104
	Slide 105
	Slide 106
	Slide 107
	Slide 108
	Slide 109
	Slide 110
	Slide 111
	Slide 112
	Slide 113
	Slide 114
	Slide 115
	Slide 116
	Slide 117
	Slide 118
	Slide 122
	Slide 123
	Slide 127
	Slide 130
	Slide 131
	Slide 132
	Slide 133
	Slide 134
	Slide 135
	Slide 136
	Slide 137