Questões do POSCOMP sobre Complexidade de Algoritmos #03

Por
|  

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.

POSCOMP questões resolvidas

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)=n2n+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.

Sugestões de livros para estudantes de computação na Amazon (patrocinado): Lista de Livros

Obrigado pela leitura! Se você puder, considere apoiar financeiramente o Blog Cyberini, Chave Pix: cyberpix9@gmail.com

Doar com PayPal

Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram, Telegram

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário

Este site usa cookies para fornecer serviços, analisar o tráfego e exibir publicidade personalizada, conforme a nossa política de privacidade. Seus dados, como IP e user agent, são compartilhados com nossos parceiros (como o Google). Saiba Mais

RecusarAceitar