Introdução à Telemática
Teoria da Informação
M.Sc. Engenharia de Sistemas
Prof. Sérgio Campello
Informação
• O que é informação?
2
Informação
• Não há definição formal.
• Capacidade de alterar: o ambiente, as
propriedades, as reações, etc.
3
Entropia
• Da química, mede o grau de
desorganização do meio.
• Função para medir a quantidade de
informação.
4
,
Entropia
• Fonte de informação X. Valores {x1,
x2,...,xN} e probabilidades {p1, p2, ... ,pN}.
•
N
HX =
n=1
1
pn log
pn
• Se a fonte é binária temos:
1
1
H X = p0 log + p1 log
p0
p1
• e
1
1
H X = p log + (1 − p) log
p
1−p
Gráfico da entropia para uma fonte
binária.
• A entropia é máxima quando p = 1/2
1
1
H X = p log + (1 − p) log
p
1−p
Entropia
• A entropia é máxima quando p = 50%.
• O que isso significa?
• Fornecer uma informação com
probabilidade de ocorrência de 50%
causa máxima entropia. O que isso quer
dizer?
7
Entropia
• Se fornecemos uma informação que tem
probabilidade zero de ocorrer não
causamos nenhuma alteração no estado
pois já se sabia que aquilo não ocorreria.
• Se fornecemos uma informação que tem
probabilidade UM de ocorrer não
causamos nenhuma alteração no estado
pois já se sabia que aquilo IRIA ocorrer.
8
Exemplo
• Sugestão com p = 1/2 , extrai mais
informação
• P{Xa = 1} = 0,19815 -> H(Xa) = 0,7182 bits
• P{Xb = 1} = 0,52132 -> H(Xb) = 0,9987 bits
Transporte da Informação
Transporte da Informação
• Modulação – adequação ao meio para o
correto transporte da equação.
Informação
“onda” Modulada
11
Transporte da Informação
• AM – Modulação em amplitude
• FM – Modulação em frequência
12
Transporte da Informação
• PM – Modulação em Fase
13
Modulação
• A modulação depende do meio físico de
transmissão e dos objetivos da
transmissão.
• Fibras ópticas, cabos metálicos, ar, água,
etc.
• Digital x Analógica
14
Digital x Analógica
• O que quer dizer analógica?
• O que quer dizer digital? Quando um sinal
é considerado digital?
• Qual é mais preciso?
• Qual é mais imune a ruídos?
• Qual dá a melhor qualidade final?
15
Transmissão da informação digital
• Agora que sabemos que o formato digital
é melhor para transmitir informações à
distância, como proceder para transmitir a
informação?
16
Codificação
• Vamos criar um código para transmitir a
palavra: CAFÉ
• Regras
– Símbolos com até 4 dígitos
– Símbolos com até 4 dígitos binários
– Os códigos são unicamente decifráveis?
– Os códigos são ótimos?
– Se conhecermos as probabilidades podemos
melhorar o código?
17
Código de huffman
• Ordenam-se os símbolos por ordem
decrescente de probabilidade
• Agrupam-se os dois símbolos com menor
probabilidade em um “super símbolo” com
probabilidade igual a soma das
probabilidades
• Se o alfabeto restante possuir dois ou mais
símbolos volta-se ao primeiro passo.
• Percorre-se a árvore ordenada de símbolos
atribuindo aleatoriamente 0 ou 1 a cada folha
da árvore
18
Código de huffman - Exemplo
•
•
•
•
•
•
•
{a,b,c,d} – {0.1, 0.25, 0.2, 0.45}
{d, b, c, a} - {0.45, 0.25, 0.2, 0.1} – ord.
{d, b, (a,c)} - {0.45, 0.25, 0.3}
{d, (a,c), b} - {0.45, 0.3, 0.25} – ord.
{d,((a,c),b)} - {0.45, 0.55}
Reordenando e reagrupando:
{((a,c),b,d)} – {1}
19
Código de huffman - Exemplo
• Os super símbolos vão sendo agrupados
em árvore.
20
Código de huffman - Exemplo
• Atribui-se 1 ou 0 aleatoriamente a cada
ramo ou folha.
21
Código de huffman - Exemplo
•
•
•
•
•
Código final
D–1
B – 00
C – 011
A - 010
22
Código de huffman - Exemplo
• Qual a vantagem deste código?
• Ele é único?
• É decodificável Unicamente?
23
Obtenção das probabilidades de
uma língua
• Como obter a probabilidade de uma
língua?
• O cálculo sempre retornará os mesmos
resultados?
24
Proteção da informação
•
•
•
•
•
Como proteger uma informação?
Como é a proteção atual da informação?
Como ela funciona?
É indecifrável?
Por que é segura?
25
Aplicação de Teoria da Informação
Ambiente de uso para comunicação
e entretenimento.
•
•
•
•
Funcionalidades
T9
Aplicativo Facilitador de Escrita (AFE)
Jogo da Memória
RSS
Aplicativo T9
• 12 Botões grandes
• Permite mudar a base
Do dicionário
• Funciona com e sem
previsão
• 3 modos de funcionamento:
– Manual (SRO)
– Automático
– Joystick
• Possui teclado numérico
•
Implementação T9
• Para cada botão é atribuído Botão
ABC
um número.
DEF
• Ao iniciar o ambiente é
GHI
carregada a lista palavras
...
em 2,1 segundos.
WXYZ
• Para cada palavra é atribuída
uma chave.
Chave
• Um dicionário guarda o
2272
Mapeamento
78376
266432
(Chave -> Palavra)
24672
2272
Número
2
3
4
...
9
Palavra (valor)
Casa
Quero
Comida
Agora
Abra
Funcionamento
• Com previsão, ao clicar em um botão é
feita uma busca pela chave e retornado as
palavras prováveis.
• Sem previsão (modo ditar), o usuário
efetua vários cliques.
Botão
Letra
Clique(com
previsão)
Cliques (sem
previsão)
Abc
A
1
1
Ghi
G
1
1
mnO
O
1
3
pqRs
R
1
3
Abc
A
1 (Opcional)
1
Desambiguação
• Feita na tela de opções: a seguir exemplo
da palavra “casa” que possui a mesma
chave de “abra” que é 2272.
Análise do T9
• Resultados satisfatórios
• Fornecida interface para resolução de
problemas de ambiguidade
• Dificuldades de utilização por pessoas
com redução do campo visual.
Aplicativo de escrita com previsão
de texto baseado em árvore
• Denominado Aplicativo Facilitador de Escrita
- AFE.
• Utiliza teoria da informação para diminuir o
tempo de escrita
• Letras são sugeridas apenas no local central
da tela
• Usuários apenas capazes de emitir um “sim”
podem utilizar o aplicativo.
• O aplicativo adapta-se ao usuário, as palavras
mais usadas passam a ser mais sugeridas.
Árvore de busca
• Árvore ->
• Adição da palavra,
“elastico” ->
• Configurações:
– Modo automático ou Assistido
– Fator de aprendizado
• Atalhos: K -> confirma, J-> desiste e L ->
próxima palavra.
Estados do aplicativo
•
•
•
•
•
A -> Digita a primeira letra
B -> Previsão com sugestão única
C -> Previsão com sugestão em grupo
D -> Busca no dicionário
E -> Modo ditar
B
A
D
C
E
Estado A – primeira letra
• A árvore seguinte é percorrida até
escolher a letra.
• Pode ter a escolha automática
Escrita de palavras utilizando o
modo Grupo-Subgrupo
• Neste teste teórico a quantidade de
passos para escrita de uma palavra é
diretamente proporcional a posição da
letra no alfabeto
Letra
Passos
Letra
Passos
Letra
Passos
Letra
Passos
B
3
C
4
Q
8
X
10
A
2
A
2
U
9
I
6
B
3
S
10
E
4
C
4
A
2
A
2
R
9
A
2
O
8
R
9
A
2
Total/Médi
a
10/2,5
18/4,5
38/7,6
33/5,5
Escrita de palavras utilizando árvore
sem previsão
• Para a escrita de uma palavra é necessária
uma quantidade média entre 4 e 5
passos.
Letra
B
A
B
A
Passo
s
5
5
5
5
Total/Média
20/5
Letra
C
A
S
A
Passo
s
4
5
4
5
19/4,5
Letra
Q
U
E
R
O
Passo
s
5
5
5
5
5
25/5
Letra
X
I
C
A
R
A
Passo
s
5
4
4
5
5
5
28/4,6
Escrita de palavras utilizando
árvore com previsão e sugestão
de uma letra
• As palavras “CASA” e “QUERO”, por
estarem na árvore de previsão necessitam
de poucos passos para a escrita
Letra
B
A
B
A
Passos
5
1
12
5
Total/Média
23/5,7
Letra
C
A
S
A
Passos
4
2
2
1
9/2,2
Letra
Q
U
E
R
O
Passos
5
1
1
2
3
11/2,2
Letra
X
I
C
A
R
A
Passos
5
2
9
5
5
5
31/5,2
Escrita de palavras utilizando
árvore com previsão e sugestão em
grupo
• Comparado com o método anterior, fica
claro que, caso não seja possível a
previsão, não ocorre perda de tempo com
a sugestão de 5 letras (passos)
Letra
Passos
Letra
Passos
Letra
Passos
Letra
Passos
B
5
C
4
Q
5
X
5
A
4
A
2
U
1
I
3
B
6
S
3
E
1
C
6
A
3
A
2
R
4
A
5
O
2
R
5
A
5
Total/Média
18/4,5
11/2,7
14/2,8
29/4,8
Previsão com aprendizado e
sugestão de palavra
• Na primeira vez que apalavra foi digitada,
pelo fato de não estar presente na árvore,
sua digitação foi bastante custosa.
• Porém pelo aplicativo ir aprendendo, na 6º
vez só é necessário 6 passos.
Letra
Passos
Letra
1º Vez
Passos
Letra
2º Vez
Passos
Letra
5º Vez
Passos
6º Vez
X
5
X
5
X
5
X
5
I
3
I
2
I
1
I
1
C
6
C
3
C
3
C
0
A
5
A
1
A
1
A
0
R
5
R
0
R
0
R
0
A
5
A
0
A
0
A
0
Total/Média
29/4,8
11/1,8
10/1,6
6/1
Aplicativo