1. 

Seja =

Utilizando o Método da Perturbação [Knuth et al 95]:

+

+

+

+

+

+

-



para

=

para

  

2. 

Sendo a série harmônica acima uma função monotônicamente decrescente, podemos utilizar a técnica de aproximação por integrais para determinar seu limite inferior e superior, conforme demonstrado em [Cormen et al. 91], dada por:



Aplicando esta aproximação, temos:

Limite Inferior:





Limite Superior:







Logo,



Podemos então afirmar que:



 

 

 

3. 

Seja =







Utilizando a Aproximação de Stirling [Cormen et al. 91], dada por:



Podemos afirmar que: , para

Portanto

 

4. 

PROCEDURE FazAlgo ( n : integer);

Seja uma função de complexidade de custo que representa o total de operações de incremento de x. Podemos observar que existem três anéis com intervalos interdependentes, sendo o mais interno com custo para cada evento, e os demais dados em função do mais interno, portanto a função de complexidade de custo para este procedimento é dada por:

sendo [Ziviani 93]

sendo [Knuth 95]

Seja uma função de complexidade de custo que representa o número de inspeções nos elementos de um conjunto com elementos. Podemos observar que cada chamada recursiva da função Pesquisa( ) tem custo dado por , e a função Inspecione( ) tem custo do número de inspeções, portanto a equação de recorrência para este procedimento é dada por:

, ou seja, não faz inspeção.

Utilizando o método da Interação [Ziviani 93]

Adicionando ambos os lados e eliminado os termos comuns da equação:

Sendo: - uma potência de 3 ()

-

- [Knuth et al 95]

Temos:

sendo (),

Seja uma função de complexidade de custo que representa o número de comparações nos elementos de um conjunto com elementos. Podemos observar que cada chamada recursiva da função Sort( ) tem custo dado por . A função Merge( ) tem custo do número de comparações para intercalar ordenado, portanto a equação de recorrência para este procedimento é dada por:

, ou seja, não faz comparação.

Utilizando o método da Interação [Ziviani 93]

Adicionando ambos os lados e eliminado os termos comuns da equação:

Sendo: - uma potência de 2 ()

-

- [Knuth et al 95]

Temos:

Seja uma função de complexidade de custo que representa o número de operações de soma em um conjunto com elementos. Podemos observar a função Proc( ) tem custo para , e cada chamada recursiva tem custo dado por , portanto a equação de recorrência para este procedimento é dada por:

, ou seja, não faz operação de soma.

Utilizando o método da Interação [Ziviani 93]

Adicionando ambos os lados e eliminado os termos comuns da equação:

Sendo: - o número de iterações ()

-

- [Knuth et al 95]

Temos:

São dados 2n números distintos distribuídos em dois arranjos A e B, cada um com n elementos ordenados, tal que: e .O problema é achar o n-ésimo maior número dentre estes 2n elementos.

1. Apresente um algoritmo ótimo para resolver esse problema. Implemente o seu algoritmo. A listagem da implementação deve ser entregue e o programa submetido.
2. Prove que o seu algoritmo é ótimo, isto é, obtenha um limite inferior para o número de comparações para resolver esta classe de problemas.

3.1 Introdução

Problemas envolvendo a busca de elementos em um arranjo são comuns e de grande utilidade na área de processamento de dados e recuperação de informação, principalmente quando faz-se necessário que esta busca ocorra em um menor tempo possível. Existem diversas instâncias deste problemas, e vários algoritmos que permitem sua solução. Nesta seção iremos apresentar um algoritmo para a solução de um problema em particular, objetivando desenvolver e implementar um algoritmo que se encontre dentro do limite inferior para esta classe de problemas, gerando resultados consistentes que comprovem sua eficácia.

3.2 Especificação do Problema

Dados 2n números distintos distribuídos em dois arranjos A e B, cada um com n elementos ordenados, tal que: e .O problema consiste em determinar o n-ésimo maior número dentre estes 2n elementos, utilizando um algoritmo ótimo.

3.3 Algoritmo Nmax

