Algoritmos e Estruturas de Dados
Tópicos diversos
Classes 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-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-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
NP-Completude
• 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
NP-Completude
• 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 NPcompleto
• Na prática, costuma-se fazer a “segunda melhor
coisa”
– Resolver um subcaso importante
– Achar soluções aproximadas
Heaps 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
• 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
• Propriedades de Bk:
–
–
–
–
–
Tem 2k nós,
Tem altura k
k 
Tem   nós de altura i
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
Heaps 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 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 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 Binomiais
Exemplo de União de Heaps Binomiais
Consulta e Inclusão em Heaps Binomiais
• 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 Binomiais
• 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 Binomiais
Tries
• 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 Trie
Compressã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çã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 Repetidas
• 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 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 Huffman
• Freqüências dos
caracteres
Char
Freq
E
125
T
93
A
80
O
76
I
72
N
71
S
65
R
61
H
55
L
41
D
40
C
31
U
27
Exemplo de Codificação de Huffman
A
O
T
E
80
76
93
125
D
L
R
S
N
I
H
40
41
61
65
71
73
55
C
U
31
27
Exemplo de Codificação de Huffman
A
O
T
E
80
76
93
125
D
L
R
S
N
I
40
41
61
65
71
73
H
58
55
C
U
31
27
Exemplo de Codificação de Huffman
A
O
80
76
81
T
E
93
125
D
L
R
S
N
I
40
41
61
65
71
73
H
58
55
C
U
31
27
Exemplo de Codificação de Huffman
A
O
80
76
81
T
E
93
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de Huffman
A
O
80
76
T
E
93
81
126
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de Huffman
A
O
80
76
T
E
93
81
126
144
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de Huffman
156
A
O
80
76
T
E
93
81
126
144
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de Huffman
156
174
A
O
80
76
T
E
93
81
126
144
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de Huffman
156
A
174
O
238
T
E
126
81
D
L
R
144
S
N
113
I
H
58
C
U
Exemplo de Codificação de Huffman
156
270
174
A
O
80
76
238
T
E
93
81
126
144
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de Huffman
330
156
27.0
174
A
O
80
76
238
T
E
93
81
126
144
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de Huffman
330
508
156
270
174
A
O
80
76
238
T
E
93
81
126
144
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de Huffman
838
330
508
156
270
174
A
O
80
76
238
T
E
93
81
126
144
125
D
L
R
S
N
I
40
41
61
65
71
73
113
H
58
55
C
U
31
27
Exemplo de Codificação de Huffman
Char
Freq
Fixo
Huff
E
125
0000
110
T
93
0001
000
A
80
0010
000
O
76
0011
011
I
73
0100
1011
N
71
0101
1010
S
65
0110
1001
R
61
0111
1000
H
55
1000
1111
L
41
1001
0101
D
40
1010
0100
C
31
1011
11100
U
27
1100
11101
Total
838
4.00
3.62
Codificaçã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