Período: 2006.1
25 de abril de 2006
Horário: 2as-feiras e 4as-feiras de 19 às 21 horas
ANÁLISE DE ALGORITMOS (INF 1309)

1o Trabalho de Implementação (T1)

Data de Entrega: 19 de maio

Descrição

Este trabalho prático consiste em desenvolver para os algoritmos para a resolução de problemas sobre conjuntos e vetores contendo números inteiros positivos.

  1. Sejam S1 e S2 conjuntos cujos elementos são números inteiros e onde |S1|+|S2|=n. Dado um inteiro x, propor um algoritmo para determinar se existem e1 Î S1 e e2 Î S2 tais que e1 + e2 = x.
    1. Proponha e implemente um algoritmo de complexidade Q (n2) e apresente a análise que permite concluir esta complexidade.
    2. Proponha e implemente um algoritmo de complexidade O(n log n) e apresente a análise que permite concluir esta complexidade.
    3. Suponha agora que S1 e S2 estejam ordenados. Proponha e implemente um algoritmo de complexidade O(n) e apresente a análise que permite concluir esta complexidade.

    4. Execute os algoritmos implementados sobre conjuntos S1 e S2 de tamanho total 1000, 2000, 5000, 10000, 20000, 50000 e 10000. Apresente os tempos de CPU para cada execução de cada algoritmo, organize numa tabela.

    5. Analise os resultados experimentais obtidos e compare com as complexidades teóricas.

  2. Sejam S1 e S2 conjuntos cujos elementos são números inteiros e onde |S1|=|S2|=n.
    1. Apresente e implemente um algoritmo de complexidade Q (n2) para determinar a união de S1 e S2. Nenhum elemento deve aparecer mais de uma vez.

    2. Apresente e implemente um algoritmo que execute em O(n log n).

    3. Execute os algoritmos implementados sobre conjuntos S1 e S2 de tamanho 1000, 2000, 5000, 10000, 20000, 50000 e 10000. Apresente os tempos de CPU para cada execução.

    4. Analise os resultados experimentais obtidos e compare com as complexidades teóricas.

  3. Busca em Vetores Ordenados

    1. Escreva um algoritmo de "busca ternária" que primeiro testa se o elemento da posição n/3 é igual ao elemento procurado x e então, se necessário, testa o elemento da posição 2n/3 para verificar a igualdade com o elemento x e, possivelmente, reduzir o tamanho do conjunto para um terço do original.

    2. Implemente um algoritmo de Busca Binária.

    3. Execute os algoritmos implementados sobre vetores de tamanho 1000, 2000, 5000, 10000, 20000, 50000 e 10000. Apresente os tempos de CPU para cada execução. Apresente também o número de comparações e recursões realizadas em cada execução.
    4. Analise os resultados experimentais obtidos e compare com as complexidades teóricas.

Os algoritmos acima devem ser desenvolvidos e seu desempenho experimental deve ser analisado com respeito ao tempo de CPU. O desenvolvimento destes códigos e a análise devem seguir os seguintes roteiros: A corretude código será testada sobre instâncias cujo gerador será fornecido e poderá ser encontrado na página do curso. Também estará disponível na página do curso uma classe para a obtenção do tempo de CPU gasto.

O trabalho entregue deve conter:
This document was translated from LATEX by HEVEA.