Algoritmos e Estruturas de Dados Tópicos diversos

Algoritmos e Estruturas de Algoritmos e Estruturas de DadosDados

Tópicos diversos

Classes P, NP e NP-CompletoClasses P, NP e NP-Completo

• Classe P– Problemas que podem ser resolvidos em tempo

polinomial, isto é, O (nk) onde n é o tamanho da entrada e k é alguma constante

• Classe NP– NP significa “não deterministicamente polinomial”

• Assume a existência de um computador hipotético “não determinístico”: toma sempre a decisão certa

– Problemas que são verificáveis em tempo polinomial

– Dada uma entrada E para um problema e uma saída S, verificação significa determinar se S é solução do problema

• S é chamada de certificado

Classes P, NP e NP-CompletoClasses P, NP e NP-Completo

• Classe NP (cont.)– Exemplo: ciclo hamiltoniano de um grafo <V, E>

• Certificado é uma seqüência < v1, v2, ... v|V|> • Claramente, determinar a correção do certificado pode

ser feito em tempo polinomial

– P NP• Todo problema solúvel em tempo polinomial é

verificável em tempo polinomial

– P NP ?• Seria de se esperar que existem problemas que são NP

mas cuja solução requer tempo não polinomial• Neste caso o “computador não determinístico” seria

um grande avanço da tecnologia• Até agora, não foram encontradas provas desta

afirmativa

NP-CompletudeNP-Completude

• Um problema é NP-completo se ele é NP e pode ser reduzido a um outro problema NP-completo– Definição recursiva?

• Problema original é o de satisfatibilidade (Cook)– Dada uma expressão booleana com n termos variáveis,

dar um valor a cada variável de tal forma que o resultado seja True

– Cook provou que o problema pode ser resolvido por computador não determinístico

– Redução• Mapeamento entre um problema e outro• Exemplo: O problema do caixeiro viajante pode ser

reduzido ao problema do ciclo hamiltoniano


• Problema do caixeiro viajante– Num grafo valorado totalmente conexo existe algum ciclo

com peso total <= K ?– Problema do ciclo hamiltoniano em um grafo G pode ser

reduzido a este bastando criar um grafo valorado G’ onde a aresta E tem peso 1 se pertence a G ou 2 caso contrário


• Problemas NP-Completos são intratáveis e existem muitos deles

• Quando um problema se mostra difícil de resolver, provar que ele é NP-completo pode ser de grande valia– Prova-se que ele é NP (certificado pode ser

testado em tempo polinomial)– Prova-se que ele é redutível a outro problema

NP-completo

• Na prática, costuma-se fazer a “segunda melhor coisa”– Resolver um subcaso importante – Achar soluções aproximadas

Heaps BinomiaisHeaps Binomiais

• Heap que suporta união em tempo O (log n+m) ao invés de O (n+m) como a heap comum

• Em compensação o tempo de consultar o menor elemento é O(log n) ao invés de O (1)

• Existe ainda um tipo de heap chamada de heap de Fibonacci que tem tempos ótimos amortizados (não pior caso):– Inserção, remoção e mínimo em tempo

amortizado O(1)

• Uma heap binomial é uma floresta de árvores binomiais

Árvores BinomiaisÁrvores Binomiais

• Uma árvore binomial Bk é uma árvore ordenada– Se k = 0 então

consiste de um único nó

– Senão, consiste de duas árvores binomiais Bk-1

ligadas de tal forma que o filho mais à esquerda de uma é a raiz da outra

Árvores BinomiaisÁrvores Binomiais

• Propriedades de Bk:– Tem 2k nós, – Tem altura k– Tem nós de altura i– A raiz tem grau k, que é maior que o de qualquer

outro nó– Corolário: Se uma árvore binomial tem n nós, então

sua altura máxima e o grau máximo de qualquer nó é lg n

i

k

Heaps BinomiaisHeaps Binomiais

• Uma heap binomial H é uma floresta de árvores binomiais onde– Cada árvore é ordenada como uma heap

mínima, isto é, todos os nós internos são menores que seus filhos

• A raiz de cada árvore contém o mínimo elemento

– Todas as raízes de todas as árvores têm graus distintos

