TRABALHO 2 – ORDENAÇÃO
A envoltória convexa de um conjunto Q de pontos de pontos, denotada por CH(Q), é o
menor polígono convexo P para o qual cada ponto em Q está no contorno de P ou em seu interior.
Figura: Envoltória Convexa
O algoritmo para calcular a CH de um conjunto de pontos é muito simples e depende
basicamente de uma ordenação particular destes pontos. A tarefa da equipe é determinar quais
algoritmos de ordenação, incluindo diferentes variantes, é mais adequado para diversos conjuntos
de pontos.
Envoltória Convexa
Uma breve explicação sobre um dos algoritmos (Graham Scan) para o cálculo da envoltória
convexa pode (deve) ser vista no YouTube:
https://youtu.be/0HZaRu5IupM
Outros materiais são facilmente encontrados usando as palavras-chave: convex hull,
computational geometry, graham scan.
Algoritmos de Ordenacao
Os algoritmos de ordenação a serem implementados são o quicksort, o mergesort e o
insertion sort.
O quicksort é um algoritmo, na prática, O(nlogn). Porém, seu desempenho, em pior caso, é
2
O(n ). Na literatura são descritas providências que minimizam grandemente a probabilidade de
ocorrer o pior caso, entre elas, o embaralhamento (shuffling) e a mediana de 3. Para tentar otimizar
o tempo de execução (mas, não o comportamento assintótico), pode-se substituir a recursão do
algoritmo por uma pilha. Espera-se que a equipe, portanto, faça 4 implementações do algoritmo
quicksort: (a) implementação básica, cujo o pivô é o primeiro elemento do vetor; (b) com
embaralhamento; (c) escolha do pivô determinado pela mediana de 3; (d) eliminação da recursão.
O mergesort é um algoritmo O(nlogn), porém, quando o subvetor a ser ordenado for
pequeno, pode ser que valha a pena usar o insertion sort para ordená-lo. Portanto, espera-se que a
equipe faça duas implementações: (a) a implementação padrão e (b) com utilização do insertion sort
para ordenar pequenos subvetores.
As implementações devem contar: (a) o número de comparações; (b) número de trocas; (c)
tempo de execução, a fim de que possam ser produzidos gráficos comparativos entre as diversas
implementações e diversos cenários de execução.
A Entrada
A entrada do algoritmo será basicamente um conjunto de pontos (em coordenadas
cartesianas). As coordenadas serão sempre valores inteiros e estarão contidas dentro da região
delimitada pelo retângulo (0,0), (xmax,ymax).
Figura: Retângulo que contém os pontos
O arquivo de entrada consistirá de uma sequência de pontos: um ponto por linha. Na primeira linha
serão colocados três números inteiros: o número de pontos no arquivo, xmax e ymax.
12 310 260
220 10
300 210
170 250
60 234
220 60
200 80
280 190
130 200
180 230
200 120
215 150
225 180
a001.pts
A Saída
O programa deverá produzir um arquivo .svg mostrando todos os pontos do arquivo de
entrada e a envoltória convexa. Existem várias ferramentas que renderizam arquivos .svg.
A figura abaixo mostra um exemplo de arquivo svg e sua respectiva renderização.
Figura: Arquivo .svg (fonte e renderizado)
O Programa
O nome do programa deve ser ch e aceitar dois parâmetros:
ch -f arq.pts -o dir
O primeiro parâmetro (-f ) especifica o nome de um arquivo de pontos e o segundo parâmetro (-o)
indica o diretório onde o arquivo de saída (arq.svg) deve ser colocado. Os eventuais arquivos
com os dados sobre execução do programa devem ser colocados no diretório dir/dat.
A Avaliação
Espera-se uma atitude pró-ativa para a aquisição dos conhecimentos (i.e., estudo) para
resolver o problema proposto. O principal problema a ser resolvido é determinar o melhor método
de ordenação para o cálculo da envoltória convexa de um conjunto de pontos. Outros problemas
menores também deverão ser resolvidos, entre eles: como implementar as diversas variações dos
algoritmos de ordenação, como medir e comparar o desempenho de cada um das variações;
determinar se alguma variante de ordenação é mais adequada para algum padrão de dados de
entrada.
A avaliação se baseará em três critérios: (a) avaliação de um artigo escrito pela equipe ; (b)
compilação e testes do executável (a equipe deve entregar os fontes); (c) apresentação do artigo
(max 30 minutos). Note que apenas algumas equipes apresentarão o trabalho (sorteio). Também
será sorteado qual membro da equipe fará a apresentação (ambos membros devem estar preparados
para fazer integralmente a apresentação).
O Que Entregar
Submeter a sala Moodle três arquivos:
•
nome1-nome2.zip: com os fontes do programa um makefile. Este makefile deve ter (pelo
menos) o target ch que deve produzir o arquivo executável.
•
nome1-nome2.pdf: artigo científico de 8 a 10 páginas descrevendo o problema, a solução
que a equipe adotou e as conclusões da equipe. Alguns destes artigos poderão ser
submetidos à Revista Eletrônica de Iniciação Científica da SBC (http://seer.ufrgs.br/reic).
Caso o artigo seja aceito pela revista antes do fechamento das notas da disciplina, os
membros da equipe obterão algum bônus em suas médias finais.
•
slides da apresentação: preferencialmente .pdf. Também são aceitos em .odp e .ppt.
Note que nome1-nome2 é alguma abreviatura do nome de cada um dos membros da equipe.
A abreviatura só deve conter letras (por exemplo, jlsilva-acoliveira, poderia se referir aos
alunos José Luís da Silva e Antônio Carlos Oliveira).