Trabalho 2 de AA
Prof. Eduardo Laber
1
Objetivo
Dados n pontos no plano, estamos interessados em encontrar o par de pontos
mais próximo. O objetivo é implementar e testar o desempenho de dois
algoritmos para este problema: um algoritmo que utiliza busca exaustiva e
o outro baseado em divisão e conquista.
Data de entrega: 17 de Junho de 2015
Grupos: O trabalho deve ser feito em duplas. Caso não tenha encontrado
uma dupla, entre em contato com o professor.
2
Definição do trabalho
O trabalho consiste de 4 tarefas descritas a seguir:
2.1
Tarefa 1
Implemente o algoritmo de força bruta e o algoritmo baseado em divisão e
conquista para este problema.
1
2.2
Tarefa 2.
Gere 120 instâncias conforme o seguinte procedimento
k←0
Para i = 1, . . . , 12
Para j = 1, . . . , 10
k++
Instância k ← 25 × 2i pontos sorteados aleatoriamente dentro
do conjunto {(x, y)|0 ≤ x ≤ 1 e 0 ≤ y ≤ 1}.
Fim Para
Fim Para
Para o sorteio utilize uma função de geração de números aleatórios.
2.3
Tarefa 3
A terceira tarefa consiste em executar os algoritmos implementados para
cada uma das 120 instâncias geradas. Para cada instância/algoritmo marque
o tempo de execução e a distância entre o par de pontos mais próximos.
Coloque um tempo limite de 3 minutos por instância.
Existe alguma relação entre o número de pontos sorteados e a distância
entre o par de pontos mais próximo? Discuta.
2.4
Tarefa 4
Escreva um relatório descrevendo o trabalho realizado. Discuta os seguintes
aspectos:
• Ambiente experimental: máquina, linguagem, etc.
• Algoritmos e estruturas de dados utilizados. Explique eventuais otimizações que tenham sido feitas.
• Resultados obtidos e tempo de execução dos experimentos. Confronte
os resultados experimentais com a análise teórica dos algoritmos.
2