• Se H tem n nós, então ela contém no máximo lg n + 1 árvores binomiais

• Observe que, em binário, n tem lg n + 1 bits. Como cada árvore binomial de ordem k tem 2k nós, teríamos uma árvore para cada bit de n que fosse igual a 1

Heaps BinomiaisHeaps Binomiais• Heaps são representadas

como listas ordenadas (por grau/altura) de árvores binomiais

• Exemplo: Uma heap binomial com 13 (=1011B) nós

União de Heaps BinomiaisUnião de Heaps Binomiais

• Faz-se o merge por grau das duas heaps numa única lista ordenada– O resultado pode ter apenas 2 árvores de cada grau

• Para cada par de árvores A e B de mesmo grau, gera-se uma árvore C que é resultante de inserir A como filho mais à esquerda de B ou vice-versa– Depende de quem é a menor das duas raízes

• O resultado da fusão de duas árvores de grau k é uma árvore de grau k+1– Podemos então ter três árvores de mesmo grau na

lista– Se isso acontecer, fundimos apenas as duas últimas

Exemplo de União de Heaps Exemplo de União de Heaps BinomiaisBinomiais

Exemplo de União de Heaps Exemplo de União de Heaps BinomiaisBinomiais

Consulta e Inclusão em Heaps Consulta e Inclusão em Heaps BinomiaisBinomiais

• A consulta do valor mínimo se faz com uma procura seqüencial das raízes das árvores em tempo O (lg n)

• A inclusão de um valor v numa heap binomial H é feita criando-se uma heap binomial unitária H’ contendo apenas v e computando-se sua união com H

Remoção do Mínimo em Heaps Remoção do Mínimo em Heaps BinomiaisBinomiais

• A árvore A contendo a menor raiz é removida da lista de H

• A raiz x de A é removida, gerando assim uma lista das sub-árvores filhas: A’, A’’, A’’’ etc

• Uma nova heap H’ é construída com a lista de filhas de A em ordem inversa

• É computada a união entre H e H’• A operação total é feita em tempo O (lg n)

Exemplo de Remoção em Heaps Exemplo de Remoção em Heaps BinomiaisBinomiais

TriesTries

• Ao contrário de árvores de busca, que podem ser consideradas estruturas que organizam dados entre si, as tries organizam o espaço em que os dados estão imersos

• Bastante usadas em estruturas de dados espaciais– As quadtrees, por exemplo, seriam mais bem

denominadas quadtries

• Em uma dimensão, são mais usadas para organizar cadeias de texto– O espaço é unidimensional porque podemos pensar

numa ordem total entre todas as cadeias (ordem alfabética)

Exemplo de TrieExemplo de Trie

Compressão de DadosCompressão de Dados

• Objetivos– Reduzir espaço de armazenagem– Reduzir tempo de transmissão

• Muito importante– Informação (e dados) tende a crescer de forma

exponencial• Exemplos:

– Compressão de arquivos em geral• ZIP, GZIP, BZIP, BOA.

– Sistemas de arquivos: NTFS.– Multimedia.

• Imagens: GIF, JPEG• Som: MP3.• Vídeo: MPEG, DivX™, HDTV.

– Comunicação• Modems• Faxes

Codificação e DecodificaçãoCodificação e Decodificação

• Seja M a mensagem que desejamos armazenar/transmitir– Codificação: Gerar uma representação “comprimida”

C(M) que, espera-se, utilize menos bits– Decodificação: Reconstrução da mensagem original ou

alguma aproximação M’

• Razão de Compressão: bits de C(M) / bits de M• Compressão sem perda: M = M’

– Texto, programas fonte, executáveis etc– RC: 50-75% ou menos

• Compressão com perda: M ~ M’– Imagens, som, vídeo– Idéia é descartar informação não perceptível pelos

sentidos– RC: 10% ou mais, dependendo do fator de qualidade

Codificação por Seqüências Codificação por Seqüências RepetidasRepetidas

• Conhecida como Run-length encoding (RLE).• Idéia é explorar longas seqüências da caracteres repetidos

– Substituir seqüência pelo número de repetições seguido do caractere repetido