O algoritmo consiste em dividir os dois vetores ao meio, caso n seja potência de 2, ou ao meio menos um, caso contrário, descartando as duas metades onde, sabidamente, não se encontre o n-ésimo maior elemento desejado. Isto pode ser feito comparando os elementos médios dos dois vetores e analisando quais os elementos que não atingem os critérios do alvo procurado, como pode ser visto no exemplo abaixo:

Sejam A[4] e B[4] abaixo:

i j

O 4º maior elemento tem que ser no maior do que 4 e menor do que 3 elementos, e se a₂ > b₂ , teremos que:

• a₁ e a₂ são, no mínimo, maiores que 5 elementos
• b₃ e b₄ são, no mínimo, menores que 4 elementos

Eliminando estes elementos temos:

i j

Possuímos agora 4 elementos, 2 que são os 3º e 4º maiores e dois que são os 3º e 4º menores, o elemento alvo é, portanto, menor do 1 e maior do 2 elementos, e se a₃ > b₁ , teremos que:

• a₃ é, no mínimo, maior que 3 elementos
• b₂ é, no mínimo, menor que 3 elementos

Eliminando estes elementos temos:

i j

E nesta situação, por comparação simples, o elemento procurado será o maior entre a₄ > b₁

No caso do número de elementos não ser potência de 2, uma pequena alteração deve ser adicionada, eliminando a mesma quantidade de elementos nos dois vetores. Abaixo o algoritmo na linguagem C:

3.4 Análise de Complexidade

Seja uma função de complexidade de custo que representa o número de comparações entre os elementos de dois conjuntos com 2 elementos. Podemos observar que a função Nmax( ) tem custo dado por , e a cada chamada recursiva a função Nmax( ) tem custo dado por , portanto a equação de recorrência para este procedimento é dada por:

, ou seja, não faz comparação.

Utilizando o método da Interação [Ziviani 93]

Adicionando ambos os lados e eliminado os termos comuns da equação:

Sendo: - uma potência de 2 ()

-

Temos:

3.5 Limite Inferior desta Classe de Problemas

Teorema 1: Qualquer árvore de decisão que busca o n-ésimo maior elemento entre 2n números distintos distribuídos em dois arranjos A e B, cada um com n elementos ordenados, tal que: e , possui altura no caso ótimo.

Prova: Considere uma árvore de decisão de altura h que busca o n-ésimo maior elemento entre 2n números distintos, distribuídos em dois arranjos A e B, cada um com n=4 elementos ordenados, tal que: e , utilizando o algoritmo proposto na seção 3.3.

Desde que existam respostas possíveis para encontrar o n-ésimo maior elemento, uma vez que cada um dos 2n elementos pode ser o elemento procurado, qualquer algoritmo utilizado para esta classe de problemas terá, no caso mínimo, a árvore acima que representa a quantidade de comparações entre elementos dos dois arranjos e , que deverá possuir, no mínimo, folhas. Desde que uma árvore binária de altura h não possui mais do folhas, temos então que, para qualquer algoritmo que busque implementar esta solução:

, isto implica que:

é o limite inferior para esta classe de problemas

Corolário: O algoritmo Nmax proposto na seção 3.3 é assintóticamente ótimo para esta classe de problemas.

Prova: O algoritmo Nmax possui complexidade de custo de , conforme demonstrado na seção 3.4, que está dentro do limite inferior para a solução desta classe de problemas, apresentado no Teorema 1.

3.6 Implementação do Algoritmo Nmax

O algoritmo foi implementado em linguagem C, no compilador gcc, utilizando uma plataforma Sun Ultra 5 em ambiente Solaris. Possui os seguintes arquivos: o principal, um módulo contendo as funções e um de cabeçalho. Como forma de tornar a análise da complexidade de custo mais transparente foi implementado utilizando recursão, o que aumenta a complexidade de espaço, que entretanto não é fator relevante neste estudo.

Para utilizá-lo basta digitar o comando executável, pois o mesmo irá gerar os dois arranjos de acordo com o problema que está sendo tratado, obtendo como saída os arranjos e sub-arranjos após cada divisão, e ao final o n-ésimo maior elemento. As principais funções do programa são:

