Exercícios de Fixação 01 - Conceitos Fundamentais - Parte II

Prévia do material em texto

ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
Lista de Exercícios de Fixação 01
Conceitos Fundamentais – Parte II
Observação: se não especificado na questão, considere a complexidade
computacional assintótica para o pior caso.
1. Considere o algoritmo, a seguir, e responda às questões seguintes.
algoritmo(n)
entrada: Um inteiro não-negativo
T ← 0
for i ← 1 to n do
T ← T + i*i*i*i
return T
a. O que o algoritmo calcula?
b. Qual é a operação básica que ele realiza?
c. O número de vezes que a operação básica é realizada depende somente do tamanho da
entrada? Explique.
d. Quantas vezes a operação básica é executada? Dica: estabeleça um somatório ou uma
relação de recorrência para indicar o número de vezes que a operação básica é executada
e resolva-o(a). 
e. Qual é a classe de eficiência do algoritmo? Represente a classe utilizando a notação
assintótica adequada.
2. Encontre a T(n) e, em seguida, determine a complexidade assintótica do seguinte trecho de
programa.
for (i = 0; i < n; i++) { 
//sequência de instruções
} 
for (j = 0; j <= n; j++) { 
//sequência de instruções
} 
1
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
3. Calcule a T(n) e determine a complexidade assintótica do pior caso para o seguinte código.
4. Determine a complexidade assintótica para o seguinte código. 
Dica: ∑
i=1
n
i2=1²+...(n)²=n(n+1)(2n+1)
6
soma = 0;
for (int k = 0; k < n; k++)
soma++;
for (int i = 0; i < n; i++)
for (int j = 0; j < i*i; j++)
soma++;
5. Calcule a T(n) e determine a complexidade assintótica do pior caso para o seguinte código.
6. Sabendo que T (1) = 1, encontre a ordem de complexidade das relações abaixo usando o
Teorema Mestre, caso aplicável.
2
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
a. T (n) = 4T(n/4) + 2n
b. F(n) = F(n – 1) + n para todo n ≥ 2
7. Considere a função definida pela recorrência: 
f(n) = 2f(n-1), f(0) = 1 
O professor Pardau afirma que f(n) = O(n), e que isso pode ser verificado simplesmente da forma
f(n) = 2f(n-1) = 2O(n-1) = O(n)
Sendo assim, pergunta-se: o professor Pardau está certo? Justifique.
8. Responda o que se pede.
a. A recorrência T(n) = 7T(n/2) + n2 descreve o tempo de execução do algoritmo da Alice.
Um algoritmo alternativo proposto por Bob tem um tempo de execução T(n) = aT(n/4) +
n2. Qual é o maior número inteiro a que faz com que o algoritmo do Bob seja
assintoticamente mais rápido que o algoritmo da Alice? Justifique.
b. O Teorema Mestre pode ser aplicado à recorrência T(n) = 4T(n/2) + n2lgn? Justifique a
resposta. 
c. Considere que você tenha um problema para resolver e duas opções de algoritmos. O
primeiro algoritmo é quadrático tanto no pior caso quanto no melhor caso. Já o segundo
algoritmo é linear no melhor caso e cúbico no pior caso. Considerando que o melhor
caso ocorre 90% das vezes que você executa o programa enquanto o pior caso ocorre
apenas 10% das vezes, qual algoritmo você escolheria? Justifique a sua resposta em
função do tamanho da entrada.
9. Quando um algoritmo possui uma chamada recursiva, seu tempo de execução pode ser
descrito por uma recorrência. Utilize um dos métodos estudados para encontrar a ordem de
complexidade da recursão: T(n) = 3T(n/2) + n e T(1) = 1.
10. Apresente a complexidade assintótica das seguintes relações de recorrência:
a. T(n) = T(n – 1) + (n – 1), T(1) = 0
b. T(n) = T(n – 1) + n, T(1) = 1
3
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
c. T(n) = 8T(n/2) + n2, T(1) = 1
d. T(N) = 2T(N/2) + N, para N ≥ 2 e T(1) = 0
e. T(N) = 2T(N-1) + 1, para N≥ 2 e T(1) = 1
f. T(n) = 2T(n/2) + (n – 1), T(1) = 1
11. Considere o algoritmo, a seguir. Suponha que a operação crucial é o fato de inspecionar um
elemento. O algoritmo inspeciona os n elementos de um conjunto e, de alguma forma, isso
permite descartar a metade dos elementos e então fazer uma chamada recursiva sobre os n/2
elementos restantes. 
void pesquisa(int n){
if (n <= 1)
inspecione elemento e termine
else{
para cada um dos n elementos, inspecione elemento;
pesquisa(n/2);
 }
}
a. Escreva uma relação de recorrência que descreve esse comportamento;
b. Apresente a complexidade computacional do algoritmo para o melhor e o pior caso.
12. Considere o algoritmo, a seguir, e responda o que se pede, fornecendo justificativas.
algoritmo segredo(n)
entrada: Um número natural n.
saída: não revelada.
 se n = 1 entao 
devolva 1
 senao 
devolva segredo(piso(n/2)) + 1
 fimse
fimalgoritmo
a. Seja s : N → Z≥, a função que descreve o tempo de execução do algoritmo segredo em
função do valor de n. Então, defina a relação de recorrência que descreve o valor s(n).
4
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
b. Resolva a recorrência que você definiu em b.
13. Elabore um algoritmo para determinar se um inteiro positivo, n, é primo. Determine a
complexidade computacional assintótica do algoritmo.
5
	Lista de Exercícios de Fixação 01