TEORIA DA

INFORMAÇÃO:

INTRODUÇÃO

Profª Drª Denise Fukumi Tsunoda Março/2015

Shannon e a Teoria da

Informação

Claude Elwood Shannon (1916 – 2001),

Americano, engenheiro elétrico e matemático

Conhecido como “pai da teoria da informação”

Em 1949, Claude Shannon publicou um paper entitulado

"Communication Theory of Secrecy Systems" que introduziu

diversos conceitos de criptografia.

A Teoria da Informação é uma disciplina centrada à

volta de uma abordagem matemática comum ao estudo

do armazenamento e manipulação da informação.

Shannon e a Teoria da

Informação

Teoria da Informação

Disciplina centrada na abordagem matemática comum ao estudo do armazenamento e manipulação da informação

Como tal, fornece uma base teórica para atividades como:

observação, medida, compressão e armazenamento de dados

telecomunicações

previsão

tomada de decisões

reconhecimento de padrões

Relativamente às

telecomunicações, a TI:

fornece “pistas” para melhorar a eficiência da

comunicação estudo das possibilidades e

limitações inerentes às leis físicas

A Codificação (de fonte e de canal) é uma

forma de melhorar a eficiência da

comunicação

estabelece limites para essa eficiência, em

relação aos quais poderemos comparar

diversos sistemas

Teoria da Informação

Trata de três conceitos básicos:

medida da informação

capacidade de um canal de comunicações transferir informação

codificação, como meio de utilizar os canais com toda a sua capacidade

A Teoria da Informação PROCURA

responder a perguntas do gênero:

O que é a informação? Como a medimos?

Quais são os limites fundamentais à

transmissão de informação?

Como minimizar os ruídos ambientais das

comunicações?

Como garantir a segurança de uma

informação?

Como compactar um documento digital?

Como quantificar a quantidade de informação

de uma propaganda?

TI e outras áreas

Fonte: COVER, T; THOMAS, J. Elements of information theory. 2nd ed. John Wiley & Sons. 2006.

O que é informação?

Informação é dependente do observador

Ex.: O que Alice sabe é diferente do que Bob

sabe

Uma informação pode ser localizada no

tempo-espaço, logo:

Informação pode ser enviada de um lugar a outro

Informação pode ser armazenada e

posteriormente recuperada

Perspectiva histórica

Código Morse (Samuel Morse, 1832)

S O S ···---···

Medida da informação: estudada por Nyquist

(1924), Hartley (1928) e Fisher (1925)

Fundamentos Shannon (1948)

(criptografia), Wiener (1948) e Kotelnikov

(1947) (sinais de radar para localização de

aviões inimigos)

Esquema de um sistema de

comunicação

Fonte de

Informaçã

o

Emissor Receptor Destinatári

o

Modelo esquemático

Início Fim

Codificação – sistemas de

numeração

Os computadores armazenam e processam

dados digitais

Todos os dados são divididos em partes e

representados por números binários (0 e 1)

Internamente, TODO O PROCESSO utiliza a

base 2

Mas podem ser utilizadas ainda as

representações

Hexadecimal (16)

Octal (8)

Memória principal

A memória é dividida em células

Cada célula tem um endereço único

Cada dado é armazenado em uma ou mais

células consecutivas

Na maioria das vezes, cada célula tem

capacidade para armazenar 8bits

Um byte armazena o código ASCII de uma

letra

Código ASCII (American Standard Code for Information Interchange)

Capacidade de memória

Cada memória tem uma capacidade que expressa

o número de bytes que consegue armazenar

Peta, Exa, Zetta, Yotta, Novetta, Decetta, Vendeka,

Udekta

Assim, um computador com 128MB de RAM tem

128x220 células para armazenar dados

Unidade Símbolo Número de bytes

Quilobyte KB 210 = 1024

Megabyte MB 220 (> 1 milhão)

Gigabyte GB 230 (> 1 bilhão)

Terabyte TB 240 (> 1trilhão)

Representação binária

Cada bit que se adiciona, duplica o número de

combinações possíveis

N bits podem representar 2N itens distintos

Assim:

BITS ITENS

1 21 = 2

2 22 = 4

3 23 = 8

4 24 = 16

5 25 = 32

6 26 = 64

7 27 = 128

8 28 = 256

Aritmética binária

O sistema de numeração convencional vale-

se de um código de posições

Exemplos:

4737

XI e IX

Sistemas de numeração:

Sistema decimal 10 dígitos

Sistema binário 2 dígitos

Conversão binário decimal

Exemplo:

3282910 =

30000 + 2000 + 800 + 20 + 9 =

(3x104)+(2x103)+(8x102)+(2x101)+(9x100)

101012 =

10000 + 0000 + 100 + 00 + 1 =