– Se seqüência é tem menos de 3 caracteres, ignorar regra• Exemplo:

– AAAABBBAABBBBBCCCCCCCCDABCBAAABBBBCCCD 4A3BAA5B8CDABCB3A4B3CD

• Como representar o número de repetições?– Alguns esquemas + ou – complicados– Pode levar à inflação de um arquivo se as seqüências são curtas

• Se o arquivo é binário, saída consiste apenas de contagens de repetições

• Aplicações– Imagens preto e branco

• Compressão aumenta com a resolução

Codificação de HuffmanCodificação de Huffman

• Idéia é usar caracteres (símbolos) com número variável de bits– Caracteres mais comuns na mensagem são codificados

com menos bits e caracteres menos comuns com mais

• Árvore de Prefixos de Huffman– Dada uma mensagem, encontra a melhor (menor)

codificação para os caracteres– Algoritmo:

• Tabular freqüências dos símbolos• Montar uma floresta de tries unitários com todos os

símbolos e suas freqüências• Repetir

– Localizar os dois tries com menor freqüência Fi e Fj

– Uní-los num trie único com freqüência Fi + Fj

Exemplo de Codificação de Exemplo de Codificação de HuffmanHuffman

• Freqüências dos caracteres

125

Freq

93

80

76

72

71

61

55

41

40

E

Char

T

A

O

I

N

R

H

L

D

31

27

C

U

65S


R S N I

E

H

C U

31 27

5571 7361 65

125

40

T

D L

41

93

A O

80 76


R S N I

E

H

C U

58

D L

A O T

31 27

5571 7361 65

125

40 41

9380 76


R S N I

E

H

C U

58

D L

81

A O T

31 27

5571 7361 65

125

40 41

9380 76


R S N I

E

H

C U

58

113

D L

81

A O T

31 27

5571 7361 65

125

40 41

9380 76


R S N I

E

H

C U

58

113126

D L

81

A O T

31 27

5571 7361 65

125

40 41

9380 76


R S N I

E

H

C U

58

113144126

D L

81

A O T

31 27

5571 7361 65

125

40 41

9380 76


R S N I

E

H

C U

58

113144126

D L

81

156

A O T

31 27

5571 7361 65

125

40 41

9380 76


R S N I

E

H

C U

58

113144126

D L

81

156 174

A O T

31 27

5571 7361 65

125

40 41

9380 76


R S N I

E

H

C U

58

113144126

238

T

D L

81

156 174

A O


R S N I

E

H

C U

58

113144126

238270

T

D L

81

156 174

A O

31 27

5571 7361 65

125

40 41

9380 76


R S N I

E

H

C U

58

113144126

23827.0

330

T

D L

81

156 174

A O

31 27

5571 7361 65

125

40 41

9380 76


R S N I

E

H

C U

58

113144126

238270

330 508

T

D L

81

156 174

A O

31 27

5571 7361 65

125

40 41

9380 76


R S N I

E

H

C U

58

113144126

238270

330 508

838

T

D L

81

156 174

A O

31 27

5571 7361 65

125

40 41

9380 76


125

Freq

93

80

76

73

71

61

55

41

40

E

Char

T

A

O

I

N

R

H

L

D

31

27

C

U

65S

0000

Fixo

0001

0010

0011

0100

0101

0111

1000

1001

1010

1011

1100

0110

110

Huff

000

000

011

1011

1010

1000

1111

0101

0100

11100

11101

1001

838Total 4.00 3.62

Codificação de HuffmanCodificação de Huffman

• Implementação.– Dois passos

• Tabular freqüências e construir o trie• Codificar mensagem percorrendo o trie

– Usar uma fila de prioridades (heap)• Complexidade O(M + N log N)

– M é o comprimento da mensagem– N é o número de caracteres distintos

• Dificuldades– Transmissão do trie

• Pode ser resolvido com variante progressiva (Knuth): Trie é construído simultaneamente pelo codificador e decodificador

– Não é ótimo• Número de bits por caractere é inteiro• Codificação aritmética: permite número “fracionário”de bits

por caractere

Documents

Algoritmos e Estruturas de Dados Tópicos diversos