Universidade Federal do Paraná
Departamento de Informática
Bacharelado em Ciência da Computação
Prof. Elias P. Duarte Jr.

Lista 2 de Algoritmos II


Fórmulas

Questões

  1. O que faz um algoritmo de pesquisa ou busca?

  2. Quais algoritmos de pesquisa foram vistos na disciplina?

  3. Considere que você vai fazer uma pesquisa em um banco de dados com 2048 elementos armazenados. Quantas comparações a pesquisa sequencial faz no pior caso? Quantas comparações a pesquisa binária faz no pior caso?

  4. Explique por que a pesquisa binária permite que o número máximo de comparações para encontrar um elemento em um vetor de N elementos é logN.

  5. Escreva o algoritmo da pesquisa sequencial inspecionando o vetor a partir do primeiro elemento, e usando sentinela.

  6. Agora escreva o mesmo algoritmo da pesquisa sequencial, também inspecionando inicialmente o primeiro elemento do vetor, mas SEM usar sentinela.

  7. Considerando o vetor {2,5,8,15,99} mostre quais comparações são nessárias para pesquisar o elemento 5. Agora mostre quais comparações são necessárias para pesquisar o elemento 70.

  8. Quantas comparações são necessárias para pesquisar um elemento em um vetor de N posições no MELHOR caso na pesquisa sequencial? E na pesquisa binária?

  9. Mostre como se calcula o caso MÉDIO do número de comparações necessárias na pesquisa sequencial.

  10. O sentinela é obrigatório do algoritmo da pesquisa sequencial? Por que usá-lo? Existe algum "custo" em usar o sentinela?

  11. Escreva dois programas na linguagem C que implementam o algoritmo da pesquisa sequencial, inspecionando o vetor a partir da última posição, COM e SEM sentinela. Faça um procedimento para criar um vetor de números aleatórios, e permita que o usuário entre com o elemento a ser procurado. Edite, compile e execute seus programas.

  12. Escreva dois programas na linguagem C que implementam o algoritmo da pesquisa binária RECURSIVA e ITERATIVA. Estes programas podem ser executados sobre vetores aleatórios? O que deve ser feito antes? Edite, compile e execute seus programas.

  13. O que faz um algoritmo de ordenação?

  14. O que é um algoritmo de ordenação estável?

  15. Escreva o algoritmo da ordenação por seleção (SelectSort) que busca inicialmente o MAIOR elemento do vetor, em seguida o segundo maior elemento, e assim por diante, até ter todo o vetor ordenado.

  16. Escreva o algoritmo da ordenação por seleção (SelectSort) que busca inicialmente o MENOR elemento do vetor, em seguida o segundo menor elemento, e assim por diante, até ter todo o vetor ordenado.

  17. Quantas comparações são realizadas pelo SelectSort no melhor caso? E no caso médio? E no pior caso?

  18. Quantas trocas de elementos de lugar são realizadas pelo SelectSort no melhor caso? E no caso médio? E no pior caso?

  19. Escreva o método da bolha (BubbleSort) que busca inicialmente o MAIOR elemento do vetor, em seguida o segundo maior elemento, e assim por diante, até ter todo o vetor ordenado.

  20. Escreva o método da bolha (BubbleSort) que busca inicialmente o MENOR elemento do vetor, em seguida o segundo menor elemento, e assim por diante, até ter todo o vetor ordenado.

  21. Quantas comparações são realizadas pelo BubbleSort no melhor caso? E no caso médio? E no pior caso?

  22. Quantas trocas de elementos de lugar são realizadas pelo BubbleSort no melhor caso? E no caso médio? E no pior caso?

  23. Qual a idéia principal do algoritmo QuickSort?

  24. Escreva um programa que implementa o procedimento de partição de um vetor, considerando como pivô o primeiro elemento do vetor. O programa recebe como entrada um vetor de números aleatórios.

  25. Qual o número de comparações usadas pelo InsertSort no (a) melhor caso (b) caso médio (c) pior caso? Mostre claramente como se calcula cada um destes números.

  26. O algoritmo de ordenação ShellSort é baseado no InsertSort, mas apresenta uma diferença importante: os deslocamentos sucessivos. Explique o objetivo destes deslocamentos. Explique a idéia básica de ordenação do ShellSort.

  27. Considere o seguinte vetor: [25, 57, 48, 37, 12, 92, 86, 33]
    Mostre passo a passo como se ordena este vetor com o ShellSort usando k = 5, 3, 1.

  28. Prove que g(N) = 5*N^2 + 27 é O(N^2), dadas as constantes c=8 e m=3.

  29. Prove que a função g(N) = 3*N^3 + 2*N^2 + N é O(N^3) para N >= 1, c = 11.

  30. Prove que g(N) = 3*N^2 + 11*N + 5 é O(N^2), para N >= 0.

  31. A relação de recorrência que expressa o número de comparações usadas pelo QuickSort no melhor caso é T(N) = N + 2 T(N/2). Resolva esta relação de recorrência.

  32. A relação de recorrência que expressa o número de movimentações de discos para resolver o problema das Torres de Hanoi é T(N) = 2 * T(N-1) +1. Resolva esta relação de recorrência.

  33. Considere a função recursiva abaixo. Quantas inspeções de elementos são executadas no pior caso por esta função? Mostre claramente como se faz o cálculo.
    FuncRec(N) {
    se N == 1
    então inspecione elemento e termine
    senao inspecione os N elementos da entrada;
    FuncRec(N/7);
    }

  34. Qual a relação de recorrência correspondente à função recursiva abaixo?
    FuncRec(N) {
    se N== 1
    então triture elemento e termine
    senao triture os N/2 menores elementos da entrada;
    FuncRec(N/2);
    }