Função GeraVetores: Gera dois vetores de tamanho n, em ordem decrescente, utilizando 2n números distintos. para garantir a distinção entre eles, um vetor será formado por números pares e outro por números ímpares, a partir de números aleatórios gerados pela função rand().

Função Nmax: Consiste em dividir os vetores ao meio (metade -1) e eliminar aqueles elementos que não possuem o n-ésimo maior elemento, comparando A[i] com B[j] e eliminando o maior entre as duas chaves e todos os maiores que ele (do mesmo vetor) e os menores que a menor chave (do mesmo vetor), sendo que em um caso particular (n ímpar), serão eliminados m-1 menores. A função é chamada recursivamente e a condição de parada é quando restar um único elemento em cada vetor, sendo que o maior entre eles será o n-ésimo maior elemento.

As demais funções podem ser encontradas no código do programa, conforme Anexo I.

3.7 Resultados Obtidos

Os testes foram efetuados considerando a geração aleatória de 2n elementos, para n=1, n=2, n=3, n=4, n=5, n=6, n=7, n=8, n=9 e n=10, sendo a busca alcançada com sucesso em todos os casos.. Segue abaixo um dos resultados obtidos, os demais poderão ser vistos no Anexo II.

Resultado impresso pelo programa para n = 8 :

3.8 Conclusão

O problema apresentado possui mais de um tipo de algoritmo que implementa sua solução, entretanto nem todos estão na ordem de complexidade do limite inferior para esta classe de problemas.

O algoritmo Nmax apresenta uma solução que se encontra dentro do limite inferior, possuindo complexidade de O(log₂(n)) , conforme demonstrado no item 3.4 . A versão recursiva do algoritmo facilita o seu entendimento em termos de complexidade de custo, entretanto, devido ao empilhamento em cada chamada recursiva, aumenta a complexidade de espaço, o que nos leva a concluir que a versão não recursiva de Nmax é uma opção mais vantajosa para a solução do problema apresentado.

Os experimentos realizados garantem a eficiência do algoritmo, uma vez que houve 100% de acerto em todos os experimentos realizados, conforme pode ser visto no Anexo II.

 4ª Questão - Árvore Binária de Pesquisa Sem Balanceamento (1 + 0,5 + 0,5 + 1 pontos)

Considere o algoritmo para pesquisar e inserir registros em uma árvore binária de pesquisa sem balanceamento. Devido à sua simplicidade e eficiência a árvore binária de pesquisa é considerada uma estrutura de dados muito útil. Considerando-se que a altura da árvore corresponde ao tamanho da pilha necessária para pesquisar na árvore é importante conhecer o seu valor. Assim sendo,

1. Determine empiricamente a altura esperada da árvore;

• Implementação de um programa de geração de uma árvore binária randômica não balanceada, tomando como base o código em C disponível em [Ziviani 93], implementado em linguagem e compilado no gcc.
• Desenvolvimento de uma função para geração automática de 50 permutações de n elementos, utilizadas para o cálculo da altura média da árvore.
• Desenvolvimento de uma função para busca da altura da árvore, utilizando busca em profundidade.
• Geração de resultados para 20 valores de n, sendo este uma potência de base 2.
• Experimentos executadas na plataforma Sun Ultra Sparc 5, em ambiente Solaris.

É possível observar através do gráfico que o valor de k aumenta à medida que aumenta também o tamanho da entrada n . Sendo o desvio padrão obtido nos 10 primeiros valores de k igual a 0.25, e o desvio padrão obtido nos 10 últimos valores e de k igual a 0.13, é possível afirmar que k tende a um valor constante quando n tende a infinito, ou seja, para entradas com n muito grande, a altura da árvore pode ser dada por h º klog₂(n), sendo k > 2.55. Estudos empíricos e matemáticos mais aprofundados são disponíveis na literatura, estabelecendo um valor de k com maior precisão. Iremos discutir sobre o valor de k encontrado neste experimento e o valor descrito na literatura no item c) desta questão.

1. Mostre analiticamente o melhor caso e o pior caso para a altura da árvore;

O melhor caso será aquele em que a árvore binária for balanceada, conforme abaixo:

Nível 1 - 2⁰ elementos

Nível 2 - 2¹ elementos

Nível 3 - 2² elementos

Nível n - 2^h elementos

 

