Etica e Moral

ATPS – Classificação e Pesquisa – Etapa 1 

Adilson Pavan RA:0901346828 
Gino Cezar da Rosa Ciocari RA:901413776 
Marcos A. Stecca RA:926435313 
Robson J. Silva RA:901382362 
Thiago Henrique da Silva RA:991002855 

Campinas 
2010 

1 Método de busca com o melhor desempenho computacional 

Considerando os parâmetros de testes definidos no ATPS, foi possível identificar que o melhor método de busca sem a ordenação dos dados é o linear com sentinela, porém se o valor procurado não estiver no vetor, o tempo e a quantidade de testes realizados serão exatamente iguais ao da busca linear, pois a chave será localizada apenas no final da base de dados. 
O calculo de tempo foi realizado através da quantidade de ciclos do processador (clock), mas como a base utilizada nos testes é pequena o processo é muito rápido para realizar uma comparação precisa entre os algoritmos, alem disso foi possível notar que os valores definidos para busca no ATPS não estão disponíveis após a geração dos números aleatórios e dessa forma os algoritmos de busca não localizarão os valores o que forçara percorrer o vetor até o final. 

2 Desempenho da busca binária x busca linear x busca linear com sentinela 

Após a ordenação dos dados fica claro que o melhor método de busca é a binária como mostra a Figura 1, pois tanto o tempo quanto a quantidade de processamento é muito menor do que as outras técnicas de busca. 
O principal ponto é se a ordenação da base de dados é viável para aplicar esse tipo de técnica, pois dependendo do tamanho da base a ordenação pode se tornar muito lenta e exigir muito processamento. 
A ordenação através de algoritmos como bubblesort e seleção demonstraram bons resultados, mas ainda assim exigem mais processamento do que as buscas em bases que não foram ordenadas, porem se a ordenação for realizada periodicamente ou no momento em que os dados são inseridos a busca binária torna-se viável, pois a localização e o tempo de processamento são muito mais rápidos do que as demais técnicas. 

|Tipo de teste |Tamanho Vetor |Quantidade de testes | 
|Busca Linear |1.000 |1.000 | 
|Busca Linear com Sentinela |1.000 |1.000 | 
|Busca Binária |1.000 |9 | 
|Bubble Sort |1.000 |244.968 | 
|Seleção |1.000 |56.738 | 

Figura 1 – Resultados dos testes realizados com os algoritmos de busca após a ordenação da base 

3 Conclusão 

Após a realização das baterias de testes foi possível concluir que existem algoritmos de localização e ordenação mais eficientes do que outros, porém a aplicação e a utilização de cada um depende da situação e principalmente do tamanho da base de dados que será manipulada. 
Considerando os parâmetros utilizados nesses testes observamos que o melhor comportamento dos algoritmos de ordenação e seleção foram obtidos pelo método seleção e a busca binária, mas isso não significa que são os melhores para todas as situações, pois todos possuem suas particularidades e deficiências. 

Anexo I 

Código completo para realizar a bateria de testes descritas abaixo. 

/* 
Name: ATPS - Classificação e Pesquisa 
Description: Bateria de testes de busca linear, linear com sentinela e binária 
ordenação bubble sort e seleção 
*/ 

#include 
#include 
#include 
#include 

#define tempo 2000 
#define search_p 87 
#define search_s 100001 

//prototipos das funções 
void bateria_testes(int tam, int t); 
void linear(int n, int t, int *p_int, double *p); 
void linear_sentinela(int n, int t, int *p_int, double *p); 
void binaria(int n, int t, int *p_int, double *p); 
void bubblesort(int n, int t, int *p_int, double *p); 
void selecao(int n, int t, int *p_int, double *p); 
double unif(long int *seed, double low, double high); 
int inteiros_unif(long int *seed, int low, int high); 

main(){ 

//declaração de variaveis 
int op=0, tipo; 

while (op!=5){ 

system("cls"); 

//cabeçalho com os parametros de teste 

printf("\n ATPS - Classifica%c%co e Pesquisa \n",135,198); 
printf(" \n +------+--------+-----+--------+------------+----------+-------------+"); 
printf(" \n | OP | N | low | high | seed | N. Proc. | S. N. Proc. |"); 
printf(" \n +------+--------+-----+--------+------------+----------+-------------+"); 
printf(" \n | 01 | 100 | 0 | 100000 | 1234554321 | 87 | 100001 |"); 
printf(" \n +------+--------+-----+--------+------------+----------+-------------+"); 
printf(" \n | 02 | 1000 | 0 | 100000 | 1234554321 | 87 | 100001 |"); 
printf(" \n +------+--------+-----+--------+------------+----------+-------------+"); 
printf(" \n | 03 | 10000 | 0 | 100000 | 1234554321 | 87 | 100001 |"); 
printf(" \n +------+--------+-----+--------+------------+----------+-------------+"); 
printf(" \n | 04 | 100000 | 0 | 100000 | 1234554321 | 87 | 100001 |"); 
printf(" \n +------+--------+-----+--------+------------+----------+-------------+"); 
printf("\n\n Selecione os par%cmetros de teste [ 1 - 4 ]: ",131); 
scanf("%d",&op); 

if(op5){ 
printf("\n Opcao invalida !"); 
getch(); 
} 
break; 
} 
} 
} 

/*------------------------------------------------------------------------------ 
Algoritmo 1 – Gerador de números reais aleatórios 
Gerador de distribuicao uniforme retorna um numero 
double (real com longa precisão) na faixa low – high,ou seja, [low,high]. 
------------------------------------------------------------------------------*/ 
double unif(long int *seed, double low, double high){ 
double unif_ret; 
long int m,a,b,c, k; 
double value_0_1; 
m = 2147483647; 
a = 16807; 
b = 127773; 
c = 2836; 
k = *seed/b; 
*seed = a * (*seed % b) - k*c; 
if (*seed

...