Lista 2 de PAA
1) Responda às perguntas a seguir:
i) Quais são os passos para se analisar algoritmos recursivos?
Definir o tamanho da entrada: Identificar o parâmetro nnn.
Determinar a operação básica: Identificar a operação que define o tempo de execução
(ex.: comparações).
Analisar a execução: Verificar como a operação é realizada para diferentes tamanhos de
entrada.
Estabelecer a recorrência: Configurar a relação que descreve o tempo de execução.
Resolver a recorrência: Encontrar a solução explícita da relação.
Classificar a eficiência: Determinar a complexidade assintótica (ex.: O(n), O(logn).
ii) Quais são as técnicas utilizadas para resolver relações de recorrência?
Substituição direta, Substituição Inversa e o Teorema Mestre.
2) Dado o problema da Torre de Hanoi, responda:
i) Qual a definição do problema?
Mover n discos de um pino A para um pino C, utilizando um pino auxiliar B,
garantindo que apenas um disco seja deslocado por vez e que nenhum disco maior seja
colocado sobre um menor.
ii) Faça a análise passo a passo do algoritmo para o problema da Torre de
Hanoi:
Solução recursiva básica para n > 1 discos do pilar A para o pilar C:
● Mova recursivamente n - 1 discos de A para B (com C auxiliar).
● Mova 1 (o maior) disco de A para C.
● Mova recursivamente n - 1 discos de B para C (com B auxiliar)
Definir o parâmetro n: n representa a quantidade de discos a serem transferidos do pino A
para o pino C.
Identificar a operação fundamental: A ação principal do algoritmo é o deslocamento de
um disco entre dois pinos.
Verificar a execução da operação para diferentes entradas: A operação fundamental é
realizada recursivamente para subproblemas de tamanho n−1.
Estabelecer a relação de recorrência: T(n)=2T(n−1)+1, onde 2T(n−1) + 1 corresponde aos
movimentos para resolver os subproblemas de tamanho n− e +1 ao deslocamento do maior
disco.
Derivar a fórmula fechada da recorrência: T(n)=2kT(n−k)+(2k−1).
Determinar a eficiência do algoritmo: T(n)=2n−1, o que mostra que o número de
movimentos cresce exponencialmente com nnn. A complexidade do algoritmo é O(2n).
3) Considere o pseudocódigo de busca em uma árvore binária. Responda:
i) O pseudocódigo pode ser considerado um algoritmo? Justifique com base
na definição de algoritmo vista em materiais anteriores.
Pode sim, pois ele atende as necessidades, como ser finito, ter
entradas válidas e possui instruções possíveis.
ii) Faça a análise passo a passo do algoritmo.
TipoItem* Pesquisa(TipoArvore a, TipoChave x):
if(a == NULL): return NULL
if(x == a -> item.chave): return &(a -> item)
if(x < a -> item.chave): return Pesquisa(a -> subArvEsq, x)
if(x > a -> item.chave): return Pesquisa(a -> subArvDir, x)
● Definir o parâmetro n: O parâmetro nnn corresponde ao número total de nós
presentes na árvore binária.
● Determinar a operação fundamental: A operação principal do algoritmo é
comparar x com a chave armazenada a -> item.chave.
● Analisar a execução da operação para diferentes tamanhos de entrada: A
operação fundamental ocorre em cada nível da árvore, e o número de comparações
varia conforme a profundidade da árvore.
● Estabelecer a relação de recorrência: T(n)=T(n/2)+1, onde T(n/2) representa o
custo de realizar a busca em uma subárvore de tamanho n/2, e +1 é o custo da
comparação no nó atual.
● Derivar a fórmula fechada da recorrência: T(n)=T(n/2k)+k.
● Determinar a eficiência do algoritmo: Para árvores balanceadas, a complexidade
é O(logn), enquanto para árvores desbalanceadas, a complexidade é O(n).
2
4) Resolva a recorrência pelo Teorema Mestre: 𝑇(𝑛) = 8𝑇(𝑛/2) + 𝑛 :
5) O tempo de execução de um algoritmo A é descrito pela recorrência
2
𝑇(𝑛) = 9𝑇(𝑛/2) + 𝑛 . Um outro algoritmo A' tem um tempo de execução
2
descrito pela recorrência 𝑇'(𝑛) = 𝑎𝑇'(𝑛/4) + 𝑛 . Qual é o maior valor inteiro
de a tal que A' tenha uma complexidade assintótica menor que A?
6) Ao analisar a complexidade de um algoritmo recursivo, qual é a abordagem mais comum
utilizada para encontrar sua complexidade de tempo?
( ) Calcular diretamente o número de operações no código-fonte.
(X) Estabelecer uma equação de recorrência para descrever o comportamento do algoritmo
e resolvê-la.
( ) Simular o código para pequenos valores de entrada e generalizar os resultados.
( ) Medir o tempo de execução em diferentes máquinas e calcular uma média.
7) Considere o seguinte algoritmo recursivo para calcular o valor de
Fibonacci:
int fibonacci(int n) {
if (n <= 1) return n;
else return fibonacci(n-1) + fibonacci(n-2);
}
Qual é a complexidade de tempo desse algoritmo?
( ) O(n)
( ) O(log n)
( ) O(n^2)
(x) O(2^n)
8) O teorema mestre é utilizado para resolver qual tipo de problema?
( ) Análise de algoritmos iterativos.
(x) Equações de recorrência associadas a algoritmos recursivos que dividem
o problema em subproblemas.
( ) Problemas de otimização de memória.
( ) Verificação da correção de algoritmos.
9) Considere a equação de recorrência 𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑛. Qual é a
complexidade de tempo utilizando o teorema mestre?
(x) O(n log n)
( ) O(n^2)
( ) O(n)
( ) O(log n)
10) Considere a equação de recorrência 𝑇(𝑛) = 3𝑇(𝑛/3) + 𝑛. Qual é a
complexidade de tempo utilizando o teorema mestre?
( ) O(n)
(x) O(n log n)
( ) O(n^2)
( ) O(n log log n)
