CURSO DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
PROJETO E ANÁLISE DE ALGORITMOS

Última alteração: 29. Abril 2003


Horario : Terça: 14:55 - 16:35, Quinta: 14:55 - 16:35, Sala: 2029
Professor: Nivio Ziviani
Monitor: Bruno Pôssas
1 $^{\underline{o}}$ Trabalho Prático - 24/04/03 - 10 pontos
Data de Entrega: 16/05/03
Penalização por Atrazo: 1 ponto até 22/05/03 mais 1 ponto por dia útil a seguir
Observação: Toda a documentação deverá ser apresentada como uma página acessível via Web (apresente o link para acesso à documentação).

  1. Avaliar as somas (0,5 + 0,5 + 0,5 pontos):
    1. \(\sum_{i=1}^n a^i\)
    2. \(\sum_{i=1}^n \frac{1}{i}\)
    3. \(\sum_{i=1}^n \log i\)

  2. Apresente a complexidade de tempo para os procedimentos abaixo: (0,5 + 0.5 + 0.5 + 0.5 pontos) 

    1. Pesquisa(n);
if  n <= 1
then termine
else begin
     obtenha o maior elemento dentre os n elementos;
     { de alguma forma isto permite descartar 2/5 dos   }
     { elementos e fazer uma chamada recursiva no resto }
     Pesquisa(3n/5);
     end;


    2. FUNCTION Fib(n: integer): integer;
BEGIN
  IF n = 0
  THEN Fib := 0
  ELSE IF n = 1
       THEN Fib := 1
       ELSE Fib := Fib(n-1) + Fib(n-2)
END;


    3. PROCEDURE Sort1 ( VAR A: ARRAY[1..n] OF integer;
                 i, j: integer );
{ n uma potencia de 2 }
BEGIN
  IF i < j
  THEN BEGIN
       m := (i + j - 1)/2;
       Sort1(A,i,m);
       Sort1(A,m+1,j);
       Merge(A,i,m,j);
       { Merge intercala A[i..m] e A[m+1..j] em A[i..j] }
       END;
END;


    4. PROCEDURE Sort2 ( VAR A: ARRAY[1..n] OF integer;
                 i, j: integer );
{ n uma potencia de 3 }
BEGIN
  IF i < j
  THEN BEGIN
       m := ( (j - i) + 1 )/3;
       Sort2(A,i,i+m-1);
       Sort2(A,i+m,i+ 2m -1);	
       Sort2(A,i+2m,j);
       Merge(A,i,i+m,i+2m, j);
       { Merge intercala A[i..(i+m-1)], A[(i+m)..(i+2m-1) e 
         A[i+2m..j] em A[i..j] a um custo ( (5n/3) -2 ) }
       END;
END;

  3. Limite inferior: (1,5 pontos)

    Obtenha o limite inferior para ordenar um conjunto de números inteiros usando comparação entre chaves.

  4. Algoritmos de ordenação parcial: estudos comparativos (1,5 + 1,5 + 1,5 + 0,5 pontos)

    O problema da ordenação parcial ocorre quando se deseja obter os $k$ primeiros elementos de um arranjo contendo $n$ elementos, em uma ordem ascendente ou descendente. Quando $k=1$ o problema se reduz a encontrar o mínimo (ou o máximo) de um conjunto de elementos. Quandfo $k=n$ caimos no problema clássico de ordenação.

    O problema da ordenação parcial ocorre em muitas situações práticas (Barbosa, 2003). Por exemplo, para facilitar a busca de informação na Web existem as máquinas de busca, que são sistemas para recuperação de informação na Web (Baeza-Yates e Ribeiro-Neto, 1999; Witten, Mofat e Bell, 1999) É comum uma consulta na Web retornar centenas de milhares de documentos relacionados com a consulta. Entretanto, o usuário está interessado apenas nos $k$ documentos mais relevantes, onde $k$, em geral, é menor do que 200 documentos (na realidade o usuário consulta apenas os 10 primeiros documentos mostrados na primeira página de resposta na maioria das vezes). Consequentemente, a comunidade de recuperação de informação necessita de algoritmos eficientes de ordenação parcial.

    O objetivo deste trabalho é realizar um estudo comparativo dos principais algoritmos de ordenação interna que possam ser adaptados para realizar eficientemente ordenação parcial. Assim, considere os seguintes algoritmos de ordenação interna: Inserção, Shellsort, Heapsort, Quicksort (Ziviani, 1993).

    1. Determine experimentalmente o número esperado de (i) comparações e (ii) movimento-de-registros para cada um dos métodos de ordenação indicados acima.

      Utilize arquivos de diferentes tamanhos com chaves geradas randomicamente. Use o programa Permut.c apresentado abaixo para obter uma permutação randômica de $n$ valores. Repita cada experimento algumas vezes e obtenha a média para cada medida de complexidade. Dê a sua interpretação dos dados obtidos, comparando-os com resultados analíticos.

    2. Uma opção alternativa é considerar os mesmos algoritmos propostos e determinar experimentalmente o tempo de execução de cada um dos métodos de ordenação indicados acima.

      Use o programa Permut.c para gerar arquivos de tamanhos 1.000, 10.000, 100.000 e 1.000.000 de registros. Para cada tamanho de arquivo dê a sua interpretação dos dados obtidos.

    3. Apresente resultados analíticos para os algoritmos estudados. Considere diferentes valores de $k$, tais como $k=1$, $k=2$, $k « n$, e $k=n$, onde o caso $k « n$ é o mais interessante.

    4. Procure trabalhos relacionados na literatura (se houver) que tratem do assunto e descreva suscintamente esses trabalhos.

    Observações:

    1. Utilize o procedimento Permut.c abaixo para obter uma permutacao randômica das chaves. 
      #include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/timeb.h>

void IniciaRand() { /* Substituir por uma funcao que tome tempo em ms */
  time_t ltime;
  time(&ltime);
  ltime%=10000;
  srand(ltime);
}

double rand0a1() {
  double resultado=  (double) rand()/ 0x7FFF; /* Dividir pelo maior inteiro */
  if(resultado>1.0) resultado= 1.0;
  return resultado;
}

void Permut( int A[], int n) {
 int i,j,b;

 IniciaRand(); /* Funcao que Inicia a geracao de numeros randomicos */
 for(i = n-1; i>0; i --) {
   j = (i * rand0a1()) +1 ;
   b = A[i];
   A[i] = A[j];
   A[j] = b;
 }
}

int main() {
  unsigned int x;
  int v[20];

  for(x=0;x<20;x++)    v[x]=x;
  Permut(v,20);
  for(x=0;x<20;x++)  printf("%d ",v[x]);
  printf("\n");
  return 0; 
}
    2. O problema da ordenação parcial foi proposto por Barbosa (2003).

    [BYR] R. Baeza-Yates and B. Ribeiro-Neto Modern Information Retrieval, Addison-Wesley, 1999.

    Ramurti A. Barbosa Comunicação pessoal, Akwan Information Technologies, 2003.

    [WMB99] I. H. Witten, A. Moffat, T.C. Bell Managing Gigabytes Compressing and Indexing Documents and Images, Morgan Kaufmann Publishers, 1999 (second edition). Bom livro sobre implementação de sistemas de RI.

    [Z] Ziviani, N. Projeto de Algoritmos Com Implementações em Pascal e C, Pioneira Thomson Learning, 1993.


Nivio Ziviani
2003-04-29