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
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 fatorial foi o primeiro algoritmo recursivo que estudamos na
disciplina. Escreva dois programas na linguagem C que implementam o
fatorial RECURSIVO e ITERATIVO. Em suas implementações a cada vez que
o fatorial de 1 é calculado uma mensagem é impressa na tela. Edite,
compile e execute seus programas. Quantas mensagens surgem quando você
calcula o fatorial de 8 na versão iterativa? E na versão recursiva?
- Uma definição recursiva do fatorial é N! = (N+1)!/(N+1); que tal
usar esta definição para implementar uma função no computador?
- Escreva os programas iterativo e recursivo que exibem como saída a série
completa de Fibonacci, do zero-ésimo termo ao i-ésimo termo, sendo i dado
como entrada para o programa.
- Escreva funções recursivas para calcular a exponenciação, soma, subtração, divisão (retorna quociente e resto) e
multiplicação de dois números inteiros, positivos maiores que zero.
- Escreva um procedimento recursivo para somar todos os elementos de um
vetor de N inteiros.
- Escreva um procedimento recursivo para calcular a média de todos os elementos de um
vetor de N inteiros.
- Escreva um procedimento recursivo que retorna o menor (Min) elemento de um
vetor de N inteiros.
- Escreva um procedimento recursivo que retorna o maior (Max) elemento de um
vetor de N inteiros.
- 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.