Lista 11 de Cana

Construção e Análise de Algoritmos, teste 11

Análise do algoritmo Heap-Sort

A informação sobre a ordem relativa dos elementos de um conjunto X pode ser representada na forma de um conujunto de pares ordenadeos P, que correspodem à relação “<“. Ou seja, se <aj,ak> está em P, então aj < ak.

Um conjunto de pares ordenados P é dito uma ordem parcial se:

1. <a_j,a_k> está em P → <ak,aj> não está em P.
2. <aj,ak> e <ak,am> estão em P →<aj,am> está em P.

Uma ordem total é simplesmente uma ordem parcial com tamanho máximo, e portanto corresponde a uma ordenação completa de X. É facil ver que, se é uma ordem total, então |P| = n(n-1)/2.

Desta forma, podemos dizer que o objetivo de um algoritmo de ordenação é construir uma ordem total para os elementos de uma lista A = {a1,a2, …, an}.

Se o algoritmo de ordenação é baseado em comparações, então ele constroi a ordem total a partir de perguntas do tipo “aj < ak?”. Caso positivo, o par <aj,ak> é colocado em P, juntamente com todos os outros pares que podem ser obtidos por transitividade.

Ou seja, o algoritmo inicia com o conjunto P vazio, e a cada passo, acrecenta novos pares ordenados a P, até que |P|=n(n-1)/2.

Podemos estudar a eficiência de um algoritmo de ordenação imaginando a sua execução como um jogo entre o algoritmo e um possível adversário.

Uma rodada do jogo se inicia com o algoritmo escolhendo um par de elementos de aj e ak, e é o adversário quem decide se o resultado da comparação é verdadeiro ou falso. O objetivo do adversário é escolher os resultados das comparações de modo que o tempo de execução do algoritmo seja o maior possível.

Exemplo: A = {a1,a2,a3,a4}:

Algortimo	Adversário	P
a1 < a2 ?	Sim	{<a1,a2>}
a3 < a4 ?	Sim	{<a1,a2>;<a3,a4>}
a2 < a3 ?	Não	{<a1,a2>;<a3,a4>;<a3,a2>}
a2 < a4 ?	Não	{<a1,a2>;<a3,a4>;<a3,a2>;<a4,a2>}
a1 < a3 ?	Não	{<a1,a2>;<a3,a4>;<a3,a2>;<a4,a2>;<a1,a3>;<a1,a4>}

a) Mostre que no exemplo acinema o adversário não joga da melhor maneira possível. Ou seja, se o adversário respondesse uma (ou mais) perguntas do algoritmo de maneira diferente, então o algoritmo seria forçado a realizar uma pergunta a mais para completar a ordem total P.

b) Por outro lado, mostre que se o algoritmo escolhesse suas perguntas de maneira mais cuidadosa, ele poderia completar a ordem total P com apenas 5 perguntas (independentemente das respostas do adversário).

c) Suponha para este item que, apos a primeira pergunt, e enquanto for possível, o algoritmo seleciona a cada passo um elemento que já foi comparado e um elemento novo para a próxima comparação. Mostre que, se este for o caso, então existe uma estratégia para o adversário tal que, após n-1 comparações o conjunto P possúi apenas n-1 pares ordenados. (Ou seja, em nenhum momento o algoritmo inclui um par em P por transitividade.)

Dica: Análise a situação utilizando um grafo direcionado.

d) Proponha uma estratégia mais eficiênte para as primeiras n-1 comparações do algoritmo.

e) Estime o tamnho de P após as n-1 comparações da sua estratégia.

Algortimo Heap-Sort

A idéia do algortimo Heap-Sort consiste em utilizar suas comparações iniciais para construir uma estrutura de heap dentro do conjunto P. Uma vez que esta estrutura esteja montada, a cada comparação adicional o algoritmo pode construir um grande numero de pares por transitividade no conjunto P (independentemente da resposta fornecida pelo adversário). Isto faz com que ele possa completar a ordem total de maneira eficiênte.

f) Apresente uma estratégia para o algoritmo que o permita construir a estrutura de heap dentro do conjunto P utilizando O(n) comparações.

h) Utilize o resultado do item(g) para provar que o algoritmo Heap-Sort executa em tempo O(nlogn).

g) Mostr que se P contém uma estrutura de Heap com K elementos, então o algoritmo pode incluir theta(k) pares ordenados comparaçãoes, e além disso, após este procedimento, P contém uma estrutura de Heap com k-1 elementos.