Pontifícia Universidade Católica do Paraná
Centro de Ciências Exatas e de Tecnologia
Curso de Engenharia de Computação
PA Projeto e Análise de Algoritmos
Segunda Avaliação
18 de Outubro de 2006
OBSERVAÇÕES IMPORTANTES
•
•
•
•
•
Leia com atenção o enunciado das questões e responda de maneira adequada.
Para serem consideradas, as respostas devem ser completas e legíveis.
Apresente sempre os passos intermediários e não somente a resposta.
A prova terá duração de três aulas (150 minutos) iniciando as 9:30 e terminando as 12:00.
É permitido consultar somente uma folha A4 com anotações. Estas anotações não podem conter exercícios resolvidos, somente teoria.
Não será permitido o empréstimo ou troca desta folha de anotações durante a prova.
QUESTÃO 1 [3,5 pontos] Considere o problema de buscar um padrão de m caracteres em um texto de n caracteres (string
matching). Dados:
•
•
•
Posição
1 2 3 ...
....25
Texto (n = 25): b c b c a b a b b c b c a a a a a b d c a a b a a
Padrão (n = 5): a a b a a
OBS: Não há espaçamento entre os caracteres do texto e entre os caracteres do padrão!
a) Construa a tabela de deslocamentos de Horspool (deslocamento pelo mau símbolo) [0,5]
b) Construa a tabela de deslocamento pelos bons sufixos para o padrão [0,5]
c) Aplique o algoritmo de Horspool até encontrar o padrão no texto e forneça [1,0]:
c1) posições onde o padrão é alinhado com o texto (posição onde o final do padrão é alinhado com o texto);
c2) número de comparações bem sucedidas (BS) e mal sucedidas (MS) em cada posição de alinhamento;
c3) número total de comparações realizadas até encontrar o padrão.
d) Aplique o algoritmo de Boyer-Moore para localizar o padrão no texto e forneça [1,5]:
d1) posições onde o padrão é alinhado com o texto (posição onde o final do padrão é alinhado com o texto);
d2) número de comparações bem sucedidas (BS) e mal sucedidas (MS) em cada posição de alinhamento;
d3) número total de comparações realizadas até encontrar o padrão.
QUESTÃO 2 [ 4 pontos] Considere o problema de encontrar os dois pontos mais próximos em um conjunto de n pontos em
um espaço 2-dimensional. A distância entre dois pontos Pi=(xi,yi) e Pj=(xj,yj) pode ser calculada utilizando a distância
Euclideana, que é definida como:
d (Pi , P j ) = ( xi − x j )2 + ( y i − y j )2
Dado um espaço 2D e um conjunto de 8 pontos:
10
9
8
b) Proponha um algoritmo não recursivo baseado na estratégia dividir e
conquistar para encontrar os dois pontos mais próximos dois [1,75]
c) Quantas medidas de distância são necessárias fazer para encontrar os dois
pontos mais próximos utilizando o algoritmo força-bruta proposto em a)? [0,5]
Eixo Y
a) Proponha um algoritmo não recursivo baseado na estratégia força-bruta
para encontrar os dois pontos mais próximos. Descreva os passos de seu
algoritmo. [1,25]
7
6
5
4
3
2
1
0
d) Quantas medidas de distância são necessárias fazer para encontrar os dois
pontos mais próximos utilizando o algoritmo dividir e conquistar proposto em
b)? [0,5]
0
1
2
3
4
5
6
7
8
9 10
Eixo X
QUESTÃO 3 [2,5 pontos] Dado o grafo não direcionado da figura abaixo:
a) Represente o grafo através de uma lista de adjacências ou matriz
de adjacências [0,5].
b) Escolha um algoritmo de busca que empregue a estratégia
decrementar e conquistar e explique como ele funciona [0,75].
a
c
e
g
b
d
f
h
c) Qual a estrutura de dados utilizada para implementar o algoritmo
escolhido no item b? [0,25].
d) Percorra este grafo (visitando todos os vértices) começando pelo
vértice “a” usando o algoritmo escolhido no item b e forneça a ordem
em que os vértices do grafo são visitados pelo algoritmo [1,0].
i