Sendo h a altura da árvore e n o número de elementos dado por:

 

Sendo

[Knuth et al 95]











 

O pior caso será aquele em que a entrada n for uma seqüência de valores crescentes ou decrescentes, resultando em que todos os elementos sejam inseridos somente à esquerda ou somente à direita da árvore. Isto faz com que cada nó pai tenha um único nó filho, e que a árvore possua um único caminho entre o nó raiz e o nó folha, dado por n-1 elementos, que é exatamente a altura da árvore, portanto:





 

2. Compare os resultados obtidos no item (a) com resultados analíticos publicados na literatura.

A altura esperada de uma árvore binária não balanceada, construída a partir de permutações randômicas, como no caso da árvore implementada no item a), é dada por:



sendo A = 4.311 [Knessl and Szpankowski 00]

Calculando-se a altura da árvore utilizando-se a expressão acima, e apresentando a quantidade de elementos n e a altura empírica da árvore obtida no item a), obtemos o quadro e o gráfico abaixo:

n	21	22	23	24	25	26	27	28	29	210	211	212	213	214	215	216	217	218	219	220
h	1	3	5	7	9	11	14	16	19	22	24	27	30	32	36	39	41	44	47	51
H	4	5	8	10	13	15	18	21	24	26	29	32	35	38	41	43	46	49	52	55



Como pode ser visto, os resultados empíricos obtidos são consistentes, quando comparados com os resultados analíticos, ainda que para valores de n não muito grandes. Para valores de n muito grande, temos que:





A constante k encontrada empiricamente no item a) foi de 2.55 para n = 2²⁰, e cuja tendência de crescimento, observada pelo declínio do desvio padrão entre as amostras, nos leva a considerar que este valor ficaria próximo do valor analítico citado na literatura [Knessl and Szpankowski 00].

 

3. Mostre analiticamente o número esperado de comparações para encontrar um registro existente na árvore (busca com sucesso).

Seja:

1. 
2. 

Multiplicando (2) por ((n-1)/2)² obtemos

3. 

E substituindo (3) em (1)

Aplicando-se a forma de Euler (usando a constante de Euler g » 0.577)

deriva-se, para valores grandes de n, a relação

Sendo o comprimento médio da trajetória em árvores banceadas aproximadamente igual a

E ignorando-se os termos constantes por serem desprezíveis quando n é muito grande:

Conforme valor citado em [Ziviani 93]

 [Cormen et al 91] Cormen, T.H.; Leirson, C.E.; Rivest, R. L.; Introduction to Algorithms, McGraw-Hill,1991.

[Knessl and Szpankowski 00] Knessel, C; Szpankowski, W; The Height of a Binary Search Tree: The limit Distribution Perspective , 55pp. manuscrito em submissão.

[Knuth et al 95] Knuth, Donald E.; Graham, Ronald L.; Patashnik, Oren; Matematica Concreta , Livros Técnicos e Científicos, 1995.

[Wirth 76] Wirth, N; Algorithms + Data Structures = Programs , Prentice Hall, 1976

[Ziviani 93] Ziviani, Nívio; Projetos de Algoritmos Com Implementações em Pascal e C, Editora Pioneira, 1993.

Knuth, D.E.; The Art of Computer Programming, volume 1. Addison-Wesley, Reading, MA, 1973.

Lueker, George S.; Some Techniques to Solve Recurrences, Computing Survey, Vol. 2, Nº4, December, 1980.

Manber,Udi; Introduction to Algorithms A Creative Approach, Addison-Wesley, 1989.

Miyazawa, Flavio Keidi; Notas de Aula de Complexidade de Algoritmos, Apostila do Instituto de Computação, UNICAMP.

if(A[i]>B[j]) // Mantém os menores que A[i] e os maiores e igual a B[j]

}else { // Mantém os menores+1 que A[i] e os maiores e igual a B[j]

q2=j+1; // Caso particular em que o tamanho do vetor é impar

else // Mantem os menores que B[j] e os maiores e igual a A[i]

}else { // Mantem os menores+1 que B[j] e os maiores e igual a A[i]

q1=i+1; // Caso particular em que o tamanho do vetor é impar