PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Período: 2009.2
8 de setembro de 2009
Horário: 2as-feiras e 4as-feiras de 15 às 17 horas
ANÁLISE DE ALGORITMOS (INF 1721)
1a Lista de Exercícios
  1. Considere as seguintes funções:
    1. 10.np
    2. log n
    3. log ( n2 )
    4. 0.005.n0.00001
    5. 1000.(log n)2
    6. 30.n3.log n
    7. 50.n.log2 n
    8. (log n)log n
    9. n/log n
    10. 70.n
    11. log log n
    12. (1.5)(log n)2
    13. 90.n2.log n + n3. log n

  2. Seja fi(n) o número de operações realizadas pelo programa i abaixo(log logaritmo na base 2).
    ************** A1  ************************
    Chamada:  A1 (n,k)
    void A1 (int n, int k)
    {
      int i,f,m;
      i = 0;
      f = (int)(log(n)/2);
      while ( 1 )
        {
           m = (int)((i+f)/2);
           p = 2**m;
           if (k < p){
                if (k >= (p/2) )
                  {
                    return(p/2);
                  }
                f = m;
             }
           else {
                if (k < 2*p)
                  {
                    return(p);
                  }
                i = m;
             }
        }
    }
    
    ************** A2  ************************
    Chamada:  A2 (1,n,k)
    int A2 (int i, int f, int k)
    {
      int a,b,p;
      if (i < f)
        {
           a = (int)log(i);
           b = (int)log(f);
           h = (int)((a+b)/2);
           p = 2**h;
           if (k < p)
             {
                if (k >= (p/2) )
                  {
                     return(p/2);
                  }
                else
                  {
                     return(A2(i, p/2, k));
                  }
             }
           else
             {
                if (k < 2*p)
                  {
                     return(p);
                  }
                else
                  {
                     return(A2(2*p, f, k));
                  }
             }
        }
    }
    
    ************** A3  ************************
    Chamada:  A3 (1, n)
    void A3 (int i, int f)
    {
      int j,continue;
      if (i <= f)
        {
           continue = 1;
           j = i;
           while ( (j <= f) && continue)
             {
                if (V[i] > V[j])
                  {
                     V[i] = V[j];
                     continue = 0;
                  }
                j = j + 1;
             }
           A3(i,(int)(f/2));
        }
    }
    
    ************** A4  ************************
    Chamada:  A4 (1, n)
    void A4 (int i, int f)
    {
      int j,continue;
      if (i <= f)
        {
           continue = 1;
           j = i;
           while ( (j <= f) && continue)
             {
                if (V[i] > V[j])
                  {
                     V[i] = V[j];
                     continue = 0;
                  }
                j = j + 1;
             }
           m = (int)((f-i)/5);
           A4(i,i+m);
           A4(i+m+1,i+2*m);
           A4(i+2*m+1,i+3*m);
        }
    }
    
  3. Considere uma matriz quadrada M contendo n números inteiros (você pode assumir que n = (2k)2 para algum k inteiro). Esta matriz é dada ordenada tanto nas linhas como nas colunas (veja o exemplo abaixo, para n=64, k seria 3).

    é
    ê
    ê
    ê
    ê
    ê
    ê
    ê
    ê
    ë
    4 10 21 34 39 40 57 62
    9 17 28 35 41 42 58 72
    19 20 30 47 49 49 65 73
    27 39 40 48 52 60 66 79
    33 43 44 58 59 61 77 81
    46 46 60 63 69 71 79 88
    56 61 62 68 72 76 87 88
    64 67 69 73 83 89 90 91
    ù
    ú
    ú
    ú
    ú
    ú
    ú
    ú
    ú
    û

    Table 1:

    Considere agora o seguinte problema: Dado um número inteiro i, deseja-se saber se este se encontra na matriz M. Analise a complexidade (de pior caso) dos algoritmos abaixo para resolver este problema. A complexidade deve ser em função de n.
    1. Algoritmo I
      • Passo 0: Seja l uma linha de M. Faça l=0.
      • Passo 1: Execute uma Busca Binária para encontrar i na linha l de M. Se i for encontrado, responda SIM e PARE. Senão, incremente l.
      • Passo 2 Se l é uma linha de M vá para o passo 1. Senão, responda NÃO e PARE.
    2. Algoritmo II
      • Passo 0: Seja (p,q) a posição central de M, que divide M em M1, M2, M3 e M4, onde M1 é a submatriz superior esquerda, M2 a superior direita, M3 a inferior esquerda e M4 a inferior direita, de tamanhos iguais. Se M1 for vazia, Responda NÃO e PARE. Senão vá para o passo 1.
      • Passo 1 Se i for igual a M(p,q), responda SIM e PARE. Senão vá para o passo 2.
      • Passo 2: Se i for menor que M(p,q) execute Alg. II para as matrizes M1, M2, e M3. Senão execute Alg. II para M2, M3 e M4.

    3. Algoritmo III
      • Passo 0: Seja (p,p) uma posição da diagonal de M.
      • Passo 1: Busque sequencialmente na diagonal a posição p tal que M(p,p) < i < M(p+1,p+1) utilize essa posição para obter quatro matrizes a partir de M: M1, M2, M3 e M4 (observe que o pior caso é o que tem estas 4 matrizes de tamanhos iguais). Se M1, M2, M3 e M4 forem vazias, Responda NÃO e PARE. Senão vá para o passo 2.
      • Passo 2 Se i for igual a M(p,p) ou M(p+1,p+1), responda SIM e PARE. Senão vá para o passo 3.
      • Passo 3: Execute Alg. III para as matrizes M2 e M3.

    4. Algoritmo IV
      • Passo 0: Seja (p,p) uma posição da diagonal de M.
      • Passo 1: Utilize Busca Binária na diagonal para encontrar a posição p tal que M(p,p) < i < M(p+1,p+1) utilize essa posição para obter quatro matrizes a partir de M: M1, M2, M3 e M4 (observe que o pior caso é o que tem estas 4 matrizes de tamanhos iguais). Se M1, M2, M3 e M4 forem vazias, Responda NÃO e PARE. Senão vá para o passo 2.
      • Passo 2 Se i for igual a M(p,p) ou M(p+1,p+1), responda SIM e PARE. Senão vá para o passo 3.
      • Passo 3: Execute Alg. IV para as matrizes M2 e M3.

  4. Dê uma descrição precisa dos algoritmos de ordenação abaixo e analise suas respectivas complexidades de pior caso. A entrada é um conjunto de n inteiros.
    1. Ordenação por intercalação (merge sort)
    2. Ordenação por rápida (quick sort)
    3. Ordenação por inserção:
      • Utilizando um vetor como estrutura abstrata de dados (insertion sort);
      • Utilizando uma árvore balanceada de busca como estrutura abstrata de dados: descreva as etapas no algoritmo que são fase de inserção e de preenchimento do vetor ordenado;
      • Utilizando uma Heap como estrutura abstrata de dados: descreva as etapas no algoritmo que são fase de inserção e de preenchimento do vetor ordenado (Heapsort);
      • Discute as 3 versões acima.

    4. Ordenação por radicais (radix sort), neste último considere que os inteiros são positivos e menores que 100000.

  5. Seja o problema de ordenar um conjunto de n inteiros I onde qualquer que seja x Î I, 0 £ x £ n3. Apresente um algoritmo O(n) para ordenar esse conjunto I. Explique como isso é possível, uma vez que sabemos que a ordenação de um conjunto de n elementos tem limite inferior de complexidade n log n, i.e. W(n log n).

  6. Dado um vetor V (ou tupla, i.e. elementos onde a ordem em que aparecem é relevante) de n elementos de Z, uma inversão ocorre quando $ i,j tais que i<j £ n e V[i] > V[j]. Diz-se que (i,j) é uma inversão de V.
    1. Escreva um algoritmo iterativo (não-recursivo) que calcule o número de inversões de V.
    2. Utilize divisão e conquista para obter um algoritmo recursivo. Dica: Este algoritmo deve ser semelhante ao MergeSort.
    3. Escreva sua relação de recorrência.
    4. Descreva as estruturas de dados e analise as respectivas complexidades dos algoritmos que você propôs acima.

  7. Considere d sequências ordenadas de números inteiros. O número total de elementos é n. Descreva um algoritmo que obtenha uma única sequência ordenada com os n elementos em O(n log d).

  8. Considere duas sequências ordenadas S e T, onde |S|=n, |T|=k e k<n. T é uma subsequência de S se todo elemento de T está em S. Proponha um algoritmo O(n) para determinar se T é ou não é uma subsequência de S.

  9. Seja x1,x2,...,xn uma sequência de números reais (não necessariamente positivos). Escreva um algoritmo de complexidade O(n) para encontrar a subsequência xi,xi+1,...,xj (de elementos consecutivos) tal que o produto x1 * x2 * ... * xn seja máximo (dentre todas as subsequências de números consecutivos). O produto de uma subsequência vazia é definido como 1.

  10. Suponha que você tenha um algoritmo que funcione como uma caixa preta (você não pode ver como ele foi construído) e que tem as sequintes propriedades: se você insere qualquer sequência de números reais e um inteiro k, o algoritmo retorna "Sim" ou "Não", indicando se existe um subconjunto dos números reais cuja soma seja exatamente k. Mostre como usar esta caixa preta para encontrar um subconjunto cuja soma seja k. Você pode usar a ``caixa preta'' O(n) vezes (onde n é o tamanho da sequência de números reais).

  11. Escreva um algoritmo de "busca binária" que não divida o conjunto de elementos em 2 subconjuntos de tamanhos (aproximadamente) iguais, mas sim em um subconjunto de tamanho um terço do original e outro de tamanho dois terços do original. Compare a complexidade deste algoritmo com a do algoritmo de busca binária.

  12. 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. Compare a complexidade deste algoritmo com a do algoritmo de busca binária.

  13. Sejam x1,x2,...,xn e y1,y2,...,yn sequências de inteiros ordenadas de forma não decrescente. Escreva um algoritmo que encontre a mediana da intercalação dos 2n elementos. (Dica: use busca binária).

  14. Sejam u e v dois números de n bits (considere que n é potência de 2). A multiplição tradicional de u por v utiliza O(n2) operações. Um algoritmo baseado em divisão e conquista divide os números em duas partes iguais, calculando o produto como: uv = (a2n/2+b)(c2n/2+d) = ac2n + (ad + bc)2n/2 + bd. As multiplicações ac, ad, bc e bd são feitas usando este mesmo algoritmo recursivamente.
  15. Considere dois heaps h1 e h2 de tamanhos n e m, respectivamente. Escreva um algoritmo para construir um heap que contenha todos os elementos dos heaps h1 e h2. A complexidade do algoritmo deve ser O(log(m+n)) no pior caso.

  16. Prove que se k é uma constante não negativa e n é potência de 2, então T(n) = 3knlog2 3 - 2kn é a solução da recorrência:
    T(n) = ì
    í
    î
    k, n = 1
    3T(n/2) + kn, n > 1


This document was translated from LATEX by HEVEA.