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
- Soma dos N primeiros números naturais: N*(N+1)/2
- Soma dos N primeiros termos de uma P.A.: N*(a1+aN)/2 = N*a1 + N*(N+1)/2
*r
- Limite da soma dos termos de uma P.G. infinita: a1/(1-q)
- Dizemos que g(N) = O(f(N)) se c*f(N) >= g(N), N>=m; c e m são constantes
Questões
- O que faz um algoritmo de pesquisa ou busca?
- Quais algoritmos de pesquisa foram vistos na disciplina?
- 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?
- 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.
- Escreva o algoritmo da pesquisa sequencial inspecionando o vetor a partir
do primeiro elemento, e usando sentinela.
- Agora escreva o mesmo algoritmo da pesquisa sequencial, também
inspecionando inicialmente o primeiro elemento do vetor, mas SEM usar
sentinela.
- 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.
- 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?
- Mostre como se calcula o caso MÉDIO do número de comparações necessárias
na pesquisa sequencial.
- O sentinela é obrigatório do algoritmo da pesquisa sequencial? Por que
usá-lo? Existe algum "custo" em usar o sentinela?
- 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.
- 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.
- O que faz um algoritmo de ordenação?
- O que é um algoritmo de ordenação estável?
- 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.
- 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.
- Quantas comparações são realizadas pelo SelectSort no melhor caso? E no
caso médio? E no pior caso?
- Quantas trocas de elementos de lugar são realizadas pelo SelectSort
no melhor caso? E no caso médio? E no pior caso?
- 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.
- 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.
- Quantas comparações são realizadas pelo BubbleSort no melhor caso? E no
caso médio? E no pior caso?
- Quantas trocas de elementos de lugar são realizadas pelo BubbleSort
no melhor caso? E no caso médio? E no pior caso?
- Qual a idéia principal do algoritmo QuickSort?
- 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.
- 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.
- 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.
- 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.
- Prove que g(N) = 5*N^2 + 27 é O(N^2), dadas as constantes c=8 e m=3.
- Prove que a função g(N) = 3*N^3 + 2*N^2 + N é O(N^3) para N >= 1, c =
11.
- Prove que g(N) = 3*N^2 + 11*N + 5 é O(N^2), para N >= 0.
- 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.
- 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.
- 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);
}
- 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);
}