ATPS - Classificação e Pesquisa

Relação Reflexiva: Uma relação R é reflexiva se todo elemento de A está relacionado consigo mesmo, ou seja, para todo x[pic 1]A: (x,x)[pic 2]R, isto é, para todo x[pic 3]A: xRx. Exemplo: Uma relação reflexiva em A={1,2,3}, é dada por: R = {(1,1),(2,2),(3,3)}

Relação Simétrica: Uma relação R é simétrica se o fato que x está relacionado com y, implicar necessariamente que y está relacionado com x, ou seja: quaisquer que sejam x[pic 4]A e y[pic 5]A tal que (x,y)[pic 6]R, segue que (y,x)[pic 7]R. Exemplo: Uma relação simétrica em A={1,2,3}, é: R = {(1,1),(2,2),(1,2),(2,1)}

Relação Transitiva: Uma relação R é transitiva, se x está relacionado com y e y está relacionado com z, implicar que x deve estar relacionado com z, ou seja: quaisquer que sejam x[pic 8]A, y[pic 9]A e z[pic 10]A, se (x,y)[pic 11]R e (y,z)[pic 12]R então (x,z)[pic 13]R. Exemplo: Uma relação transitiva em A={1,2,3}, é: R = {(1,1),(1,3),(3,2),(1,2)}

Se A é o conjunto de todas as vagas existentes no 1º andar, E seria do 2° andar, I do 3° andar, O do 4° andar e U do 5° andar e cada elemento dos conjuntos representa uma vaga, cada andar tem 24 vagas.

Conjuntos A, E, I, O E U

A = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)

E = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)

I = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)

O = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)

U = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)

Analisando os conjuntos podemos ver que há os três tipos de relações entre eles, sendo assim ela é uma relação de Equivalência.

Relações nos conjuntos A, E, I, O e U:

Reflexiva: (2,2)

Simétrica: (5,6) , (6,5)

Transitiva: (5,14) , (14,22), logo (5,22) pertence a relação.  

BUBBLESORT

SHELLSORT

QUICKSORT

BUSCA BINARIA

• BubbleSort (500)

#include
#include
#define MAX 100000

void troca(int *a, int *b)
{
 int aux = *a;
 *a = *b ;
 *b = aux ;
}
void MostraHora()
{
struct tm *local;
time_t t;
t = time(NULL);
local=localtime(&t);
printf("%d:%d:%d\n",local->tm_hour,local->tm_min,local->tm_sec);
}
int BubbleSort(int *vetor, int tamanho, int *numeroTroca, int *comparacoes)
{
 int i,j;
 int ContadorTroca, ContadorComparacoes;
 for (i=tamanho-1; i>0; i--)
 {
   for (j=0; j    {
     ContadorComparacoes+=1;
     *comparacoes = ContadorComparacoes;
     if (vetor[i] < vetor[j])
     {
       troca(&vetor[i],&vetor[j]);
       ContadorTroca+=1;
       *numeroTroca = ContadorTroca ;
     }
   }
 }
}
void PreencherVetor(int *vetor, int tamanho){
    int contador = 0;
    for(contador; contador < tamanho; contador++)
    {
       vetor[contador] = rand() % tamanho;
    }
}
int main()
{
 clock_t t0, tf;
 double tempo_gasto;
 int v[500];
 PreencherVetor(v,500);
 int Comparacoes, Ntroca;
  t0 = clock();
 BubbleSort(v,500,&Ntroca,&Comparacoes);
 tf = clock();
 tempo_gasto = ( (double) (tf - t0) ) / CLOCKS_PER_SEC;
  printf("\n\nNumero de Trocas:      %d \n", Ntroca);
 printf("Numero de Comparacoes: %d \n", Comparacoes);
 printf("Tempo gasto:           %lf s\n", tempo_gasto);
  getch();  
}

...