Algoritmos de varredura linear e
busca de padrões
Davi Duarte, Luiz Afonso
{ddp, lacbs}@cin.ufpe.br
A importância do estudo de algoritmos
• O que é algoritmo?
• Porque aprender algoritmos?
– Capacidade de generalização
– Aplicação a problemas reais
– Estimativa de tempo de execução
Análise de tempo de execução
• Tempo aproximado para algoritmos com N=100
Complexidade Tempo esperado
O(log(N))
10-7 segundos
O(N)
10-6 segundos
O(N.log2(N))
10-5 segundos
O(N2 )
10-4 segundos
O(N6)
3 minutos
O(2N)
1014 anos
O(N!)
10142 anos
Varredura Linear
– Utilizado para resolver problemas geométricos
– Linha conceitual “varre” o plano verticalmente
– Pode ser utilizada em conjunto com outros
algoritmos
– Particularmente útil em problemas envolvendo
distância Euclidiana e de Manhattan
Distância de Manhattan
– A distância de Manhattan entre os pontos (x1,y1)
e (x2,y2) é dada por |x1 – x2| + |y1 – y2|
– É chamada distância de Manhattan por conta das
ruas em forma de grade da cidade de Manhattan
– Formalmente conhecida como métrica L1
Par de pontos mais próximos
– Dado um conjunto de pontos encontrar o par de
pontos mais próximo
– Ordenar os pontos pelo eixo X e varrer com uma
linha vertical
– Utilizar árvores binárias balanceadas
para guardar os pontos mais
próximos
– Complexidade O(N Log N)
Interseção de segmentos de reta
– Encontrar interseção de segmentos de retas
verticais e horizontais
– Utilizar linha de varredura para percorrer o plano
horizontalmente
– Percorrer passando pelos pontos
extremos dos segmentos
– Usar árvore binária balanceada
para armazenar retas intersectantes em um ponto de varredura
– Complexidade O(N log N)
Área de união de retângulos
– Calcular a área da união de vários retângulos
– Utilizar linha de varredura para percorrer o plano
horizontalmente
– Percorrer passando pelas arestas
dos retângulos
– Utilizar árvore binária balanceada
para armazenar número de retângulos em um ponto de varredura
– Complexidade O(N log N)
Fecho convexo de pontos 2D
– Encontrar menor polígono que cerca um conjunto
de pontos no plano 2D
– Ordenar os pontos pelo eixo X
– Utilizar duas linhas de varredura percorrendo
verticalmente o plano
– Gerar fecho superior e inferior
– Procedimento similar ao Graham
scan para tratamento de triângulos
– Complexidade O(N log N)
Árvore de peso mínimo no espaço de
Manhattan
– Encontrar a árvore geradora mínima em um conjunto
de pontos considerando a distância de Manhattan
– Dividir o plano em octantes
– Ordenar os pontos pela soma
das coordenadas
– Dividir o octante em metades e usar
abordagem dividir para conquistar
– Problema reduzido a encontrar o
vizinho mais próximo em um octante
– Complexidade O (N log N)
Busca de padrões
– DNA
– Banco de Dados
– Indexação
Busca de padrões
– Algoritmo ingênuo
•
•
•
•
•
•
•
•
•
•
•
ABABABABAABABAA
ABABAA ?
_ABABAA ?
__ABABAA ?
___ABABAA ?
____ABABAA !
_____ABABAA ?
______ABABAA ?
_______ABABAA ?
________ABABAA ?
_________ABABAA !
– O(N*M)
Busca de padrões
– Knuth-Morris-Pratt
•
•
•
•
ABABABABAABABAA
ABABAA ?
____ABABAA !
_________ABABAA !
– O(M+N)
Busca de padrões
– Trie
• CERCARROCORAL
–
–
–
–
–
"A",
"CARRO",
"CERCA",
“COR”,
"CORAL“
ϵ
C
A
C
A
C
E
C
O
CA
R
CE
R
CO
R
CAR
R
CER
C
COR
A
CARR
O
CERC
A
CORA
L
Busca de padrões
– Aho-Corasick
• CERCARROCORAL
–
–
–
–
–
"A",
"CARRO",
"CERCA",
“COR”,
"CORAL“
ϵ
C
A
CA
CE
CO
CAR
CER
COR
CARR
CERC
CORA
CARRO
CERCA
CORAL
Busca de padrões
– Árvove de sufixos
– Hashing
• Texto
• Polinômio limitado
• Número
Dúvidas?