Continuando a série de postagens com a resolução de questões do POSCOMP, nesta postagem apresento a resolução de algumas questões dos anos 2009 e 2010 sobre Complexidade de Algoritmos.

Para mais questões resolvidas, acesse a página POSCOMP.
POSCOMP 2009
As questões a seguir são do POSCOMP 2009.
Questão 21
A sequência de Fibonacci é uma sequência de inteiros, cujo primeiro termo é 0, o segundo termo é 1, e a partir do terceiro, cada termo é igual à soma dos dois anteriores. O seguinte algoritmo recursivo retorna o n-ésimo termo da sequência
Procedimento F(n)
se n < 3 então retornar n-1
senão retornar F(n-1) + F(n-2)
A chamada externa é F(n), sendo n > 0.
Assinale a alternativa CORRETA:
- (A) O algoritmo não está correto, pois não retorna o n-ésimo termo da sequência.
- (B) O algoritmo é ótimo, no que diz respeito ao número de passos.
- (C) O número de passos efetuados pelo algoritmo é linear em n.
- (D) O número de passos efetuados pelo algoritmo é polinomial em n.
- (E) O número de passos efetuados pelo algoritmo é exponencial em n.
Resolução
A versão recursiva do algoritmo que calcula o n-ésimo número de Fibonacci de uma dada posição é exponencial. Portanto, a alternativa correta é a E.
Questão 22
Deseja-se efetuar uma busca para localizar uma certa chave fixa x, em uma tabela contendo n elementos. A busca considerada pode ser a linear ou binária. No primeiro caso pode-se considerar que a tabela esteja ordenada ou não. No segundo caso a tabela está, de forma óbvia, ordenada.
Assinale a alternativa CORRETA:
- (A) A busca binária sempre localiza x, efetuando menos comparações que a busca linear.
- (B) A busca linear ordenada sempre localiza x, efetuando menos comparações que a não ordenada.
- (C) A busca linear não ordenada sempre localiza x, com menos comparações que a ordenada.
- (D) A busca binária requer O(log n) comparações, no máximo, para localizar x.
- (E) A busca linear ordenada nunca requer mais do que n/2 comparações para localizar x.
Resolução
Vamos analisar cada alternativa:
(A) É falsa. Suponha que a chave esteja na primeira posição e que a tabela esteja ordenada. Neste caso, a busca linear precisaria de apenas uma comparação e a busca binária precisaria de mais de uma (considerando n > 2).
(B) e (C) são falsas. O fato de o vetor está ordenado ou desordenado não nos permite inferir que uma situação irá requerer menos comparações do que a outra.
(D) É verdadeira.
(E) É falsa. Se a chave de busca estiver na última posição, por exemplo, serão necessárias n comparações.
Portanto, a alternativa correta é a D.
Questão 34
Dado um conjunto C contendo n inteiros distintos, qual das seguintes estruturas de dados em memória principal permite construir um algoritmo para encontrar o valor máximo de C em tempo constante?
- (A) Um vetor não ordenado.
- (B) Um vetor ordenado.
- (C) Uma árvore binária de busca balanceada.
- (D) Uma lista encadeada simples ordenada em ordem crescente.
- (E) Uma árvore rubro-negra.
Resolução
Vamos analisar as alternativas:
(A) É falsa. A busca pelo valor máximo seria feita em tempo O(n), pois você precisaria verificar todos os elementos do vetor.
(B) É verdadeira. O valor máximo estará no final do vetor, portanto basta retornar o valor da última posição, algo que pode ser realizado em tempo O(1), pois o acesso aos elementos de um vetor pode ser feito em tempo constante.
(C) É falsa. A complexidade seria O(log n), isto é, a complexidade é proporcional à altura da árvore.
(D) É falsa. O valor máximo estará no último nó da lista, portanto, o acesso será realizado em tempo O(n). É claro, estamos considerando uma lista simples (sem nó cauda).
(E) É falsa. A justificativa é a mesma de C.
Portanto, a alternativa correta é a B.
POSCOMP 2010
As questões a seguir são do POSCOMP 2010.
Questão 25
Considere dois algoritmos A1 E A2, cujas funções de custo são, respectivamente, T1(n)=n2−n+1 e T2(n)=6nlog2n+2n. Para simplificar a análise, assuma que n>0 é sempre uma potência de 2. Com relação ao enunciado, assinale a alternativa correta.
- (A) Como T1(n)=Θ(n2) e T2(n)=Θ(nlogn), então A2 é sempre mais eficiente que A1.
- (B) O limite superior T1(n)=O(n3) é correto e assintoticamente restrito.
- (C) O limite inferior T2(n)=Ω(n3) é correto e assintoticamente restrito.
- (D) T1 e T2 são assintoticamente equivalentes.
- (E) A1 é mais eficiente que A2, para n suficientemente pequeno.
Resolução
Vamos analisar cada alternativa:
(A) É falsa. Apesar das notações assintóticas estarem corretas, observe, por exemplo, que quando n=1, T1(1)=1 e T2(2)=2, logo, nesse caso, A1 é mais eficiente que A2.
(B) É falsa. O limite está correto, mas não é assintoticamente restrito, pois T1(n) não é Θ(n3).
(C) É falsa. T2(n) não é Ω(n3), pois a função cúbica é assintoticamente superior.
(D) É falsa, pois não há equivalência entre as duas funções.
(E) É verdadeira. Observe que para n=1 e para n=2, por exemplo, o algoritmo A1 é mais eficiente.
Portanto, a alternativa correta é a E.
Questão 27
Considere o problema de ordenação onde os vetores a serem ordenados, de tamanho n > 0, possuem ⌊n/2⌋ valores iguais a um número real x e ⌈n/2⌉ valores iguais a um outro número real y. Considere que os números reais x e y são conhecidos e fixos, porém estão distribuídos aleatoriamente no vetor a ser ordenado.
Neste caso, é correto afirmar:
- (A) Podemos ordenar estes vetores a um custo O(n).
- (B) No caso médio, o Quicksort será o algoritmo mais eficiente para este problema, com um custo O(nlogn).
- (C) O algoritmo de ordenação por inserção sempre opera no melhor caso com um custo O(n).
- (D) O limite inferior para esta classe de problema é Ω(n2).
- (E) O limite inferior para esta classe de problema é Ω(nlogn).
Resolução
Utilizando como base o algoritmo de partição do Quicksort, podemos construir um algoritmo O(n) para resolver o problema.
O menor valor entre x e y será o pivô. Todos os elementos iguais ao pivô devem ficar à esquerda. O algoritmo é apresentado a seguir (pseudocódigo)
1. sort(V[1...n], x, y) 2. | pivô ← min(x, y) 3. | i ← 0 4. | para j ← 1 até n 5. | | se(V[j] = pivô) 6. | | | i ← i + 1 7. | | | trocar(V, i, j) 8. | | fim_se 9. | fim_para 10.fim_sort
O algoritmo foi escrito utilizando como base o algoritmo de partição do Quicksort do livro do Cormen.
Portanto, a alternativa correta é a A.
Referências
CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 2012.
Nenhum comentário:
Postar um comentário