Projeto de Algoritmos em C Nivio Ziviani
Projeto de Algoritmos em C Nivio Ziviani
Projeto de Algoritmos em C Nivio Ziviani
Introdução
∗ Transparências elaboradas por Charles Ornelas Almeida, Israel Guerra e Nivio Ziviani
Projeto de Algoritmos – Cap.1 Introdução 1
Conteúdo do Capítulo
1.5 Pascal
Projeto de Algoritmos – Cap.1 Introdução – Seção 1.1 2
Estruturas de dados
Programas
• Programar é basicamente estruturar dados e construir algoritmos.
• Programas são formulações concretas de algoritmos abstratos,
baseados em representações e estruturas específicas de dados.
• Programas representam uma classe especial de algoritmos capazes
de serem seguidos por computadores.
• Um computador só é capaz de seguir programas em linguagem de
máquina (sequência de instruções obscuras e desconfortáveis).
• É necessário construir linguagens mais adequadas, que facilitem a
tarefa de programar um computador.
• Uma linguagem de programação é uma técnica de notação para
programar, com a intenção de servir de veículo tanto para a expressão
do raciocínio algorítmico quanto para a execução automática de um
algoritmo por um computador.
Projeto de Algoritmos – Cap.1 Introdução – Seção 1.2 6
Tipos de Dados
Custo de um Algoritmo
Função de Complexidade
• Para medir o custo de execução de um algoritmo é comum definir uma
função de custo ou função de complexidade f .
• f (n) é a medida do tempo necessário para executar um algoritmo para
um problema de tamanho n.
• Função de complexidade de tempo: f (n) mede o tempo necessário
para executar um algoritmo em um problema de tamanho n.
• Função de complexidade de espaço: f (n) mede a memória
necessária para executar algoritmo em um problema de tamanho n.
• Utilizaremos f para denotar uma função de complexidade de tempo
daqui para a frente.
• A complexidade de tempo na realidade não representa tempo
diretamente, mas o número de vezes que determinada operação
considerada relevante é executada.
Projeto de Algoritmos – Cap.1 Introdução – Seção 1.3 16
int Max(TipoVetor A)
{ int i , Temp;
Temp = A[ 0 ] ;
for ( i = 1; i < N; i ++) i f (Temp < A[ i ] ) Temp = A[ i ] ;
return Temp;
}
• f (n) = 2(n − 1), para n > 0, no melhor caso, pior caso e caso médio.
Projeto de Algoritmos – Cap.1 Introdução – Seção 1.3 24
d d d ··· d
Contém o máximo
d d d ··· d
Contém o mínimo
Projeto de Algoritmos – Cap.1 Introdução – Seção 1.3 26
Os três f (n)
algoritmos Melhor caso Pior caso Caso médio
• Para derivar o limite inferior, o oráculo procura sempre fazer com que o
algoritmo trabalhe o máximo, escolhendo como resultado da próxima
comparação aquele que cause o maior trabalho possível necessário
para determinar a resposta final.
Projeto de Algoritmos – Cap.1 Introdução – Seção 1.3 30
comparações. 2
Dominação assintótica
Notação O
• Escrevemos g(n) = O(f (n)) para expressar que f (n) domina
assintoticamente g(n). Lê-se g(n) é da ordem no máximo f (n).
• Exemplo: quando dizemos que o tempo de execução T (n) de um
programa é O(n2 ), significa que existem constantes c e m tais que,
para valores de n ≥ m, T (n) ≤ cn2 .
• Exemplo gráfico de dominação assintótica que ilustra a notação O.
f,g
c f (n)
g(n) O valor da constante m é o menor
possível, mas qualquer valor maior é
válido.
n
m
Exemplos de Notação O
Exemplos de Notação O
Notação Ω
• Exemplo: Para mostrar que g(n) = 3n3 + 2n2 é Ω(n3 ) basta fazer c = 1,
e então 3n3 + 2n2 ≥ n3 para n ≥ 0.
f,g
g(n)
Notação Θ
• Definição: Uma função g(n) é Θ(f (n)) se existirem constantes c1 , c2 e
m tais que 0 ≤ c1 f (n) ≤ g(n) ≤ c2 f (n), para todo n ≥ m.
• Exemplo gráfico para a notação Θ
f,g
c2 f ( n )
g(n)
c1 f ( n )
n
m
Exemplo de Notação Θ
• Seja g(n) = n2 /3 − 2n.
Notação o
• Definição: Uma função g(n) é o(f (n)) se, para qualquer constante
c > 0, então 0 ≤ g(n) < cf (n) para todo n ≥ m.
Notação ω
• Definição: Uma função g(n) é ω(f (n)) se, para qualquer constante
c > 0, então 0 ≤ cf (n) < g(n) para todo n ≥ m.
n2 n2
• Exemplo: 2
= ω(n), mas 2
6= ω(n2 ).
g(n)
• A relação g(n) = ω(f (n)) implica limn→∞ f (n)
= ∞, se o limite existir.
Projeto de Algoritmos – Cap.1 Introdução – Seção 1.3.2 44
Comparação de Programas
• Um programa com tempo O(n) é melhor que outro com tempo O(n2 ).
• f (n) = O(n3 ).
– Um algoritmo de complexidade O(n3 ) é dito ter complexidade cúbica.
– Úteis apenas para resolver pequenos problemas.
– Quando n é 100, o número de operações é da ordem de 1 milhão.
– Sempre que n dobra, o tempo de execução fica multiplicado por 8.
Projeto de Algoritmos – Cap.1 Introdução – Seção 1.3.2 49
Função Tamanho n
de custo 10 20 30 40 50 60
9 4 8
5 c3 3
c2 c4
8
Anel Interno
Anel Externo
Procedimento Recursivo
Pesquisa(n) ;
(1) i f (n ≤ 1)
(2) ‘inspecione elemento’ e termine
else{
(3) para cada um dos n elementos ‘ inspecione elemento ’ ;
(4) Pesquisa(n/ 3 ) ;
}
• Sustitui-se os termos T (k), k < n, até que todos os termos T (k), k > 1,
tenham sido substituídos por fórmulas contendo apenas T (1).
T (n) = n + T (n/3)
T (n/3) = n/3 + T (n/3/3)
T (n/3/3) = n/3/3 + T (n/3/3/3)
.. ..
. .
T (n/3/3 · · · /3) = n/3/3 · · · /3 + T (n/3 · · · /3)
end
Projeto de Algoritmos – Cap.1 Introdução – Seção 1.5 67
Tipos em Pascal
Tipos Estruturados
• Definem uma coleção de valores simples, ou um agregado de valores
de tipos diferentes.
• Existem quatro tipos estruturados primitivos:
– Arranjos: tabela n-dimensional de valores homogêneos de
qualquer tipo. Indexada por um ou mais tipos simples, exceto o tipo
real.
– Registros: união de valores de tipos quaisquer, cujos campos
podem ser acessados pelos seus nomes.
– Conjuntos: coleção de todos os subconjuntos de algum tipo
simples, com operadores especiais ∗ (interseção), + (união), −
(diferença) e in (pertence a) definidos para todos os tipos
conjuntos.
– Arquivos: sequência de valores homogêneos de qualquer tipo.
Geralmente é associado com alguma unidade externa.
Projeto de Algoritmos – Cap.1 Introdução – Seção 1.5 71
const n = 20;
Dada a variável
var x: coluna;
var p: pessoa;
p.sobrenome := ’Ziviani’;
p.primeironome := ’Patricia’;
p.aniversário.dia := 21;
p.aniversário.mês := 10;
p.sexo := f;
Projeto de Algoritmos – Cap.1 Introdução – Seção 1.5 74
Declaradas as variáveis
var ci : conjint;
var cc : array [1..5] of conjcor;
var ch: conjchar;
Projeto de Algoritmos – Cap.1 Introdução – Seção 1.5 75
ci := [1,4,9];
cc[2] := [vermelho..rosa];
cc[4] := [ ];
cc[5] := [azul, rosa];
• São úteis para criar estruturas de dados encadeadas, do tipo listas, árvores
e grafos.
Exemplo:
Separador de Comandos
• Quando mal colocado, pode causar erros que não são detectados em
tempo de compilação.
if a = 0 then;
a := a + 1;
Projeto de Algoritmos – Cap.1 Introdução – Seção 1.5 80
Resultado da execução:
Procedimento SomaUm : 1 1
Programa principal :0 1
Paradigmas de Projeto de
Algoritmos ∗
∗ Transparências elaboradas por Charles Ornelas Almeida, Israel Guerra e Nivio Ziviani
Projeto de Algoritmos – Cap.2 Paradigmas de Projeto de Algoritmos 1
Conteúdo do Capítulo
2.1 Indução
2.2 Recursividade
2.2.1 Como Implementar Recursividade
2.2.2 Quando Não Usar Recursividade
2.5 Balanceamento
Indução Matemática
• É útil para provar asserções sobre a correção e a eficiência de
algoritmos.
• Consiste em inferir uma lei geral a partir de instâncias particulares.
• Seja T um teorema que tenha como parâmetro um número natural n
Provando que T é válido para todos os valores de n, provamos que:
1. T é válido para n = 1;
2. Para todo n > 1, se T é válido para n − 1, então T é válido para n.
• A condição 1 é chamada de passo base.
• Provar a condição 2 é geralmente mais fácil que provar o teorema
diretamente (podemos usar a asserção de que T é válido para n − 1).
• Esta afirmativa é a hipótese de indução ou passo indutivo.
• As condições 1 e 2 implicam T válido para n = 2, o que junto com a
condição 2 implica T também válido para n = 3, e assim por diante.
Projeto de Algoritmos – Cap.2 Paradigmas de Projeto de Algoritmos – Seção 2.1 3
• Nestes casos, pode ser mais fácil tentar advinhar a solução ou obter
um limite superior para a ordem de complexidade.
• Mostrar que um certo limite existe é mais fácil do que obter o limite.
• cn cresce mais lentamente que T (n), pois c2n = 2cn e não existe
espaço para o valor 2n − 1.
Recursividade
• Um procedimento que chama a si mesmo é dito ser recursivo.
• Recursividade permite descrever algoritmos de forma mais clara e
concisa, especialmente problemas recursivos ou que utilizam
estruturas recursivas.
• Ex.: árvore binária de pesquisa:
– Registros com chaves menores estão na subárvore esquerda;
– Registros com chaves maiores estão na subárvore direita.
Recursividade
• Algoritmo para percorrer todos os registros em ordem de
caminhamento central:
1. caminha na subárvore esquerda na ordem central;
2. visita a raiz;
3. caminha na subárvore direita na ordem central.
• Os nós são visitados em ordem lexicográfica das chaves.
Implementação de Recursividade
n 20 30 50 100
Recursiva 1 seg 2 min 21 dias 109 anos
Iterativa 1/3 mseg 1/2 mseg 3/4 mseg 1,5 mseg
Projeto de Algoritmos – Cap.2 Paradigmas de Projeto de Algoritmos – Seção 2.3 17
void Tenta( )
{ i n i c i a l i z a selecao de movimentos;
• Tabuleiro com n × n posi-
do ções: cavalo se movimenta
{ seleciona proximo candidato ao movimento; segundo regras do xadrez.
i f ( aceitavel ) • Problema: a partir de
{ registra movimento;
(x0 , y0 ), encontrar, se exis-
i f ( tabuleiro nao esta cheio)
tir, um passeio do cavalo
{ tenta novo movimento;
que visita todos os pontos
i f (nao sucedido)
do tabuleiro uma única vez.
apaga registro anterior ;
}
}
} while ( ! ( ( movimento bem sucedido)
ou (acabaram-
se os candidatos a movimento) ) ) ;
}
Projeto de Algoritmos – Cap.2 Paradigmas de Projeto de Algoritmos – Seção 2.3 20
3 2
4 1
5 8
6 7
Projeto de Algoritmos – Cap.2 Paradigmas de Projeto de Algoritmos – Seção 2.3 21
void MaxMin4( int Linf , int Lsup, int ∗Max, int ∗Min)
{ int Max1, Max2, Min1, Min2, Meio;
i f (Lsup − Linf <= 1)
{ i f (A[ Linf − 1] < A[Lsup − 1])
{ ∗Max = A[Lsup − 1]; ∗Min = A[ Linf − 1]; }
else { ∗Max = A[ Linf − 1]; ∗Min = A[Lsup − 1]; }
return ;
}
Meio = ( Linf + Lsup) / 2 ;
MaxMin4( Linf , Meio, &Max1, &Min1) ;
MaxMin4(Meio + 1 , Lsup, &Max2, &Min2) ;
i f (Max1 > Max2) ∗Max = Max1; else ∗Max = Max2;
i f (Min1 < Min2) ∗Min = Min1; else ∗Min = Min2;
}
Projeto de Algoritmos – Cap.2 Paradigmas de Projeto de Algoritmos – Seção 2.4 25
= 2i−1 f (2) + 2i − 2
= 2i−1 + 2i − 2
3n
= 2 − 2.
• Logo, f (n) = 3n/2 − 2 para o melhor caso, pior caso e caso médio.
Projeto de Algoritmos – Cap.2 Paradigmas de Projeto de Algoritmos – Seção 2.4 26
• n + 1 deve ser menor do que a metade do maior inteiro que pode ser
representado pelo compilador, para não provocar overflow na
operação Linf + Lsup.
Projeto de Algoritmos – Cap.2 Paradigmas de Projeto de Algoritmos – Seção 2.4 27
• Logo, os três casos não cobrem todas as funções f (n) que poderemos
encontrar. Existem algumas poucas aplicações práticas que ficam
entre os casos 1 e 2 (quando f (n) é menor do que nlogb a , mas não
polinomialmente menor) e entre os casos 2 e 3 (quando f (n) é maior
do que nlogb a , mas não polinomialmente maior). Assim, se a função
f (n) cai em um desses intervalos ou se a condição af (n/b) ≤ cf (n)
não é satisfeita, então o Teorema Mestre não pode ser aplicado.
Projeto de Algoritmos – Cap.2 Paradigmas de Projeto de Algoritmos – Seção 2.4 30
Teorema Mestre
• A prova para o caso em que f (n) = cnk , onde c > 0 e k ≥ 0 são duas
constantes inteiras, é tratada no Exercício 2.13.
• A prova desse teorema não precisa ser entendida para ser aplicado,
conforme veremos em exemptrados a seguir.
Projeto de Algoritmos – Cap.2 Paradigmas de Projeto de Algoritmos – Seção 2.4 31
Balanceamento
Análise do Mergesort
• Na contagem de comparações, o comportamento do Mergesort pode
ser representado por: T (n) = 2T (n/2) + n − 1, T (1) = 0
• No caso da equação acima temos:
T (n) = 2T (n/2) + n − 1
n
2T (n/2) = 22 T (n/22 ) + 2 − 2 × 1
2
.. ..
. .
n
2i−1 T (n/2i−1 ) = 2i T (n/2i ) + 2i−1 i−1 − 2i−1
2
• Adicionando lado a lado:
i−1 i−1
i i
X 2i−1+1 − 1
X
k
T (n) = 2 T (n/2 ) + n− 2 = in − = n log n − n + 1.
k=0 k=0 2−1
Programação Dinâmica
• O calculo inicia com mii para todo i, depois mi,i+1 para todo i, depois
mi,i+2 , e assim sucessivamente.
Algoritmos Gulosos
Algoritmos Aproximados
∗ Slides elaborados por Charles Ornelas Almeida, Israel Guerra e Nivio Ziviani
Projeto de Algoritmos – Cap.3 Estruturas de Dados Básicas 1
Conteúdo do Capítulo
3.2 Pilhas
3.2.1 Implementação de Pilhas por meio de Arranjos
3.2.2 Implementação de Pilhas por meio de Apontadores
3.3 Filas
3.3.1 Implementação de Filas por meio de Arranjos
3.3.2 Implementação de Filas por meio de Apontadores
Projeto de Algoritmos – Cap.3 Estruturas de Dados Básicas – Seção 3.1 2
Listas Lineares
• Uma das formas mais simples de interligar os elementos de um
conjunto.
• Estrutura em que as operações inserir, retirar e localizar são definidas.
• Podem crescer ou diminuir de tamanho durante a execução de um
programa, de acordo com a demanda.
• Itens podem ser acessados, inseridos ou retirados de uma lista.
• Duas listas podem ser concatenadas para formar uma lista única, ou
uma pode ser partida em duas ou mais listas.
• Adequadas quando não é possível prever a demanda por memória,
permitindo a manipulação de quantidades imprevisíveis de dados, de
formato também imprevisível.
• São úteis em aplicações tais como manipulação simbólica, gerência
de memória, simulação e compiladores.
Projeto de Algoritmos – Cap.3 Estruturas de Dados Básicas – Seção 3.1 3
• Desvantagens:
– custo para inserir ou retirar itens da lista, que pode causar um
deslocamento de todos os itens, no pior caso;
– em aplicações em que não existe previsão sobre o crescimento da
lista, a utilização de arranjos em linguagens como o Pascal pode
ser problemática porque nesse caso o tamanho máximo da lista
tem de ser definido em tempo de compilação.
Projeto de Algoritmos – Cap.3 Estruturas de Dados Básicas – Seção 3.1.2 11
typedef struct {
TipoApontador Primeiro , Ultimo ;
} TipoLista ;
Projeto de Algoritmos – Cap.3 Estruturas de Dados Básicas – Seção 3.1.2 13
• Vantagens:
– Permite inserir ou retirar itens do meio da lista a um custo constante
(importante quando a lista tem de ser mantida em ordem).
– Bom para aplicações em que não existe previsão sobre o
crescimento da lista (o tamanho máximo da lista não precisa ser
definido a priori).
Chave : 1..999;
NotaFinal : 0..10;
Opcao : array [ 1 . . 3 ] of 1 . . 7 ;
Pilha
TAD Pilhas
• Conjunto de operações:
1. FPVazia(Pilha). Faz a pilha ficar vazia.
2. Vazia(Pilha). Retorna true se a pilha está vazia; caso contrário,
retorna false.
3. Empilha(x, Pilha). Insere o item x no topo da pilha.
4. Desempilha(Pilha, x). Retorna o item x no topo da pilha, retirando-o
da pilha.
5. Tamanho(Pilha). Esta função retorna o número de itens da pilha.
Itens
Primeiro = 1 x1
2 x2
..
.
Topo xn
..
.
MaxTam
Projeto de Algoritmos – Cap.3 Estruturas de Dados Básicas – Seção 3.2.1 30
ET - Implementação
• Este programa utiliza um tipo abstrato de dados sem conhecer
detalhes de sua implementação.
• A implementação do TAD Pilha que utiliza arranjo pode ser substituída
pela que utiliza apontadores sem causar impacto no programa.
#define MAXTAM 70
#define CANCELACARATER ’# ’
#define CANCELALINHA ’ \ \ ’
#define SALTALINHA ’∗ ’
#define MARCAEOF ’~ ’
typedef char TipoChave;
/ ∗ Entram aqui os tipos da transparência 30 ∗ /
var Pilha : TipoPilha ;
x : TipoItem ;
/ ∗ Entram aqui os operadores da transparência 31 ∗ /
/ ∗ Entra aqui o procedimento Imprime ( transp . 40 ) ∗ /
Projeto de Algoritmos – Cap.3 Estruturas de Dados Básicas – Seção 3.2.2 39
ET - Implementação
int main( int argc , char ∗argv [ ] )
{ TipoPilha Pilha ; TipoItem x ;
FPVazia(&Pilha ) ; x .Chave = getchar ( ) ;
i f ( x .Chave == ’ \n ’ ) x .Chave = ’ ’ ;
while ( x .Chave ! = MARCAEOF)
{ i f ( x .Chave == CANCELACARATER)
{ i f ( ! Vazia( Pilha ) ) Desempilha(&Pilha , &x ) ; }
else i f ( x .Chave == CANCELALINHA ) FPVazia(&Pilha ) ;
else i f ( x .Chave == SALTALINHA ) Imprime(&Pilha ) ;
else { i f (Tamanho( Pilha ) == MAXTAM ) Imprime(&Pilha ) ;
Empilha(x, &Pilha ) ;
}
x .Chave = getchar ( ) ; i f ( x .Chave == ’ \n ’ ) x .Chave = ’ ’ ;
}
i f ( ! Vazia( Pilha ) ) Imprime(&Pilha ) ; return 0;
}
Projeto de Algoritmos – Cap.3 Estruturas de Dados Básicas – Seção 3.2.2 40
Fila
• É uma lista linear em que todas as inserções são realizadas em um
extremo da lista, e todas as retiradas e, geralmente, os acessos são
realizados no outro extremo da lista.
• O modelo intuitivo de uma fila é o de uma fila de espera em que as
pessoas no início da fila são servidas primeiro e as pessoas que
chegam entram no fim da fila.
• São chamadas listas fifo (“first-in”, “first-out”).
• Existe uma ordem linear para filas que é a “ordem de chegada”.
• São utilizadas quando desejamos processar itens de acordo com a
ordem “primeiro-que-chega, primeiro-atendido”.
• Sistemas operacionais utilizam filas para regular a ordem na qual
tarefas devem receber processamento e recursos devem ser alocados
a processos.
Projeto de Algoritmos – Cap.3 Estruturas de Dados Básicas – Seção 3.3 42
TAD Filas
• Conjunto de operações:
1. FFVazia(Fila). Faz a fila ficar vazia.
2. Enfileira(x, Fila). Insere o item x no final da fila.
3. Desenfileira(Fila, x). Retorna o item x no início da fila, retirando-o
da fila.
4. Vazia(Fila). Esta função retorna true se a fila está vazia; senão
retorna false.
Projeto de Algoritmos – Cap.3 Estruturas de Dados Básicas – Seção 3.3.1 43
4
Tras
´ 8 5
7 6
Projeto de Algoritmos – Cap.3 Estruturas de Dados Básicas – Seção 3.3.1 44
...
4
Tras
´ 8 5
7 6
• Nesse caso, a fila está cheia quando Trás+1 for igual a Frente.
• Para enfileirar um novo item, basta criar uma célula nova, ligá-la após
a célula que contém xn e colocar nela o novo item.
- x1 - ··· - xn - nil
6 6
Frente Trás
Projeto de Algoritmos – Cap.3 Estruturas de Dados Básicas – Seção 3.3.2 49
∗ Transparências elaboradas por Charles Ornelas Almeida, Israel Guerra e Nivio Ziviani
Projeto de Algoritmos – Cap.4 Ordenação 1
Conteúdo do Capítulo
4.1 Ordenação Interna 4.1.7 Ordenação em Tempo Linear
4.1.1 Seleção ∗ Ordenação por Contagem
4.1.2 Inserção ∗ Radixsort para Inteiros
4.1.3 Shellsort ∗ Radixsort para Cadeias de
4.1.4 Quicksort Caracteres
e
♣ < ♦ < ♥ < ♠.
• Algoritmo:
1. Distribuir as cartas em treze montes: ases, dois, três, . . ., reis.
2. Colete os montes na ordem especificada.
3. Distribua novamente as cartas em quatro montes: paus, ouros,
copas e espadas.
4. Colete os montes na ordem especificada.
Projeto de Algoritmos – Cap.4 Ordenação 6
• Se para cada monte nós reservarmos uma área, então a demanda por
memória extra pode tornar-se proibitiva.
Ordenação Interna
• Na escolha de um algoritmo de ordenação interna deve ser
considerado o tempo gasto pela ordenação.
• Sendo n o número registros no arquivo, as medidas de complexidade
relevantes são:
– Número de comparações C(n) entre chaves.
– Número de movimentações M (n) de itens do arquivo.
• O uso econômico da memória disponível é um requisito primordial na
ordenação interna.
• Métodos de ordenação in situ são os preferidos.
• Métodos que utilizam listas encadeadas não são muito utilizados.
• Métodos que fazem cópias dos itens a serem ordenados possuem
menor importância.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1 8
Ordenação Interna
Ordenação Interna
• Algoritmo:
– Selecione o menor item do vetor.
– Troque-o com o item da primeira posição do vetor.
– Repita essas duas operações com os n − 1 itens restantes, depois
com os n − 2 itens, até que reste apenas um elemento.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.1 11
Vantagens:
Desvantagens:
• Algoritmo:
– Em cada passo a partir de i=2 faça:
∗ Selecione o i-ésimo item da seqüência fonte.
∗ Coloque-o no lugar apropriado na seqüência destino de acordo
com o critério de ordenação.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.2 15
• Solução:
– Utilizar um registro sentinela na posição zero do vetor.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.2 18
Shellsort
Shellsort
• Exemplo de utilização:
1 2 3 4 5 6
Chaves iniciais: O R D E N A
h=4 N A D E O R
h=2 D A N E O R
h=1 A D E N O R
Shellsort
h(s) = 1, para s = 1.
Shellsort
Shellsort
Shellsort: Análise
Shellsort
• Vantagens:
– Shellsort é uma ótima opção para arquivos de tamanho moderado.
– Sua implementação é simples e requer uma quantidade de código
pequena.
• Desvantagens:
– O tempo de execução do algoritmo é sensível à ordem inicial do
arquivo.
– O método não é estável,
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.4 28
Quicksort
Quicksort
Quicksort
Quicksort
1 2 3 4 5 6
O R D E N A
A R D E N O
A D R E N O
Quicksort
Procedimento Particao:
void Particao ( TipoIndice Esq, TipoIndice Dir , TipoIndice ∗ i , TipoIndice ∗ j , TipoItem ∗A)
{ TipoItem x , w;
∗ i = Esq; ∗ j = Dir ;
x = A[(∗ i + ∗ j ) / 2 ] ; /∗ obtem o pivo x ∗/
do
{ while ( x .Chave > A[∗ i ] .Chave) ( ∗ i )++;
while ( x .Chave < A[∗ j ] .Chave) ( ∗ j )−−;
i f (∗ i <= ∗ j )
{ w = A[∗ i ] ; A[∗ i ] = A[∗ j ] ; A[∗ j ] = w;
(∗ i )++; (∗ j )−−;
}
} while (∗ i <= ∗ j ) ;
}
Quicksort
Procedimento Quicksort:
Quicksort
1 2 3 4 5 6
Chaves iniciais: O R D E N A
1 A D R E N O
2 A D
3 E R N O
4 N R O
5 O R
A D E N O R
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.4 35
Quicksort: Análise
• Seja C(n) a função que conta o número de comparações.
• Pior caso:
C(n) = O(n2 )
Quicksort: Análise
• Melhor caso:
Quicksort
• Vantagens:
– É extremamente eficiente para ordenar arquivos de dados.
– Necessita de apenas uma pequena pilha como memória auxiliar.
– Requer cerca de n log n comparações em média para ordenar n
itens.
• Desvantagens:
– Tem um pior caso O(n2 ) comparações.
– Sua implementação é muito delicada e difícil:
∗ Um pequeno engano pode levar a efeitos inesperados para
algumas entradas de dados.
– O método não é estável.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.5 38
Heapsort
• Algoritmo:
1. Selecione o menor item do vetor.
2. Troque-o com o item da primeira posição do vetor.
3. Repita estas operações com os n − 1 itens restantes, depois com
os n − 2 itens, e assim sucessivamente.
Heapsort
Filas de Prioridades
• Aplicações:
– SOs usam filas de prioridades, nas quais as chaves representam o
tempo em que eventos devem ocorrer.
– Métodos numéricos iterativos são baseados na seleção repetida de
um item com maior (menor) valor.
– Sistemas de gerência de memória usam a técnica de substituir a
página menos utilizada na memória principal por uma nova página.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.5 40
Heapsort
Filas de Prioridades - Tipo Abstrato de Dados
• Operações:
1. Constrói uma fila de prioridades a partir de um conjunto com n
itens.
2. Informa qual é o maior item do conjunto.
3. Retira o item com maior chave.
4. Insere um novo item.
5. Aumenta o valor da chave do item i para um novo valor que é maior
que o valor atual da chave.
6. Substitui o maior item por um novo item, a não ser que o novo item
seja maior.
7. Altera a prioridade de um item.
8. Remove um item qualquer.
9. Ajunta duas filas de prioridades em uma única.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.5 41
Heapsort
Filas de Prioridades - Representação
Heapsort
Filas de Prioridades - Representação
• Observação:
Para implementar a operação Ajunta de forma eficiente e ainda
preservar um custo logarítmico para as operações Insere, Retira,
Substitui e Altera é necessário utilizar estruturas de dados mais
sofisticadas, tais como árvores binomiais (Vuillemin, 1978).
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.5 43
Heapsort
Filas de Prioridades - Algoritmos de Ordenação
• As operações das filas de prioridades podem ser utilizadas para
implementar algoritmos de ordenação.
• Basta utilizar repetidamente a operação Insere para construir a fila de
prioridades.
• Em seguida, utilizar repetidamente a operação Retira para receber os
itens na ordem reversa.
• O uso de listas lineares não ordenadas corresponde ao método da
seleção.
• O uso de listas lineares ordenadas corresponde ao método da
inserção.
• O uso de heaps corresponde ao método Heapsort.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.5 44
Heap
• É uma seqüência de itens com chaves c[1], c[2], . . . , c[n], tal que:
c[i] ≥ c[2i],
c[i] ≥ c[2i + 1],
1 S
2 R O 3
4 E 5 N A 6 D 7
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.5 45
Heap
Heap
• As chaves na árvore satisfazem a condição do heap.
• A chave em cada nó é maior do que as chaves em seus filhos.
• A chave no nó raiz é a maior chave do conjunto.
• Uma árvore binária completa pode ser representada por um array:
1 2 3 4 5 6 7
S R O E N A D
Heap
Heap
1 2 3 4 5 6 7
Chaves iniciais: O R D E N A S
Esq = 3 O R S E N A D
Esq = 2 O R S E N A D
Esq = 1 S R O E N A D
Heap
Heap
Programa para refazer a condição de heap:
Heap
Heap
Heap
Programa que implementa a operação de aumentar o valor da chave do
item i:
Heap
• Exemplo da operação de aumentar o valor da chave do item na
posição i:
(a) S (b) S
R O R O
i i
E N A D E N U D
(c) S (d) U i
i
R U R S
E N O D E N O D
Heap
Heapsort
• Algoritmo:
1. Construir o heap.
2. Troque o item na posição 1 do vetor (raiz do heap) com o item da
posição n.
3. Use o procedimento Refaz para reconstituir o heap para os itens
A[1], A[2], . . . , A[n − 1].
4. Repita os passos 2 e 3 com os n − 1 itens restantes, depois com os
n − 2, até que reste apenas um item.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.5 57
Heapsort
• Exemplo de aplicação do Heapsort:
1 2 3 4 5 6 7
S R O E N A D
R N O E D A S
O N A E D R
N E A D O
E D A N
D A E
A D
Heapsort
Programa que mostra a implementação do Heapsort:
Heapsort
• Vantagens:
– O comportamento do Heapsort é sempre O(n log n), qualquer que
seja a entrada.
• Desvantagens:
– O anel interno do algoritmo é bastante complexo se comparado
com o do Quicksort.
– O Heapsort não é estável.
• Recomendado:
– Para aplicações que não podem tolerar eventualmente um caso
desfavorável.
– Não é recomendado para arquivos com poucos registros, por causa
do tempo necessário para construir o heap.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.5 60
Complexidade
Inserção O(n2 )
Seleção O(n2 )
Shellsort O(n log n)
Quicksort O(n log n)
Heapsort O(n log n)
• O método é estável.
• Deve ser usado para arquivos com registros muito grandes, desde que
o tamanho do arquivo não exceda 1.000 elementos.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.5 68
• Apesar de ser cerca de duas vezes mais lento do que o Quicksort, não
necessita de nenhuma memória adicional.
Ordenação Parcial
Ordenação Parcial
Aplicações:
Ordenação Parcial
Algoritmos considerados:
• Seleção parcial.
• Inserção parcial.
• Heapsort parcial.
• Quicksort parcial.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.6 76
Seleção Parcial
• Princípio de funcionamento:
– Selecione o menor item do vetor.
– Troque-o com o item que está na primeira posição do vetor.
– Repita estas duas operações com os itens n − 1, n − 2 . . . n − k.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.6 77
Seleção Parcial
void SelecaoParcial(TipoVetor A,
Análise:
TipoIndice n, TipoIndice k)
{ TipoIndice i , j , Min ; TipoItem x ; • Comparações entre cha-
for ( i = 1; i <= k ; i ++) ves e movimentações de
{ Min = i ; registros:
for ( j = i + 1; j <= n ; j ++)
k2 k
i f (A[ j ] .Chave < A[Min ] .Chave) Min = j ; C(n) = kn − 2
− 2
x = A[Min ] ; A[Min] = A[ i ] ; A[ i ] = x ;
M (n) = 3k
}
}
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.6 78
Seleção Parcial
Inserção Parcial
Inserção Parcial
Heapsort Parcial
Heapsort Parcial
Quicksort Parcial
Quicksort Parcial
1 2 3 4 5 6
Chaves iniciais: O R D E N A
1 A D R E N O
2 A D
3 E R N O
4 N R O
5 O R
A D E N O R
Quicksort Parcial
• No quarto for, como podem haver itens iguais no vetor A, então o valor
de C[A[j]] é decrementado de 1 toda vez que um item A[j] é colocado
no vetor B. Isso garante que o próximo item com valor igual a A[j], se
existir, vai ser colocado na posição imediatamente antes de A[j] no
vetor B.
• O último for copia para A o vetor B ordenado. Essa cópia pode ser
evitada colocando o vetor B como parâmetro de retorno no
procedimento Contagem, como mostrado no Exercício 4.24.
07 01 01
33 22 07
18 ⇒ 33 ⇒ 07
22 07 18
01 07 22
07 18 33
↑ ↑
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.1.7 102
Primeiro refinamento:
Ordenação Externa
• A ordenação externa consiste em ordenar arquivos de tamanho maior
que a memória interna disponível.
• Os métodos de ordenação externa são muito diferentes dos de
ordenação interna.
• Na ordenação externa os algoritmos devem diminuir o número de
acesso as unidades de memória externa.
• Nas memórias externas, os dados ficam em um arquivo seqüencial.
• Apenas um registro pode ser acessado em um dado momento. Essa é
uma restrição forte se comparada com as possibilidades de acesso
em um vetor.
• Logo, os métodos de ordenação interna são inadequados para
ordenação externa.
• Técnicas de ordenação diferentes devem ser utilizadas.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.2 112
Ordenação Externa
Fatores que determinam as diferenças das técnicas de ordenação externa:
Ordenação Externa
Ordenação Externa
• Objetivo:
– Ordenar os 22 registros e colocá-los em uma fita de saída.
fita 4: AACEILNRT
fita 5: AAABCCLNO
fita 6: AADE
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.2.1 119
Entra 1 2 3
Entra 1 2 3
E I N T
L C O A*
R N E* T
A L O A*
C R E* T
N O A* A*
A T E* C*
C A* N* A*
L A* E* C*
E A* N* C*
A C* E* L*
A C* N* E*
C E* A L*
D E* N* A
A L* A C
A N* D A
O A A C
A D A
B A O C
A D
A B O C
D
Algoritmo:
Considerações Práticas
Considerações Práticas
Considerações Práticas
Considerações Práticas
Considerações Práticas
Intercalação Polifásica
• Solução:
– Intercalação polifásica.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.2.4 132
Intercalação Polifásica
• Neste ponto, uma das fitas de saída troca de papel com a fita de
entrada.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.2.4 133
Intercalação Polifásica
• Exemplo:
– Blocos ordenados obtidos por meio de seleção por substituição:
fita 1: AABCLO
fita 2:
fita 3: AACEINNRT AAACDEL
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.2.4 134
Intercalação Polifásica
• Exemplo:
– Depois da intercalação-de-2-caminhos das fitas 1 e 3 para a fita 2:
fita 1:
fita 2: AAAABCCEILNNORT
fita 3: AAACDEL
– Finalmente:
fita 1: AAAAAAABCCCDEEILLNNORT
fita 2:
fita 3:
Intercalação Polifásica
Intercalação Polifásica
Análise:
Quicksort Externo
Quicksort Externo
• Algoritmo:
1. Particionar A da seguinte forma:
{R1 , . . . , Ri } ≤ Ri+1 ≤ Ri+2 ≤ . . . ≤ Rj−2 ≤ Rj−1 ≤ {Rj , . . . , Rn },
2. chamar recursivamente o algoritmo em cada um dos subarquivos
A1 = {R1 , . . . , Ri } e A2 = {Rj , . . . , Rn }.
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.2.5 139
Quicksort Externo
Quicksort Externo
i Li Ls j i Li Ls j
área Linf Lsup área Linf Lsup
a) 5 3 10 6 1 7 4 b) 5 3 10 6 1 7 4 4
Ei Es Ei Es
i Li Ls j i Li Ls j
c) 5 3 10 6 1 7 4 4 5 d) 5 3 10 6 1 7 4 4 5 7
Ei Es Ei Es
i Li Ls j i Li Ls j
e) 5 3 10 6 1 7 7 4 5 7 f) 5 3 10 6 1 7 7 3 4 5 7
Ei Es Ei Es
i Li Ls j i Li Ls j
g) 3 3 10 6 1 7 7 4 5 3 7 h) 3 3 10 6 1 7 7 4 5 3 7
Ei Es Ei Es
Li
i Li Ls j i Ls j
i) 3 1 10 6 1 7 7 4 5 3 7 j) 3 1 10 6 1 7 7 4 5 3 7
Ei Es Ei Es
Li
i Ls j i Ls Li j
k) 3 1 10 6 1 10 7 4 5 3 7 l) 3 1 10 6 1 10 7 4 5 6 3 7
Ei Es Ei Es
i Ls Li j i Ls Li j
m) 3 1 10 6 6 10 7 4 5 3 7 n) 3 1 4 5 6 10 7 3 7
Ei Es Es Ei
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.2.5 141
Quicksort Externo
void QuicksortExterno(FILE ∗∗ArqLi , FILE ∗∗ArqEi , FILE ∗∗ArqLEs,
int Esq, int Dir )
{ int i , j ;
TipoArea Area ; /∗ Area de armazenamento interna ∗/
i f ( Dir − Esq < 1) return ;
FAVazia(&Area) ;
Particao (ArqLi , ArqEi , ArqLEs, Area, Esq, Dir , & i , & j ) ;
i f ( i − Esq < Dir − j )
{ /∗ ordene primeiro o subarquivo menor ∗/
QuicksortExterno(ArqLi , ArqEi , ArqLEs, Esq, i ) ;
QuicksortExterno(ArqLi , ArqEi , ArqLEs, j , Dir ) ;
}
else
{ QuicksortExterno(ArqLi , ArqEi , ArqLEs, j , Dir ) ;
QuicksortExterno(ArqLi , ArqEi , ArqLEs, Esq, i ) ;
}
}
Projeto de Algoritmos – Cap.4 Ordenação – Seção 4.2.5 142
• Objetivo da pesquisa:
Encontrar uma ou mais ocorrências de registros com chaves iguais à
chave de pesquisa.
• Tabela:
associada a entidades de vida curta, criadas na memória interna
durante a execução de um programa.
• Arquivo:
geralmente associado a entidades de vida mais longa, armazenadas
em memória externa.
• Depende principalmente:
1. Quantidade dos dados envolvidos.
2. Arquivo estar sujeito a inserções e retiradas frequentes.
Dicionário
• Nome comumente utilizado para descrever uma estrutura de dados
para pesquisa.
• Dicionário é um tipo abstrato de dados com as operações:
1. Inicializa
2. Pesquisa
3. Insere
4. Retira
• Analogia com um dicionário da língua portuguesa:
– Chaves ⇐⇒ palavras
– Registros ⇐⇒ entradas associadas com cada palavra:
∗ pronúncia
∗ definição
∗ sinônimos
∗ outras informações
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.1 7
Pesquisa Sequencial
• Método de pesquisa mais simples: a partir do primeiro registro,
pesquise sequencialmente até encontrar a chave procurada; então
pare.
• Armazenamento de um conjunto de registros por meio do tipo
estruturado arranjo:
#define MAXN 10
typedef long TipoChave;
typedef struct TipoRegistro {
TipoChave Chave;
/∗ outros componentes ∗/
} TipoRegistro ;
typedef int TipoIndice ;
typedef struct TipoTabela {
TipoRegistro Item [ MAXN + 1];
TipoIndice n;
} TipoTabela;
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.1 8
Pesquisa Sequencial
Pesquisa Sequencial
Pesquisa Sequencial
Pesquisa Binária
Árvores de Pesquisa
E D
E R D
3 7
2 4 6
• O nível do nó raiz é 0.
• Se um nó está no nível i então a raiz de suas subárvores estão no
nível i + 1.
• A altura de um nó é o comprimento do caminho mais longo deste nó
até um nó folha.
• A altura de uma árvore é a altura do nó raiz.
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.3.1 18
• Alguns comentários:
1. A retirada de um registro não é tão simples quanto a inserção.
2. Se o nó que contém o registro a ser retirado possui no máximo um
descendente ⇒ a operação é simples.
3. No caso do nó conter dois descendentes o registro a ser retirado
deve ser primeiro:
– substituído pelo registro mais à direita na subárvore esquerda;
– ou pelo registro mais à esquerda na subárvore direita.
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.3.1 23
3 7
2 4 6
Assim: para retirar o registro com chave 5 na árvore basta trocá-lo pelo
registro com chave 4 ou pelo registro com chave 6, e então retirar o nó que
recebeu o registro com chave 5.
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.3.1 24
bye
and easy
be to
bye
and to
be
be be
and to
and to
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.3.1 27
Caminhamento Central
Caminhamento Central
2 4 6
1
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.3.1 29
Análise
Análise
1. Para obter o pior caso basta que as chaves sejam inseridas em ordem
crescente ou decrescente. Neste caso a árvore resultante é uma lista
linear, cujo número médio de comparações é (n + 1)/2.
2. Para uma árvore de pesquisa randômica o número esperado de
comparações para recuperar um registro qualquer é cerca de
1, 39 log n, apenas 39% pior que a árvore completamente balanceada.
• Uma árvore A com n chaves possui n + 1 nós externos e estas n
chaves dividem todos os valores possíveis em n + 1 intervalos. Uma
inserção em A é considerada randômica se ela tem probabilidade igual
de acontecer em qualquer um dos n + 1 intervalos.
• Uma árvore de pesquisa randômica com n chaves é uma árvore
construida através de n inserções randômicas sucessivas em uma
árvore inicialmente vazia.
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.3.2 31
5 4
3 7 2 6
2 4 6 1 3 5 7
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.3.2 32
Árvores SBB
7 7
2,5 10 2 5 10
1 3,4 6 8,9 11 1 3 4 6 8 9 11
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.3.2.1 35
Árvores SBB
• Árvore 2-3 ⇒ árvore B binária (assimetria inerente)
1. Apontadores à esquerda apontam para um nó no nível abaixo.
2. Apontadores à direita podem ser verticais ou horizontais.
Eliminação da assimetria nas árvores B binárias ⇒ árvores B binárias
simétricas (Symmetric Binary B-trees – SBB)
• Árvore SBB tem apontadores verticais e horizontais, tal que:
1. todos os caminhos da raiz até cada nó externo possuem o mesmo
número de apontadores verticais, e
2. não podem existir dois apontadores horizontais sucessivos.
3 5 9
1 2 4 6 7 8 10
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.3.2.2 36
2 3 1 2 3 2
1 1 3
1 3 1 2 3 2
2 1 3
Exemplo
Inserção de uma sequência de chaves em uma árvore SBB:
1. Árvore à esquerda é obtida após a inserção das chaves 7, 10, 5.
2. Árvore do meio é obtida após a inserção das chaves 2, 4 na árvore
anterior.
3. Árvore à direita é obtida após a inserção das chaves 9, 3, 6 na árvore
anterior.
5 3 5 9
5 7 10 2 4 7 10 2 4 6 7 10
Procedimento Retira
Exemplo
5 3 5 9
5 7 10 2 4 7 10 2 4 6 7 10
3 5 9 4 9 4
2 4 6 10 2 3 6 10 2 3 6 10
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.3.2.2 49
2 chamadas DirCurto
Caso 2:
4 4 4
2 10
2 6 8 10 2 8
1 3 6 8 12
1 3 1 3 6 10
1a chamada DirCurto
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.3.2.2 50
2 6 10 2 6 10
1 3 5 8 12 1 3 5 8
2 6
1 3 5 8 10
4 4
2 6 10 2 6 10
1 3 5 8 9 12 1 3 5 8 9
4
4
2 6 9
2 6
1 3 5 8 10
1 3 5 8 10
9
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.3.2.2 51
Análise
Análise
• De fato Bayer (1972) mostrou que
log(n + 1) ≤ k ≤ 2 log(n + 2) − 2.
• Custo para manter a propriedade SBB ⇒ Custo para percorrer o
caminho de pesquisa para encontrar a chave, seja para inserí-la ou
para retirá-la.
• Logo: O custo é O(log n).
• Número de comparações em uma pesquisa com sucesso é:
melhor caso : C(n) = O(1)
pior caso : C(n) = O(log n)
caso médio : C(n) = O(log n)
• Observe: Na prática o caso médio para Cn é apenas cerca de 2%
pior que o Cn para uma árvore completamente balanceada, conforme
mostrado em Ziviani e Tompa (1982).
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.4 53
Pesquisa Digital
Trie
Exemplo
B = 010010
C = 010011
H = 011000
J = 100001
M = 101000
0 1
1 0
0 1 0 1
0 H J Q
1
0 1
B C
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.4.1 56
• Desvantagem:
– Uma grande desvantagem das tries é a formação de caminhos de
uma só direção para chaves com um grande número de bits em
comum.
– Exemplo: Se duas chaves diferirem somente no último bit, elas
formarão um caminho cujo comprimento é igual ao tamanho delas,
não importando quantas chaves existem na árvore.
– Caminho gerado pelas chaves B e C.
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.4.2 58
B = 010010 1
C = 010011 3 3
H = 011000 6 H J Q
J = 100001 B C
Q = 101000
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.4.2 60
Inserção da Chave K
1 1
3 3 3 3
6 H J Q 6 H 5 Q
B C B C J K
• Para inserir a chave K = 100010 na árvore à esquerda, a pesquisa inicia pela raiz e
termina quando se chega ao nó externo contendo J.
• Os índices dos bits nas chaves estão ordenados da esquerda para a direita. Bit de
índice 1 de K é 1 → a subárvore direita Bit de índice 3 → subárvore esquerda que
neste caso é um nó externo.
• Chaves J e K mantêm o padrão de bits 1x0xxx, assim como qualquer outra chave
que seguir este caminho de pesquisa.
• Novo nó interno repõe o nó J, e este com nó K serão os nós externos descendentes.
• O índice do novo nó interno é dado pelo 1o bit diferente das 2 chaves em questão,
que é o bit de índice 5. Para determinar qual será o descendente esquerdo e o
direito, verifique o valor do bit 5 de ambas as chaves.
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.4.2 61
Inserção da Chave W
• A inserção da chave W = 110110 ilustra um outro aspecto.
• Os bits das chaves K e W são comparados a partir do primeiro para
determinar em qual índice eles diferem (nesse casod os de índice 2).
• Portanto: o ponto de inserção agora será no caminho de pesquisa
entre os nós internos de índice 1 e 3.
• Cria-se aí um novo nó interno de índice 2, cujo descendente direito é
um nó externo contendo W e cujo descendente esquerdo é a
subárvore de raiz de índice 3.
3 2
6 H 3 W
B C 5 Q
J K
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.4.2 62
Estrutura de Dados
#define D 8 /∗ depende de TipoChave ∗/
typedef unsigned char TipoChave; /∗ a definir , depende da aplicacao ∗/
typedef unsigned char TipoIndexAmp;
typedef unsigned char TipoDib ;
typedef enum {
Interno , Externo
} TipoNo;
typedef struct TipoPatNo∗ TipoArvore ;
typedef struct TipoPatNo {
TipoNo nt ;
union {
struct {
TipoIndexAmp Index ;
TipoArvore Esq, Dir ;
} NInterno ;
TipoChave Chave;
} NO ;
} TipoPatNo;
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.4.2 63
Funções Auxiliares
short EExterno(TipoArvore p)
{ /∗ Verifica se p^ e nodo externo ∗/
return ( p−>nt == Externo ) ;
}
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.4.2 64
TipoArvore CriaNoExt(TipoChave k)
{ TipoArvore p;
p = (TipoArvore)malloc(sizeof(TipoPatNo) ) ;
p−>nt = Externo ; p−>NO .Chave = k ; return p;
}
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.4.2 65
Algoritmo de Pesquisa
• Continuação:
3. Se a raiz da subárvore corrente for um nó interno, vai-se para a
subárvore indicada pelo bit da chave k de índice dado pelo nó
corrente, de forma recursiva.
4. Depois são criados um nó interno e um nó externo: o primeiro
contendo o índice i e o segundo, a chave k. A seguir, o nó interno é
ligado ao externo pelo apontador de subárvore esquerda ou direita,
dependendo se o bit de índice i da chave k seja 0 ou 1,
respectivamente.
5. O caminho de inserção é percorrido novamente de baixo para cima,
subindo com o par de nós criados no Passo 4 até chegar a um nó
interno cujo índice seja menor que o índice i determinado no Passo
2. Este é o ponto de inserção e o par de nós é inserido.
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.4.2 68
Algoritmo de inserção
TipoArvore InsereEntre(TipoChave k , TipoArvore ∗ t , int i )
{ TipoArvore p;
i f ( EExterno(∗ t ) | | i < (∗ t)−>NO . NInterno . Index)
{ /∗ cria um novo no externo ∗/
p = CriaNoExt(k ) ;
i f ( Bit ( i , k) == 1)
return ( CriaNoInt( i , t , &p) ) ;
else return ( CriaNoInt( i , &p, t ) ) ;
}
else
{ i f ( Bit ((∗ t)−>NO . NInterno . Index , k) == 1)
(∗ t)−>NO . NInterno . Dir = InsereEntre(k,&(∗ t)−>NO . NInterno . Dir , i ) ;
else
(∗ t)−>NO . NInterno .Esq = InsereEntre(k,&(∗ t)−>NO . NInterno .Esq, i ) ;
return (∗ t ) ;
}
}
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.4.2 69
Algoritmo de inserção
• Hash significa:
1. Fazer picadinho de carne e vegetais para cozinhar.
2. Fazer uma bagunça. (Webster’s New World Dictionary)
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.5 71
N p
10 0,883
22 0,524
23 0,493
30 0,303
Funções de Transformação
void GeraPesos(TipoPesos p)
{ int i ;
struct timeval semente;
/∗ Utilizar o tempo como semente para a funcao srand ( ) ∗/
gettimeofday(&semente, NULL ) ;
srand( ( int ) (semente. tv_sec + 1000000∗semente. tv_usec ) ) ;
for ( i = 0; i < n ; i ++)
p[ i ] = 1+(int) (10000.0∗rand ( ) / ( RAND_MAX+1.0));
}
Listas Encadeadas
• Uma das formas de resolver as colisões é construir uma lista linear
encadeada para cada endereço da tabela. Assim, todas as chaves
com mesmo endereço são encadeadas em uma lista linear.
• Exemplo: Se a i-ésima letra do alfabeto é representada pelo número i
e a função de transformação h(Chave) = Chave mod M é utilizada
para M = 7, o resultado da inserção das chaves P E S Q U I S A na
tabela é o seguinte:
– h(A) = h(1) = 1, h(E) = h(5) = 5, h(S) = h(19) = 5, e assim por
diante.
T
0 - U - nil
1 - A - nil
2 - P - I - nil
3 - Q - nil
4 - nil
5 - E - S - S - nil
6 - nil
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.5.2 81
Análise
Endereçamento Aberto
• Quando o número de registros a serem armazenados na tabela puder
ser previamente estimado, então não haverá necessidade de usar
apontadores para armazenar os registros.
• Existem vários métodos para armazenar N registros em uma tabela
de tamanho M > N , os quais utilizam os lugares vazios na própria
tabela para resolver as colisões. (Knuth, 1973, p.518)
• No Endereçamento aberto todas as chaves são armazenadas na
própria tabela, sem o uso de apontadores explícitos.
• Existem várias propostas para a escolha de localizações alternativas.
A mais simples é chamada de hashing linear, onde a posição hj na
tabela é dada por:
Exemplo
• Se a i-ésima letra do alfabeto é representada pelo número i e a função
de transformação h(Chave) = Chave mod M é utilizada para M = 7.
• então o resultado da inserção das chaves L U N E S na tabela,
usando hashing linear para resolver colisões é mostrado abaixo.
• Por exemplo, h(L) = h(12) = 5, h(U ) = h(21) = 0, h(N ) = h(14) = 0,
h(E) = h(5) = 5, e h(S) = h(19) = 5.
T
0 U
1 N
2 S
3
4
5 L
6 E
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.5.3 87
Análise
• Seja α = N/M o fator de carga da tabela. Conforme demonstrado por
Knuth (1973), o custo de uma pesquisa com sucesso é
1 1
C(n) = 1+ ·
2 1−α
Vantagens:
• Simplicidade de implementação.
Desvantagens:
na qual h0 (x), h1 (x), . . . , hr−1 (x) são r funções não perfeitas descritas
pelos programas dos slides 77 ou 79, x é a chave de busca, e g um
arranjo especial que mapeia números no intervalo 0 . . . M − 1 para o
intervalo 0 . . . N − 1.
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.5.4 95
v 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
g[v] 3 3 1 2 8 8 5 3 12 -1 11 12 8 9 0
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.5.4 101
Análise
111
000
(a) (b) g fhp
S 00
11 0 1 h 0 (x)
0110 000
111
00
11 0 0 0 mar
1
0 jan
00
11 0 jan
000
111
1 1
00
11
00
11 00
11 2 3 2 3
fev Geração
0
1
00
11
2 3 h 1 (x) Atribuição
0
1
00
11
3 3 3 3
0
1
mar 2 fev
4 4
0
1
00
11
3 3
0
1 5 5
00
11 0
1
4 5 h 2 (x)
0
1
00 1
11
{1,2,4} {1,3,5} {0,2,5}
0 fev jan mar L
0 1 2
(a) Para S = {jan, fev, mar}, gera um 3-grafo 3-partido acíclico com M = 6
vértices e N = 3 arestas e um arranjo de arestas L obtido no momento
de verificar se o hipergrafo é acíclico.
(b) Constrói função hash perfeita que transforma o conjunto S de chaves
para o intervalo [0, 5], representada pelo arranjo g : [0, 5] → [0, 3] de
forma a atribuir univocamente uma aresta a um vértice.
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.5.5 124
• Utiliza três funções h0 , h1 and h2 , com intervalos {0, 1}, {2, 3} e {4, 5},
respectivamente, cujos intervalos não se sobrepõem e por isso o grafo
é 3-partido.
i a v Visitado u j Soma
2 {0, 2, 5} 2 False → True 5 2 0
1 False → True 2 1 0
0 False → True 0 0 0
1 {1, 3, 5} 2 True - - 3
1 False → True 3 1 3
0 False → True 1 0 3
0 {1, 2, 4} 2 False → True 4 2 0
1 True 4 2 0
0 True 4 2 3
• O comando a seguir:
while g[u] < 0 do g[u] := g[u] + Grafo.r;
irá fazer g[1] = g[1] + 3 = −3 + 3 = 0.
• Agora o comando
Tipog = array[0..MAXNUMVERTICES] of integer;
muda para
Tipog = array[0..MAXNUMVERTICES] of byte;
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.5.5 132
hp(k) = hi(k) (k), onde i(k) = (g[h0 (k)] + g[h1 (k)] + . . . + g[hr−1 (k)]) mod r
g fhp
0 0 0 mar fhpm
1 0 1 jan
0 mar
2 3 2 3
Ranking 1 jan
3 3 3 3 2 fev
4 2 4 fev
5 3 5 3
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.5.5 140
Tr
• A função rank usa um
0 = (0000) 2 2 algoritmo proposto por
g 1 = (0001) 2
2
0 2 = (0010) 2 2 Pagh (2001).
0
0 TabRank 3 = (0011) 2 1
0 k=4 4 = (0100) 2 2
• Usa ǫ M bits adicionais,
1
0 0 0 5 = (0101) 2 2 0 < ǫ < 1, para armazenar
a) b)
1 2 1 6 = (0110) 2 2
2 o rank de cada k−ésimo
1 7 = (0111) 2 1
3
1 8 = (1000) 2 2 índice de g em TabRank,
1 9 = (1001) 2 2
1 10 = (1010) 2 2
onde k = ⌊log(M )/ǫ⌋.
4
0 11 = (1011) 2 1
1 12 = (1100) 2 1
• Para uma avaliação de
5
1 13 = (1101) 2 1 rank (u) em O(1), é neces-
14 = (1110) 2 1
15 = (1111) 2 0
sário usar uma tabela Tr
auxiliar.
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.5.5 141
Implementação da Tabela Tr
• Para calcular o rank (u) usando as tabelas TabRank e Tr são
necessários dois passos:
– Obter o rank do maior índice precomputado v ≤ u em TabRank.
– Usar Tr para contar número de vértices atribuídos de v até u − 1.
• Na figura do slide 140 Tr possui 16 entradas necessárias para
armazenas todas as combinações possíveis de 4 bits.
• Por exemplo, a posição 0, cujo valor binário é (0000)2 , contém dois
valores diferentes de r = 3; na posição 3, cujo valor binário é (0011)2 ,
contém apenas um valor diferente de r = 3, e assim por diante.
• Cabe notar que cada valor de r ≥ 2 requer uma tabela Tr diferente.
• O procedimento a seguir considera que Tr é indexada por um número
de 8 bits e, portanto, MaxTrValue = 255. Além disso, no máximo 4
vértices podem ser empacotados em um byte, razão pela qual o anel
interno vai de 1 a 4.
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.5.5 143
Implementação da Tabela Tr
void GeraTr ( TipoTr Tr)
{ int i , j , v , Soma = 0;
for ( i = 0; i <= MAXTRVALUE ; i ++)
{ Soma = 0; v = i ;
for ( j = 1; j <= 4; j ++)
{ i f ( ( v & 3) != NAOATRIBUIDO ) Soma = Soma + 1;
v = v >> 2;
}
Tr [ i ] = Soma;
}
} /∗ GeraTr ∗/
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.5.5 144
Análise de Tempo
• O Programa 7.10 para verificar se um hipergrafo é acíclico do tem
complexidade O(|V | + |A|). Como |A| = O(|V |) para grafos esparsos
como os considerados aqui, a complexidade de tempo para gerar a
função de transformação é proporcional ao número de chaves N .
• O tempo necessário para avaliar a função hp do slide 132 envolve a
avaliação de três funções hash universais, com um custo final O(1).
• O tempo necessário para avaliar a função hpm do slide 144 tem um
custo final O(1), utilizando uma estrutura de dados sucinta que permite
computar em O(1) o número de posições atribuidas antes de uma
dada posição em um arranjo.
• A tabela Tr permite contar o número de vértices atribuídos em ǫ log M
bits com custo O(1/ǫ), onde 0 < ǫ < 1.
• Mais ainda, a avaliação da função rank é muito eficiente já que tanto
TabRank quanto Tr cabem inteiramente na memória cache da CPU.
Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária 5.5.5 148
∗ Transparências elaboradas por Wagner Meira Jr, Flávia Peligrinelli Ribeiro, Israel Guerra, Nívio Ziviani e Charles Ornelas
Almeida
Projeto de Algoritmos – Cap.1 Introdução 1
Conteúdo do Capítulo
Introdução
• Pesquisa em memória secundária: arquivos contém mais registros do que
a memória interna pode armazenar.
• Custo para acessar um registro é algumas ordens de grandeza maior do que
o custo de processamento na memória primária.
• Medida de complexidade: custo de trasferir dados entre a memória principal
e secundária (minimizar o número de transferências).
• Memórias secundárias: apenas um registro pode ser acessado em um dado
momento (acesso seqüencial).
• Memórias primárias: acesso a qualquer registro de um arquivo a um custo
uniforme (acesso direto).
• O aspecto sistema de computação é importante.
• As características da arquitetura e do sistema operacional da máquina
tornam os métodos de pesquisa dependentes de parâmetros que afetam
seus desempenhos.
Projeto de Algoritmos – Cap.6 Pesquisa em Memória Secundária – Seção 6.1 3
Memória Virtual
N◦ da N◦ do
página byte
Endereço
de p b
programa
Tabela_de_Páginas Página p
-
-
? ?
p′ p′ + b
p′ = nil → página não
presente na
memória
Projeto de Algoritmos – Cap.6 Pesquisa em Memória Secundária – Seção 6.1.1 8
Memória Virtual
• Em casos em que precisamos manipular mais de um arquivo ao
mesmo tempo:
– A tabela de páginas para cada arquivo pode ser declarada
separadamente.
– A fila de molduras é única → cada moldura deve ter indicado o
arquivo a que se refere aquela página.
Memória Virtual
P1 P3
Consulta p Determina Página
- tabela de - moldura
páginas - para página p′ • Quadrados → resulta-
6 p′ dos de processos ou ar-
p ?
A2 P5 quivos.
Fila Grava página
de na memória
molduras p secundária • Retângulos → proces-
Programa p′ p′
Usuário p′ sos transformadores de
A1 A3 p′
6
Tabela
Memória informação.
de
páginas secundária Página
6 p6
p′ p
? p′ ?
P2 P4
Determina Recupera página
endereço da memória
p′ Página
real secundária
Projeto de Algoritmos – Cap.6 Pesquisa em Memória Secundária – Seção 6.2 15
1 3 5 7 11 2 14 17 20 21 3 25 29 32 36 4 41 44 48
Projeto de Algoritmos – Cap.6 Pesquisa em Memória Secundária – Seção 6.2 16
Árvores B
• Árvores n-árias: mais de um registro por nodo.
• Em uma árvore B de ordem m:
– página raiz: 1 e 2m registros.
– demais páginas: no mínimo m registros e m + 1 descendentes e no
máximo 2m registros e 2m + 1 descendentes.
– páginas folhas: aparecem todas no mesmo nível.
• Registros em ordem crescente da esquerda para a direita.
• Extensão natural da árvore binária de pesquisa.
• Árvore B de ordem m = 2 com três níveis:
30hhh
hhh
10 20 40 50
`
` `
``
```
`
`
3489 11 13 17
25 28
33 36
43 45 48
52 55
Projeto de Algoritmos – Cap.6 Pesquisa em Memória Secundária – Seção 6.3.1 19
• Estrutura de Dados:
• Operações:
– Inicializa
– Pesquisa
– Insere
– Remove
Projeto de Algoritmos – Cap.6 Pesquisa em Memória Secundária – Seção 6.3.1 21
Árvores B - Pesquisa
Árvores B - Inserção
1. Localizar a página apropriada aonde o regisro deve ser inserido.
2. Se o registro a ser inserido encontra uma página com menos de 2m
registros, o processo de inserção fica limitado à página.
3. Se o registro a ser inserido encontra uma página cheia, é criada uma
nova página, no caso da página pai estar cheia o processo de divisão
se propaga.
Exemplo: Inserindo o registro com chave 14.
1 10
``
```
`
23489 16 20 25 29
3 (a)
110 20
``
` `
` `
3489 25 29 (b)
2
3 14 16
4
Projeto de Algoritmos – Cap.6 Pesquisa em Memória Secundária – Seção 6.3.1 23
Árvores B - Inserção
Exemplo de inserção das chaves: 20, 10, 40, 50, 30, 55, 3, 11, 4, 28, 36,
33, 52, 17, 25, 13, 45, 9, 43, 8 e 48
(a)
20
(b)
30 P
PP
10 20
40 50
(c) 10 20 30 40
( ( (
(
Ph h hh h
( (
( P
P h
h
3 4
11 13 17
25 28
33 36
50 52 55
(d)
30hhh
hhh
10 20 40 50
` `
`
``
```
`
`
3489 11 13 17
25 28
33 36
43 45 48
52 55
Projeto de Algoritmos – Cap.6 Pesquisa em Memória Secundária – Seção 6.3.1 24
Árvores B - Remoção
Árvores B - Remoção
4j 4j 6j
H H , ll
H
* , ,, ll
j j 4j 8j
2 6 8 6 8
@@ T T AA AA
j j 5 7j9j
j jjj j 7j 9j
1 3 1 2 5 7 9 1 2 5
(a) Página vizinha possui mais do que m registros
4j 4j j
,, ll * ,
, ll
2j 6j j 6j 4 6
AA AA AA T
j j 5j 7j j j jj
1 3 1 2 5 7 1 2 5 7
(b) Página vizinha possui exatamente m registros
Projeto de Algoritmos – Cap.6 Pesquisa em Memória Secundária – Seção 6.3.1 30
Árvores B - Remoção
(d) 13 25 43 48
Árvores B* - Pesquisa
∗ Transparências elaboradas por Charles Ornelas Almeida, Israel Guerra e Nivio Ziviani
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos 1
Conteúdo do Capítulo
7.1 Definições Básicas 7.5 Busca em Largura
7.2 O Tipo Abstrato de Dados Grafo 7.6 Ordenação Topológica
7.2.1 Implementação por meio de Ma- 7.7 Componentes Fortemente Conectados
trizes de Adjacência
7.8 Árvore Geradora Mínima
7.2.2 Implementação por meio de Lis-
7.8.1 Algoritmo Genérico para Obter a
tas de Adjacência Usando Apon-
Árvore Geradora Mínima
tadores
7.8.2 Algoritmo de Prim
7.2.3 Implementação por meio de Lis-
tas de Adjacência Usando Ar- 7.8.2 Algoritmo de Kruskal
ranjos 7.9 Caminhos mais Curtos
7.2.4 Programa Teste para as Três Im- 7.10 O Tipo Abstrato de Dados Hipergrafo
plementações 7.10.1 Implementação por meio de Matri-
7.3 Busca em Profundidade zes de Incidência
7.4 Verificar se Grafo é Acíclico 7.10.1 Implementação por meio de Listas
7.4.1 Usando Busca em Profundidade de Incidência Usando Arranjos
7.4.1 Usando o Tipo Abstrato de Da-
dos Hipergrafo
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos 2
Motivação
• Existe um tipo abstrato chamado grafo que é usado para modelar tais
situações.
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos 3
Aplicações
Conceitos Básicos
• Grafo: conjunto de vértices e arestas.
• Vértice: objeto simples que pode ter nome e outros atributos.
• Aresta: conexão entre dois vértices.
3 aresta
0 1 4
2 vértice
• Notação: G = (V, A)
– G: grafo
– V: conjunto de vértices
– A: conjunto de arestas
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.1 5
Grafos Direcionados
0 1 4
3 2 5
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.1 6
0 1 4
3 2 5
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.1 7
Grau de um Vértice
Ciclos
• Em um grafo direcionado:
– Um caminho (v0 , v1 , . . . , vk ) forma um ciclo se v0 = vk e o caminho
contém pelo menos uma aresta.
– O ciclo é simples se os vértices v1 , v2 , . . . , vk são distintos.
– O self-loop é um ciclo de tamanho 1.
– Dois caminhos (v0 , v1 , . . . , vk ) e (v0′ , v1′ , . . . , vk′ ) formam o mesmo
ciclo se existir um inteiro j tal que vi′ = v(i+j) mod k para
i = 0, 1, . . . , k − 1.
Ciclos
3 2 5
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.1 11
Componentes Conectados
e {3}.
3 2 5
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.1 12
Grafos Isomorfos
0 1
4 5 s w x t
7 6 v z y u
3 2
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.1 14
Subgrafos
0 1 4 1 4
3 2 5 2 5
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.1 15
0 1 0 1
2 2
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.1 16
0 1 4 0 1 4
3 2 5 3 2 5
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.1 17
Grafos Completos
Árvores
• Árvore livre: grafo não direcionado acíclico e conectado. É comum
dizer apenas que o grafo é uma árvore omitindo o “livre”.
• Floresta: grafo não direcionado acíclico, podendo ou não ser
conectado.
• Árvore geradora de um grafo conectado G = (V, A): subgrafo que
contém todos os vértices de G e forma uma árvore.
• Floresta geradora de um grafo G = (V, A): subgrafo que contém
todos os vértices de G e forma uma floresta.
(a) (b)
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.2 20
i f ( ! ListaAdjVazia(v,Grafo) )
{ Aux = PrimeiroListaAdj (v,Grafo ) ;
FimListaAdj = FALSE ;
while ( ! FimListaAdj)
ProxAdj(&v , Grafo, &u, &Peso, &Aux, &FimListaAdj ) ;
}
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.2.1 24
Matriz de Adjacência
0 1 4 0 1 4
3 2 5 3 2 5
0 1 2 3 4 5 0 1 2 3 4 5
0 1 1 0 1 1
1 1 1 1 1 1
2 1 1 2 1 1
3 1 3
4 4
5 5
(a) (b)
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.2.1 26
3 0 1 5
5
0 1 1 3 2 7
1
7 2
3 2 3
0 1 5
5
0 1 0 5 2 7
1
7 1 7
2
3 2
3
Busca em Profundidade
Busca em Profundidade
b( / ) b( / ) b( / )
b( / ) 2 3 b( / ) 2 3 b( / ) 2 3
b( / ) b( / ) b( / )
b( / ) c(7/ ) p(7/8)
VisitaDfs é O(|A|).
Classificação de Arestas
Classificação de Arestas
• Classificação de arestas pode ser útil para derivar outros algoritmos.
• Na busca em profundidade cada aresta pode ser classificada pela cor
do vértice que é alcançado pela primeira vez:
– Branco indica uma aresta de árvore.
– Cinza indica uma aresta de retorno.
– Preto indica uma aresta de avanço quando u é descoberto antes de
v ou uma aresta de cruzamento caso contrário.
3/6 2/9 1/10
arv arv
2 1 0
3 cruz 4 cruz 5
4/5 7/8 11/12
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.4.1 58
Busca em Largura
Busca em Largura
Ordenação Topológica
• Pode ser vista como uma ordenação de seus vértices ao longo de uma
linha horizontal de tal forma que todas as arestas estão direcionadas
da esquerda para a direita.
Ordenação Topológica
• Os grafos direcionados acíclicos são usados para indicar precedências
entre eventos.
• Uma aresta direcionada (u, v) indica que a atividade u tem que ser
realizada antes da atividade v.
1/18 16/17 19/20
0 5 9
2/15 7/12
4/5 3 1 6 8 9/10
2 4 7
3/14 6/13 8/11
9 0 5 1 2 4 6 7 8 3
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.6 74
Ordenação Topológica
0 1 0 1 0,1,2
3 2 3 2 3
2. Obtem GT .
3 2 3 2 arv
cruz
4/5 3/6 7/8 2/5
1
0 0
6 5
1 1
1 2 2 3 1 2 2 3
2 2
5 6 4 4 4
4 5 4 5
3 3
(a) (b)
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.8.1 88
• A árvore começa por um vértice qualquer (no caso 0) e cresce até que
“gere” todos os vértices em V .
1 3 1 3 1 3
2 2 2
4 5 4 5 4 5
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.8.3 101
void Kruskal ( ) ;
{
1. S = ∅ ;
2. for (v=0;v < Grafo.NumVertices) CriaConjunto ( v ) ;
3. Ordena as arestas de A pelo peso;
4. for (cada ( u, v ) de A tomadas em ordem ascendente de peso)
5. i f ( EncontreConjunto (u) ! = EncontreConjunto ( v ) )
6. { S = S+ { (u, v ) } ;
7. Uniao ( u, v ) ;
}
}
Algoritmo de Dijkstra
• Mantém um conjunto S de vértices cujos caminhos mais curtos até um
vértice origem já são conhecidos.
• Produz uma árvore de caminhos mais curtos de um vértice origem s
para todos os vértices que são alcançáveis a partir de s.
• Utiliza a técnica de relaxamento:
– Para cada vértice v ∈ V o atributo p[v] é um limite superior do peso
de um caminho mais curto do vértice origem s até v.
– O vetor p[v] contém uma estimativa de um caminho mais curto.
• O primeiro passo do algoritmo é inicializar os antecessores e as
estimativas de caminhos mais curtos:
– Antecessor[v] = nil para todo vértice v ∈ V ,
– p[u] = 0, para o vértice origem s, e
– p[v] = ∞ para v ∈ V − {s}.
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.9 110
Relaxamento
5 1 6 5 1 6 5 1 6
2 3 2 3 2 3
2 2 3 6 2 3
5 1 6 5 1 6 5 1 6
2 3 2 3 2 3
5 2 3 5 2 3 5 2 3
(a) ∅ ∞ ∞ ∞ ∞ ∞
(b) {0} 0 1 ∞ 3 10
(c) {0, 1} 0 1 6 3 10
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.9 114
5 1 6 5 1 6 5 1 6
2 3 2 3 2 3
2 2 3 6 2 3
5 1 6 5 1 6 5 1 6
2 3 2 3 2 3
5 2 3 5 2 3 5 2 3
(d) {0, 1, 3} 0 1 5 3 9
(e) {0, 1, 3, 2} 0 1 5 3 6
(f) {0, 1, 3, 2, 4} 0 1 5 3 6
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.9 115
Algoritmo de Dijkstra
• Para cada vértice v, p[v] é o caminho mais curto obtido até o momento,
de v até o vértice raiz.
0 11
00
1
00
11
h0 (x)
Arestas
00
11
00
11
(1, 2, 4, 7)
0
1
00
11
0
1
2
00
11
3
0
1
h1 (x) 11 (1, 3, 5, 8)
00
0
1
0
1
0
1
(0, 2, 5, 9)
4
0
1
5 h2 (x)
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.10 120
0 11
00
1 h0 (x) Arestas 0 1 2
00
11 Arestas
|A|=3 (1,2,4) (1,3,5) (0,2,5)
00
11
00
11
(1, 2, 4, 7)
0
1
00
11 1
0
2 0
1
00
11
3
0
1
h1 (x) 0 (1, 3, 5, 8)
1 Prim 0 1 2 3 4 5
|V|=3 2 1 5 4 6 8
0
1
0
1
0
1
(0, 2, 5, 9)
4
0
1
5 h2 (x) Prox 0 1 2 3 4 5 6 7 8
r|A|=3x3=9 −1 0 −1 −1 −1 3 −1 −1 7
(a) (b)
Projeto de Algoritmos – Cap.7 Algoritmos em Grafos – Seção 7.10.2 133
i f ( ExisteAresta(&Aresta, &Grafo) )
p r i n t f ( "Sim\n" ) ;
else p r i n t f ( "Nao\n" ) ;
p r i n t f ( " Retira aresta : " ) ;
for ( j = 0; j < Grafo. r ; j ++) scanf( "%d∗[^\n] " , &Aresta . Vertices [ j ] ) ;
getchar ( ) ;
i f ( ExisteAresta(&Aresta, &Grafo) )
{ Aresta = RetiraAresta(&Aresta, &Grafo ) ;
p r i n t f ( "Aresta retirada : " ) ;
for ( i = 0; i < Grafo. r ; i ++) p r i n t f ( "%3d" , Aresta . Vertices [ i ] ) ;
p r i n t f ( "%4d\n" , Aresta .Peso) ;
}
else p r i n t f ( "Aresta nao existe \n" ) ;
ImprimeGrafo(&Grafo ) ;
return 0;
}
Processamento de Cadeias de
Caracteres ∗
∗ Transparências elaboradas por Fabiano Cupertino Botelho, Charles Ornelas Almeida, Israel Guerra e Nivio Ziviani
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres 1
Conteúdo do Capítulo
8.2 Compressão
8.2.1 Por Que Usar Compressão
8.2.2 Compressão de Textos em Linguagem Natural
8.2.3 Codificação de Huffman Usando Palavras
8.2.4 Codificação de Huffman Usando Bytes
8.2.5 Pesquisa em Texto Comprimido
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1 2
Definição e Motivação
• Cadeia de caracteres: sequência de elementos denominados
caracteres.
• Exemplos de aplicação:
– edição de texto;
– recuperação de informação;
– estudo de sequências de DNA em biologia computacional.
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1 3
Notação
Categorias de Algoritmos
• P pré-processado:
– algoritmo sequencial;
– padrão conhecido anteriormente permitindo seu
pré-processamento.
– complexidade de tempo O(n) e de espaço O(m + c), no pior caso.
– ex.: programas para edição de textos.
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1 6
Categorias de Algoritmos
• P e T são pré-processados:
– algoritmo constrói índice.
– complexidade de tempo O(log n) e de espaço é O(n).
– tempo para obter o índice é grande, O(n) ou O(n log n).
– compensado por muitas operações de pesquisa no texto.
– Tipos de índices mais conhecidos:
∗ Arquivos invertidos
∗ Árvores trie e árvores Patricia
∗ Arranjos de sufixos
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1 7
• Para cada palavra distinta, uma lista de posições onde ela ocorre no
texto é armazenada.
exemplo 7
exercem 45
fascínio 53
palavras 26 36
tem 22
texto 1 16
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1 9
m exemplo: 7
x e
e r exercem: 45
f fascínio: 53
p
palavras: 26,36
t m tem: 22
e
x texto: 1, 16
Casamento Exato
• Consiste em obter todas as ocorrências exatas do padrão no texto.
Ex.: ocorrência exata do padrão teste.
teste
os testes testam estes alunos . . .
• Dois enfoques:
• Pior caso: Cn = m × n.
Autômatos
Tipos de Autômatos
Exemplo de Autômatos
• Autômato finito não-determinista.
A partir do estado 0, através do caractere de transição a é possível
atingir os estados 2 e 3.
a
0 3
a c
1 2
b
a c
1 2
b
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1.1 20
a c
1 2
b
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1.1 21
Transições Vazias
Estados Ativos
Ciclos em Autômatos
• Os autômatos abaixo são acíclicos pois as transições não formam ciclos.
a d
0 3 0 3
a c a c
1 2 1 2
b b
Ex: o autômato abaixo reconhece ba, bba, bbba, bbbba, e assim por diante.
a
b 0 1
b
a
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1.1 24
Knuth-Morris-Pratt (KMP)
• Até 1971, o limite inferior conhecido para busca exata de padrões era
O(mn).
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1.1 26
KMP - 2DPDA
• Em 1971, Cook provou que qualquer problema que puder ser resolvido por
um autômato determinista de dois caminhos com memória de pilha (Two-way
Deterministic Pushdown Store Automaton, 2DPDA) pode ser resolvido em
tempo linear por uma máquina RAM.
• O 2DPDA é constituído de:
– uma fita apenas para leitura;
– uma pilha de dados (memória temporária);
– um controle de estado que permite mover a fita para esquerda ou direita,
empilhar ou desempilhar símbolos, e mudar de estado.
# c 1 c 2 ... c n $ p 1 p 2 ... p m φ
Cabeça de leitura
Controle c n
Pilha
c n−1
...
c 1
#
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1.1 27
Controle c n
Pilha
c n−1
...
c 1
KMP - Algoritmo
Shift-And
Shift-And - Algoritmo
sHift-And - Pré-processamento
1 2 3 4 5
M[t] 1 0 0 1 0
M[e] 0 1 0 0 1
M[s] 0 0 1 0 0
Shift-And - Pesquisa
• O valor do conjunto é inicializado como R = 0m (0m significa 0 repetido
m vezes).
• Para cada novo caractere ti+1 lido do texto o valor do conjunto R′ é
atualizado: R′ = ((R >> 1) | 10m−1 ) & M [T [i]].
• A operação “>>” desloca todas as posições para a direita no passo
i + 1 para marcar quais posições de P eram sufixos no passo i.
• A cadeia vazia ǫ também é marcada como um sufixo, permitindo um
casamento na posição corrente do texto (self-loop no início do
autômato).
Σ
t e s t e
0 1 2 3 4 5
Shift-And - Implementação
Shift−And ( P = p1 p2 · · · pm , T = t1 t2 · · · tn )
{ /∗−−Préprocessamento−−∗/
for ( c∈ Σ ) M [ c ] = 0m ;
for ( j = 1; j <= m; j ++) M [ pj ] = M [ pj ] | 0j−1 10m−j ;
/∗−− Pesquisa−−∗/
R = 0m ;
for ( i = 1; i <= n ; i ++)
{ R = ( ( R >> 1 | 10m−1 ) & M [ T [ i ] ] ) ;
i f ( R & 0m−1 1 6= 0m ) ’Casamento na posicao i − m + 1’ ;
}
}
• As operações and, or, deslocamento à direita e complemento não
podem ser realizadas com eficiência na linguagem Pascal padrão, o
que compromete o conceito de paralelismo de bit.
• Análise: O custo do algoritmo Shift-And é O(n), desde que as
operações possam ser realizadas em O(1) e o padrão caiba em umas
poucas palavras do computador.
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1.1 37
Boyer-Moore-Horspool (BMH)
Funcionamento do BM e BMH
BM - Heurística Ocorrência
• Alinha a posição no texto que causou a colisão com o primeiro caractere no
padrão que casa com ele;
Ex.: P ={cacbac}, T ={aabcaccacbac}.
1 2 3 4 5 6 7 8 9 0 1 2
c a c b a c
a a b c a c c a c b a c
c a c b a c
c a c b a c
c a c b a c
c a c b a c
• A partir da posição 6, da direita para a esquerda, existe uma colisão na
posição 4 de T , entre b do padrão e c do texto.
• Logo, o padrão deve ser deslocado para a direita até o primeiro caractere no
padrão que casa com c.
• O processo é repetido até encontrar casamento a partir da posição 7 de T .
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1.1 40
BM - Heurística Casamento
• Ao mover o padrão para a direita, faça-o casar com o pedaço do texto
anteriormente casado.
Ex.: P ={cacbac} no texto T ={aabcaccacbac}.
1 2 3 4 5 6 7 8 9 0 1 2
c a c b a c
a a b c a c c a c b a c
c a c b a c
c a c b a c
• Novamente, a partir da posição 6, da direita para a esquerda, existe uma
colisão na posição 4 de T , entre o b do padrão e o c do texto.
• Neste caso, o padrão deve ser deslocado para a direita até casar com o
pedaço do texto anteriormente casado, no caso ac, deslocando o padrão 3
posições à direita.
• O processo é repetido mais uma vez e o casamento entre P e T ocorre.
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1.1 41
Escolha da Heurística
BMH - Implementação
BMHS - Implementação
BH - Análise
BMH - Análise
BMHS - Análise
Casamento Aproximado
• O casamento aproximado de cadeias permite operações de inserção,
substituição e retirada de caracteres do padrão. Ex.: Três ocorrências
do padrão teste em que os casos de inserção, substituição, retirada
de caracteres no padrão acontecem:
1. um espaço é inserido entre o terceiro e quarto caracteres do
padrão;
2. o último caractere do padrão é substituído pelo caractere a;
3. o primeiro caractere do padrão é retirado.
tes te
testa
este
os testes testam estes alunos . . .
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1.2 51
Distância de Edição
Casamento Aproximado
• A busca aproximada só faz sentido para 0 < k < m, pois para k = m toda
subcadeia de comprimento m pode ser convertida em P por meio da
substituição de m caracteres.
• O nível de erro α = k/m, fornece uma medida da fração do padrão que pode
ser alterado.
(a) Σ Σ Σ Σ Σ Σ • P ={teste} e k = 1.
t e s t e
0 1 2 3 4 5 • (a) inserção; (b) substitui-
Σ ção e (c) retirada.
t e s t e
0 1 2 3 4 5 • Casamento de caractere
(b) Σ Σ Σ Σ Σ
é representado por uma
e s t e
1 2 3 4 5 aresta horizontal. Avança-
Σ mos em P e T .
t e s t e
0 1 2 3 4 5
• O self-loop permite que
(c) e e e e e
uma ocorrência se inicie em
e s t e
1 2 3 4 5 qualquer posição em T .
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1.2 54
Σ Σ Σ Σ Σ
e s t e
1 2 3 4 5
• P ={teste} e K = 2.
• As três operações de distância de edição estão juntas em um único autômato:
– Linha 1: casamento exato (k = 0);
– Linha 2: casamento aproximado permitindo um erro (k = 1);
– Linha 3: casamento aproximado permitindo dois erros (k = 2).
• Uma vez que um estado no autômato está ativo, todos os estados nas linhas
seguintes na mesma coluna também estão ativos.
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.1.2 57
• Padrão: teste.
Compressão - Motivação
Razão de Compressão
c) 4 2 d) 4 2
2 rosa 2 uma 4 rosa uma
0 1 0 1 0 1
para cada , é 2 2
0 1 0 1
para cada , é
e) 4 f) 10
6 rosa 0 1
0 1
rosa 6
uma 4 0 1
0 1
uma 4
2 2 0 1
0 1 0 1
2 2
para cada , é
0 1 0 1
para cada , é
Árvore de Huffman
Árvore de Huffman
O Algoritmo
• A entrada do algoritmo é um vetor A contendo as frequências das
palavras em ordem não-crescente.
• Frequências relativas à frase exemplo: “para cada rosa rosa,
uma rosa é uma rosa”
4 2 1 1 1 1
1 2 n
a) ...
Frequências
Folha Prox Raiz
1 n
b) ... ... ... ...
1 2 3 n
a) ...
Profundidades dos nós internos obtida com a segunda fase tendo como
entrada o vetor exibido na letra k do slide 84.
0 1 2 3 3
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.2.3 87
1 2 n
a) ...
1 2 4 4 4 4
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.2.3 89
Código Canônico
• Os comprimentos dos códigos obedecem ao algoritmo de Huffman.
• Códigos de mesmo comprimento são inteiros consecutivos.
• A partir dos comprimentos obtidos, o cálculo dos códigos é trivial: o primeiro
código é composto apenas por zeros e, para os demais, adiciona-se 1 ao
código anterior e faz-se um deslocamento à esquerda para obter-se o
comprimento adequado quando necessário.
• Codificação Canônica Obtida:
Obtenção do código:
• Parâmetros: vetores Base e Offset, índice i do símbolo (Tabela da
transparência 71) a ser codificado e o comprimento MaxCompCod dos
vetores Base e Offset.
• No anel while é feito o cálculo do comprimento c de código a ser
utilizado.
• A seguir, basta saber qual a ordem do código para o comprimento c
(i − Offset[c]) e somar esse valor à Base[c].
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.2.3 94
Exemplo de Codificação
Exemplo de Decodificação
• Decodificação da sequência de bits “1101”:
• O método original proposto por Huffman (1952) tem sido usado como
um código binário.
• Nesse caso, o oitavo bit é usado para marcar o primeiro byte do código
da palavra, sendo chamado de código de Huffman com marcação.
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.2.4 101
• Exemplo:
– Código pleno para “uma” com 3 bytes: “47 81 8”.
– Código com marcação para “uma” com 3 bytes: “175 81 8”
– Note que o primeiro byte é 175 = 47 + 128.
b) Árvore ótima
...
... ...
254 elementos
256 elementos 2 elementos 254 nós vazios
• Na Figura, o alfabeto possui 512 símbolos (nós folhas), todos com a mesma
frequência de ocorrência.
• O segundo nível tem 254 espaços vazios que poderiam ser ocupados com
símbolos, mudando o comprimento de seus códigos de 2 para 1 byte.
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.2.4 103
Alterações:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0
Procedimento Escreve
Resultados Experimentais
ama
puma
uma
umas
Projeto de Algoritmos – Cap.8 Processamento de Cadeias de Caracteres – Seção 8.2.5 153
Pré-Processamento:
rosa 011
roupa 010 XXX
azul 000
Conteúdo do Capítulo
Introdução
• Problemas intratáveis ou difíceis são comuns na natureza e nas áreas do
conhecimento.
• Problemas “fáceis”: resolvidos por algoritmos polinomiais.
• Problemas “difíceis”: somente possuem algoritmos exponenciais para
resolvê-los.
• A complexidade de tempo da maioria dos problemas é polinomial ou
exponencial.
• Polinomial: função de complexidade é O(p(n)), onde p(n) é um polinômio.
– Ex.: algoritmos com pesquisa binária (O(log n)), pesquisa sequencial
(O(n)), ordenação por inserção (O(n2 )), e multiplicação de matrizes
(O(n3 )).
• Exponencial: função de complexidade é O(cn ), c > 1.
– Ex.: problema do caixeiro viajante (PCV) (O(n!)).
– Mesmo problemas de tamanho pequeno a moderado não podem ser
resolvidos por algoritmos não-polinomiais.
Projeto de Algoritmos – Cap.9 Problemas N P -Completo e Algoritmos Aproximados – Seção 9.1 3
Problemas N P-Completo
Caminho em um Grafo
• Considere um grafo com peso nas arestas, dois vértices i, j e um
inteiro k > 0.
5 12 j
2 7 9 10 13
11 5 1
3 2 8 3
i 7 3
Coloração de um Grafo
• Em um grafo G = (V, A), mapear C : V ← S, sendo S um conjunto
finito de cores tal que se vw ∈ A então c(v) 6= c(w) (vértices adjacentes
possuem cores distintas).
• O número cromático X(G) de G é o menor número de cores
necessário para colorir G, isto é, o menor k para o qual existe uma
coloração C para G e |C(V )| = k.
• O problema é produzir uma coloração ótima, que é a que usa apenas
X(G) cores.
• Formulação do tipo “sim/não”: dados G e um inteiro positivo k, existe
uma coloração de G usando k cores?
– Fácil: k = 2.
– Difícil: k > 2.
• Aplicação: modelar problemas de agrupamento (clustering) e de
horário (scheduling).
Projeto de Algoritmos – Cap.9 Problemas N P -Completo e Algoritmos Aproximados – Seção 9.1 7
• Variáveis com interseção nos tempos de vida útil não podem ocupar o
mesmo registrador.
Ciclo de Hamilton
• Ciclo de Hamilton: ciclo simples (passa por todos os vértices uma
única vez).
• Caminho de Hamilton: caminho simples (passa por todos os
vértices uma única vez).
• Exemplo de ciclo de Hamilton: 0 1 4 2 3 0. Exemplo de caminho de
Hamilton: 0 1 4 2 3.
0 1 • Existe um ciclo de Hamilton no grafo G?
4
– Fácil: Grafos com grau máximo = 2 (vér-
tices com no máximo duas arestas inci-
3 2 dentes).
– Difícil: Grafos com grau > 2.
• É um caso especial do PCV. Pares de vértices com uma aresta entre
eles tem distância 1 e pares de vértices sem aresta entre eles têm
distância infinita.
Projeto de Algoritmos – Cap.9 Problemas N P -Completo e Algoritmos Aproximados – Seção 9.1 11
Cobertura de Arestas
• Uma cobertura de arestas de um grafo G = (V, A) é um subconjunto
A′ ⊂ A de k arestas tal que todo v ∈ V é parte de pelo menos uma
aresta de A′ .
• O conjunto resposta para k = 4 é A′ = {(0, 3), (2, 3), (4, 6), (1, 5)}.
0 1 • Uma cobertura de vértices é um sub-
conjunto V ′ ⊂ V tal que se (u, v) ∈ A
3 4 5 então u ∈ V ′ ou v ∈ V ′ , isto é, cada
aresta do grafo é incidente em um dos
vértices de V ′ .
2 6
Algoritmos Não-Deterministas
Função escolhe(C)
Máquina Não-Determinista
Pesquisa Não-Determinista
void PesquisaND(A, 1 , n)
{ j ← escolhe(A, 1 , n)
i f (A[ j ] == x ) sucesso ; else insucesso ;
}
Ordenação Não-Determinista
• Ordenar um conjunto A[1 : n] contendo n inteiros positivos, n ≥ 1.
Problema da Satisfabilidade
• Considere um conjunto de variáveis booleanas x1 , x2 , · · · , xn , que
podem assumir valores lógicos verdadeiro ou falso.
• A negação de xi é representada por xi .
• Expressão booleana: variáveis booleanas e operações ou (∨) e e (∧).
(também chamadas respectivamente de adição e multiplicação).
• Uma expressão booleana E contendo um produto de adições de
variáveis booleanas é dita estar na forma normal conjuntiva.
• Dada E na forma normal conjuntiva, com variáveis xi , 1 ≤ i ≤ n, existe
uma atribuição de valores verdadeiro ou falso às variáveis que torne E
verdadeira (“satisfaça”)?
• E1 = (x1 ∨ x2 ) ∧ (x1 ∨ x3 ∨ x2 ) ∧ (x3 ) é satisfatível (x1 = F , x2 = V ,
x3 = V ).
• A expressão E2 = x1 ∧ x1 não é satisfatível.
Projeto de Algoritmos – Cap.9 Problemas N P -Completo e Algoritmos Aproximados – Seção 9.1.1 19
Problema da Satisfabilidade
void AvalND(E, n) ;
{ for ( i = 1; i <= n ; i ++)
{ xi ← escolhe ( true , false ) ;
i f ( E(x1 , x2 , · · · , xn ) == true ) sucesso ; else insucesso ;
}
}
Projeto de Algoritmos – Cap.9 Problemas N P -Completo e Algoritmos Aproximados – Seção 9.1.1 20
Problema da Satisfabilidade
N P ⊃ P ou N P = P? - Conseqüências
Transformação Polinomial
• Sejam Π1 e Π2 dois problemas “sim/não”.
• Suponha que um algoritmo A2 resolva Π2 .
• Se for possível transformar Π1 em Π2 e a solução de Π2 em solução de
Π1 , então A2 pode ser utilizado para resolver Π1 .
• Se pudermos realizar as transformações nos dois sentidos em tempo
polinomial, então Π1 é polinomialmente transformável em Π2 .
Dados Dados Solução Solução
de 1 de 2 para 2 para 1
Transformação Algoritmo A 2
Transformação
Polinomial Polinomial
0 1
3 4 5
2 6
Projeto de Algoritmos – Cap.9 Problemas N P -Completo e Algoritmos Aproximados – Seção 9.1.2 26
Clique de um grafo
0 1
3 4 5
2 6
Projeto de Algoritmos – Cap.9 Problemas N P -Completo e Algoritmos Aproximados – Seção 9.1.2 28
Transformação Polinomial
Transformação Polinomial
Teorema de Cook
• Existe algum problema em N P tal que se ele for mostrado estar em P,
implicaria P = N P?
• Teorema de Cook: Satisfabilidade (SAT) está em P se e somente se
P = N P.
• Ou seja, se existisse um algoritmo polinomial determinista para
satisfabilidade, então todos os problemas em N P poderiam ser resolvidos
em tempo polinomial.
• A prova considera os dois sentidos:
1. SAT está em N P (basta apresentar um algoritmo não-determinista que
execute em tempo polinomial). Logo, se P = N P, então SAT está em P.
2. Se SAT está em P, então P = N P. A prova descreve como obter de
qualquer algoritmo polinomial não determinista de decisão A, com entrada
E, uma fórmula Q(A, E) de modo que Q é satisfatível se e somente se A
termina com sucesso para E. O comprimento e tempo para construir Q é
O(p3 (n) log(n)), onde n é o tamanho de E e p(n) é a complexidade de A.
Projeto de Algoritmos – Cap.9 Problemas N P -Completo e Algoritmos Aproximados – Seção 9.1.2 35
2 2
1 1
1 2 1 2
1 1
1 1
1 5 1 5 2
1 1
1 1
4 3 4 3
1 1
Classe N P-Intermediária
NP
NPC
NPI
P
Membros Potenciais de N PI
Problemas Exponenciais
• É desejável resolver instâncias grandes de problemas de otimização
em tempo razoável.
• Os melhores algoritmos para problemas N P-completo têm
comportamento de pior caso exponencial no tamanho da entrada.
• Para um algoritmo que execute em tempo proporcional a 2N , não é
garantido obter resposta para todos os problemas de tamanho
N ≥ 100.
• Independente da velocidade do computador, ninguém poderia esperar
por um algoritmo que leva 2100 passos para terminar sua tarefa.
• Um supercomputador poderia resolver um problema de tamanho
N = 50 em 1 hora, ou N = 51 em 2 horas, ou N = 59 em um ano.
• Nem um computador paralelo com um milhão de processadores, (cada
um sendo um milhão de vezes mais rápido que o mais rápido
existente) é suficiente para N = 100.
Projeto de Algoritmos – Cap.9 Problemas N P -Completo e Algoritmos Aproximados – Seção 9.2 43
• Para o grafo
0
2 6
1
1 3 2 1
5 1 2 6
2 4
4
2 1
4
Projeto de Algoritmos – Cap.9 Problemas N P -Completo e Algoritmos Aproximados – Seção 9.2.1 48
1 5 6
2 3 4 3 4 4
4 4 5 2 3 5 6 1 4 1 2 3 6 1 2 3 5
3 5 6 2 5 6 4 5 3 2 4 1 2 6 2 3 1 1 2 3 1 1 5 3
5 3 2 6 4 2 6 2 1 3 2 5 3 2 1
6 5 2
0 0
5 6
3 4 4
4 2 3 6 2 3 5
2 6 1 1 5 3
1 3 3
0
Projeto de Algoritmos – Cap.9 Problemas N P -Completo e Algoritmos Aproximados – Seção 9.2.1 51
• A ideia é cortar a pesquisa tão logo se saiba que não levará a uma
solução.
0 1 2 3 4 5
0 3 10 11 7 25
5 1
1 8 12 9 26
2 9 4 20
4 2 3 5 15
3 4 18
• Pode mesmo ser arbitrariamente ruim, uma vez que a aresta final pode
ser muito longa.
• Passos do algoritmo:
– Suponha uma AGM que tenha cidades do PCV como vértices.
– Dobre suas arestas para obter um grafo Euleriano.
– Encontre um caminho Euleriano para esse grafo.
– Converta-o em um caminho do caixeiro viajante usando
curto-circuitos.
(c) (d)
Projeto de Algoritmos – Cap.9 Problemas N P -Completo e Algoritmos Aproximados – Seção 9.2.3 74
M´
Ótimo PVC
1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1
AGM 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1
Ótimo 1
1 1 1 1