Exercicios de Fixação 01 - Conceitos Fundamentais - Parte I

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 I
1. Um algoritmo é executado em 10 segundos para uma entrada de tamanho 50. Se o algoritmo
é quadrático, quanto tempo em segundos ele gastaria, aproximadamente, no mesmo
computador, se a entrada tiver tamanho 100? 
2. Considere o algoritmo a seguir e responda as perguntas que seguem, fornecendo
justificativas:
algoritmo enigma(n, ref A)
entrada: um número natural n e uma referência para o vetor A com n valores reais
saída: não revelada
   para i de 1 a n­1 faca
      k   i←
      para j de i+1 a n faca
       se (A[j] < A[i]) entao
k   j←
fimse
 fimpara
      troca(A[k], A[i])
   fimpara
fimalgoritmo
a. Supondo que a função troca() faz a troca de valores de seus 2 argumentos, o que o
algoritmo enigma faz?
b. Caracterize as instâncias de pior caso do algoritmo.
3. Um problema algorítmico está definido quando estabelecemos os seguintes três aspectos: o
conjunto de entradas; o conjunto de saídas válidas; e, finalmente, a relação entre cada
entrada e suas correspondentes saídas válidas. Todos os demais aspectos são irrelevantes,
1
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
pois as medidas de eficiência O,  e  não dependem de constantes multiplicativas
associadas ao artefato computacional. É correta tal afirmação? Justifique.
4. Ordene as funções, a seguir, por sua taxa assintótica de crescimento.
4nlgn + 2n 210 2lgn
3n + 100nlgn 4n 2n
n2 + 10n n3 nlgn
5. É verdade que 1/2n2 é O(n)? Justifique.
6. Qual das seguintes afirmações sobre crescimento assintótico de funções não é verdadeira?
a) 2n2 + 3n + 1 é O(n2)
b) Se f(n) é O(g(n)) então g(n) é O(f(n))
c) lgn2 é O(lgn)
d) Se f(n) é O(g(n)) e g(n) é O(h(n)) então f(n) é O(h(n))
e) 2n+ 1 é O(2n)
7. Critique a afirmação 'n2 – 100n está O(n2) para todo n ≥100'.
8. Mostre que lgn não está em (n).
9. Mostre que n(n + 1)/2 e n(n – 1)/2 estão em (n2).
10. Quais das seguintes igualdades são verdadeiras?
2
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
I. n2 = o(n3)
II. 2n + 1 = o(n2)
III. n3 = o(n2)
IV. 3n + 5nlgn = o(n)
V. lgn + n1/2= o(n)
a) somente I e II
b) somente II, III e IV
c) somente III, IV e V
d) somente I, II e V
e) somente I, III e IV
11. Sejam duas funções f(n) que mapeiam números inteiros positivos em números reais
positivos. Com respeito às notações assintóticas de complexidade, avalie as afirmações a
seguir.
I. Diz-se que f(n) é O(g(n)) se existe uma constante real c > 0 e existe uma constante inteira
n0 ≥ 1 tal que f(n) ≤ cg(n) para todo inteiro n ≥ n0
II. Diz-se que f(n) é o(g(n)) se para toda constante real c > 0 existe uma constante inteira n0
≥ 1 tal que f(n) < cg(n) para todo inteiro n ≥ n0 
III. Diz-se que f(n) é (g(n)) se existe uma constante real c > 0 e existe uma constante
inteira n0 ≥ 1 tal que f(n) ≥ cg(n) para todo inteiro n ≥ n0 
IV. Diz-se que f(n) é (g(n)) se para toda constante real c > 0 existe uma constante inteira n0
≥ 1 tal que f(n) > cg(n) para todo inteiro n ≥ n0 
V. Diz-se que f(n) é (g(n)) se, e somente se, f(n) é O(g(n)) e f(n) é (g(n))
A análise permite concluir que
a) todas as afirmativas são falsas
3
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
b) todas as afirmativas são verdadeiras
c) apenas as afirmativas I e III são verdadeiras
d) apenas as afirmativas II e IV são verdadeiras
e) apenas a afirmativa V é falsa
12. Alice e Bob estão discutindo sobre seus algoritmos. Alice afirma que seu método de tempo
O(nlgn) é sempre mais rápido que o método de Bob de tempo O(n2). Para decidir a questão,
eles executaram um conjunto de experimentos. Para o espanto de Alice, eles encontraram
que se n < 100, o algoritmo O(n2) executa mais rápido, e somente quando n ≥ 100 é o
algoritmo O(nlgn) é um pouco melhor. Explique como isso é possível.
13. Suponha que dois algoritmos, A e B, resolvem o mesmo problema, para um tamanho de
instâncias dado por n. Em quais dos seguintes casos podemos afirmar que A é mais rápido
que B? Justifique. 
a) Caso 1: A consome tempo O(lgn) no pior caso e B consome tempo O(n3) no pior caso;
b) Caso 2: A consome O(nlgn) unidades de tempo no pior caso e B consome (n2) unidades
de tempo pior caso;
c) Caso 3: No pior caso, A consome O(n2) unidades de tempo e B consome (n2lgn)
unidades de tempo.
14. Observe as funções representadas no gráfico, a seguir.
4
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
Indique a alternativa falsa sobre o crescimento assintótico dessas funções:
a) f(n) = O(h(n)) e i(n) = (g(n))
b) f(n) = (h(n)) e i(n) = (h(n))
c) g(n) = O(i(n)) e h(n) = (g(n))
d) g(n) = O(i(n)), i(n) = O(f(n)) e, portanto, g(n) = O(f(n))
e) h(n) = (i(n)), logo, i(n) = O(h(n))
15. Considere dois algoritmos A1 e A2, cujas funções de custo são, respectivamente, T1(n) = n2 –
n + 1 e T2(n) = 6nlgn + 2n. Para simplificar a análise, assuma que n > 0 é sempre uma
potência de 2. Com relação ao enunciado, indique a alternativa correta. 
a) Como T1(n) = (n2) e T2(n) = (nlgn), então A2 é sempre mais eficiente que A1
b) O limite superior T1(n) = O(n3) é correto assintoticamente restrito
c) O limite inferior T2(n) = (n3) é correto e assintoticamente restrito
d) T1 e T2 são assintoticamente equivalentes
5
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
e) A1 é mais eficiente que A2, para n suficientemente pequeno
16. Sejam T1(n) = 100n + 15, T2(n) = 10n2 + 2n e T3(n) = 0,5n3 + n2 + 3 as equações que
descrevem a complexidade de tempo dos algoritmos Alg1, Alg2 e Alg3, respectivamente,
para entradas de tamanho n. A respeito da ordem de complexidade desses algoritmos, pode-
se concluir que
a) as complexidades assintóticas estão, respectivamente, em O(n), O(n2) e O(n3)
b) as complexidades assintóticas estão, respectivamente, em O(n), O(n2) e O(n2)
c) as complexidades assintóticas estão, respectivamente, em O(100), O(10) e O(0,5)
d) Alg2 e Alg3 pertencem as mesmas classes de complexidade assintótica
e) Alg1 e Alg2 pertencem as mesmas classes de complexidade assintótica
17. Em relação ao limite assintótico de notação O, atribua V (verdadeiro) ou F (falso) às
afirmativas a seguir.
( ) Em uma estrutura de laço duplamente aninhado, tem-se imediatamente um limite
superior O(n2)
( ) Em uma estrutura de laço duplamente aninhado, o custo de cada iteração do laço interno
é de limite superior O(1)
( ) Em uma estrutura de laço triplamente aninhado, o custo de cada iteração do laço interno
é de limite superior O(n3)
( ) O limite O(n2) para o tempo de execução do pior caso de execução aplica-se para
qualquer entrada
( ) f(n) = O(g(n)) é uma afirmação de que algum múltiplo constante de g(n) é de limite
assintótico inferior
Indique a alternativa que contém, de cima para baixo, a sequência correta.
a) V, V, F, V, F
6
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
b) V, F, V, F, V
c) F, V, V, F, F
d) F, F, V, V, F
e) F, F, F, V, V
18. Considere o problema de encontrar o maior e o menor elemento de um vetor de inteiros
A[1..n], n > 0. O algoritmo simples para resolver este problema pode ser derivado do
Programa, a seguir.
Programa – Implementação direta para obter o máximo e o mínimo de um conjunto
procedure MaxMin1 (var A: Vetor; var Max, Min: integer);
var i: integer;
begin
Max := A[1]
Min := A[1]
for i := 2 to n do
begin
if A[i] > Max then Max := A[i];
if A[i] < Min then Min := A[i];
end;
end.
Seja f uma função de complexidade talque f(n) é número de comparações entre os elementos de A,
se A contiver n elementos. Portanto, f(n) = 2(n-1), para n>0.
Faça a análise de complexidade para o melhor caso, pior caso e caso médio do programa
apresentado.
19. Bill dispõe de um algoritmo, encontre2D, para encontrar um elemento x em um arranjo Anxn.
O algoritmo encontre2D itera sobre s linhas de A e chama o algoritmo encontreArray, do
trecho de código abaixo, para cada linha, até que x seja encontrado ou todas as linhas de A
7
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
tenham sido pesquisadas.
algoritmo encontreArray(x, A): 
Entrada: Um elemento x e um arranjo A com n elementos 
Saída: O índice i tal que x = A[i], ou ­1 se nenhum elemento de A é igual a x 
i = 0; 
enquanto i < n faça 
se x = A[i] então 
retorna i
senão i = i + 1
retorna ­1 
Qual o tempo para o pior caso de encontre2D em termos de n? Qual o tempo para o pior caso de
encontre2D em termos de N, onde N é o tamanho total de A? É correto dizer que encontre2D é um
algoritmo de tempo linear? Justifique.
20. Considere o código, a seguir.
void ordena (int n, int* v){
int i,j;
for (i=n­1; i>=1; i­­)
          for (j=0; j<i; j++)
            if (v[j]>v[j+1]){ /*troca*/
int temp = v[j];
v[j] = v[j+1];
v[j+1] = temp;
}
}
Apresente a análise da complexidade de tempo para o melhor, pior e médio caso. Especifique, para
tanto, o que caracteriza cada caso. 
8
	Lista de Exercícios de Fixação 01