(1x24) + (0x23)+(1x22)+(0x21)+(1x20) = 2110

Conversão decimal binário

Demonstrar a conversão:

65410 10100011102

100111012 15710

Vantagens do sistema binário

Pode-se representar grandes números com menor quantidade de elementos

Facilidade de adição e multiplicação

Exemplos:

Calcular: a) 101102+110112 e 2210+1710

b) 11012x1012 e 1310x510

+ 0 1

0 0 1

1 1 10

x 0 1

0 0 0

1 0 1

Conversões – Calcular para

decimal

11010102 = ? 10

C1B316 = ? 10

368 = ? 10

Para base binária

10610 = ? 2

C1B316 = ? 2

368 = ? 2

Para base octal

10610 = ? 8

C1B316 = ? 8

111102 = ? 8

Para hexadecimal

10610 = ? 16

11000001101100112 = ? 16

368 = ? 16

Perguntas

Quantos bits são necessários para representar

N números?

Exemplo: quantos bits preciso para

representar 100 objetos diferentes?

Com K bits, tenho 2K números diferentes

Para representar N elementos diferentes, são

necessários log2(N) bits

ASSIM, para 100 elementos diferentes,

preciso de quantos bits??

Medidas da informação

Incerteza

Entropia

Informação mútua média

Capacidade de canal

Incerteza

Se não houver nenhuma possibilidade de escolha ( só uma mensagem possível)

não há incerteza

não há informação

29

Incerteza

Uma situação de incerteza pode ser descrita

como sendo aquela com muitas possibilidades

e com o resultado mais adequado indefinido

Ex. “qual será a próxima tecla a ser digitada

por um programador?”

Como pode ser medida a incerteza de um

esquema S?

30

Medida da Incerteza

Intuitivamente, quanto maior a cardinalidade de número de elementos de S |S|, maior a incerteza.

Quanto mais incerto for alguma coisa, mais entropia há nela.

Ex.: se uma pessoa qualquer de uma população geral é

masculina ou feminina, a variável "gênero" possui um bit de entropia

se uma pessoa qualquer prefere um dos quatro Beatles, e cada um deles é igualmente provável, isso corresponde a dois bits de entropia

Incerteza

O sexo de alguém em uma prova olímpica

para mulheres não possui entropia todas

são do sexo feminino

A entropia da preferência dos Beatles em uma

reunião de fãs de John Lennon possui muito

menos de dois bits é muito mais provável

que qualquer pessoa prefira John

Resumindo quanto mais certeza na

variável, menos entropia haverá

Conteúdo da Informação -

Shannon

SIC – Shannon Information Content

O cálculo de conteúdo de uma informação com probabilidade p é –log2p.

Exemplo1:

Jogada de uma moeda

x=[cara;coroa] p = [1/2;1/2] SIC=[1;1]bits

Exemplo2:

Hoje é meu aniversário?

x=[sim;não] p=[364/365;1/365] SIC=[0,004;8,512]bits

Entropia – conceituação básica

A teoria da informação afirma que quanto

menos informações sobre um sistema, maior

será sua entropia

A entropia de uma mensagem é entendida na

teoria da informação como sendo o menor

número de bits, unidade de informação,

necessários para conter todos os valores ou

significados desta mensagem

Entropia - unidade

O log utilizado é o de base 2, uma vez que a

entropia é medida em bits

Se fosse utilizado o log na base e

(2,718281828459045...) número de Euler

a unidade de medida seria nat

1 nat = log2(e) bits = 1,44 bits

O logaritmo neperiano (John Napier) ou

natural

)2ln(

)ln()(log2

xx

Entropia - Cálculo

A fórmula da entropia é:

M = número de diferentes símbolos;

Pj = probabilidade de ocorrência do símbolo j

Unidade: bits/caracter

No caso de uma fonte binária, com probabilidades

p e 1-p, a entropia é designada por (p) e vale:

j

M

j

jM PPPPPPH 2

1

321 log.)...,,(

)1(log).1(log.)1,()( 22 ppppppHp

Análise de intervalos

37

Exemplos de entropia

no log leia-se log2

Entropia máxima (Hmax)

A entropia atinge seu valor máximo quando

todas as saídas da fonte são equiprováveis

Exemplo:

Calcular a entropia do conjunto!

Entropia

Dia da semana Chuva Temperatura Trabalho

Segunda Não Quente Pouco

Terça Sim Frio Pouco

Terça Sim Quente Pouco

Segunda Sim Frio Pouco

Segunda Não Quente Muito

Terça Não Frio Muito

Segunda Não Quente Pouco

Segunda Sim Quente Muito

Segunda Sim Frio Pouco

Calcular a entropia do conjunto!

Calcular as entropias individuais dos atributos!

Árvore de Decisão

Construir a árvore!