Questões do POSCOMP sobre Complexidade de Algoritmos #04

Por
|  

As questões desta postagem são das provas do POSCOMP 2012 e 2013 sobre Complexidade de Algoritmos.

POSCOMP questões resolvidas de complexidade de algoritmos

Para mais questões resolvidas, acesse a página POSCOMP.

POSCOMP 2012

As questões a seguir são do POSCOMP 2012.

Para as questões 21 e 22 deve-se considerar o algoritmo a seguir.

O algoritmo ALGSORT ordena vetores de números inteiros distintos usando apenas comparações. Nesse algoritmo, a função menor(V, i, j) retorna o índice l, tal que V[l] é o menor número no vetor V[i..j]. O custo de tempo de pior caso de menor(V, i, j) é igual a j − i comparações. De forma similar, a função maior(V, i, j) retorna um índice g, tal que V[g] é o maior número no vetor V[i..j], também com custo de execução de j − i comparações no pior caso. Para ordenar o vetor X[1..n], ALGSORT(V, i, j) é chamado com os parâmetros, V = X, i = 1 e j = n.

ALGSORT (V,i,j);
(1) Se j-i=0 então retorne;
(2) Se j-i=1 então
      Se V[j] < V[i] então
         Troque(V[j],V[i]);
      Fim;
      retorne;
   Fim;
(3) l = menor(V,i,j);
(4) Troque(V[i],V[l]);
(5) g = maior(V,i,j);
(6) Troque(V[j],V[g]);
(7) ALGSORT (V,i+1,j-1);

Questão 21

A função que caracteriza o custo de tempo de pior caso, T(n), para a chamada ALGSORT(X, 1, n) é dada por:

  • (A) T(n)=T(n1)+2n2
  • (B) T(n)=T(n2)+2n2
  • (C) T(n)=T(n2)+n1
  • (D) T(n)=T(n2)+(n1)2
  • (E) T(n)=T(n2)2+2n
Resolução

Para a chamada ALGSORT(V, 1, n) as linhas 3 e 5 contabilizarão n1 comparações, cada uma, totalizando 2n2.

Na linha 7, é feita a chamada recursiva do algoritmo, porém com outros parâmetros: ALGSORT(V, 2, n-1). Houve uma redução de duas unidades no intervalo. Portanto, a quantidade de comparações será T(n2).

Somando as expressões, temos

T(n)=T(n2)+2n2

Portanto, a alternativa B é a correta.

Questão 22

Com relação ao projeto do algoritmo ALGSORT, assinale a alternativa correta.

  • (A) O custo de combinação de ALGSORT é O(n) em função do tamanho da entrada para a chamada ALGSORT(X, 1, n).
  • (B) Modificando o trecho das linhas de (3) a (6) de ALGSORT, é possível obter um algoritmo assintoticamente menos custoso.
  • (C) O tempo de execução para a chamada ALGSORT(X, 1, n) em função de n é O(nlgn).
  • (D) O tempo de execução de ALGSORT é Θ(n2) em função de n para a chamada ALGSORT(X, 1, n).
  • (E) O custo do caso base n=1 para a chamada ALGSORT(X, 1, n) em função de n é T(n)=1.
Resolução

Basicamente, devemos resolver a equação de recorrência anterior para responder a questão

T(n)=T(n2)+2(n1)=T(n4)+2(n3)+2(n1)=T(n6)+2(n5)+2(n3)+2(n1)=T(n2k)+ki=02(n2i1)

O valor de k é determinado pelo caso base. Quando n é ímpar, o caso base é T(1)=1. Dessa forma,

T(n2k)=T(1)n2k=1k=n12

Continuando os cálculos, temos

T(n)=T(1)+2n12i=0(n2i1)=1+12(n21)=12(n2+1)

A fórmula obtida só é válida para n ímpar. Para n par, teríamos que mudar o caso base para T(2)=1. Porém, o resultado também seria um polinômio do segundo grau.

Logo, T(n)=Θ(n2) e a alternativa correta é a D.

Questão 23

Em relação à pesquisa sequencial e binária, assinale a alternativa correta.

  • (A) A pesquisa binária em média percorre a metade dos elementos do vetor.
  • (B) A pesquisa binária percorre no pior caso log2n elementos.
  • (C) A pesquisa binária pode ser feita sobre qualquer distribuição dos elementos.
  • (D) A pesquisa sequencial exige que os elementos estejam completamente ordenados.
  • (E) A pesquisa sequencial percorre todos os elementos para encontrar a chave.
Resolução

A alternativa A é falsa. A pesquisa binária percorre em média log2n elementos.

A alternativa C é falsa, pois a pesquisa binária só funciona se o conjunto de dados estiver ordenado.

D também é uma alternativa falsa, pois a pesquisa sequencial funciona em qualquer conjunto de dados, estando ordenado ou não.

A alternativa E é falsa, pois, quando a chave é encontrada, a pesquisa termina. Portanto, se o elemento não estiver na última posição, então nem todos os elementos serão percorridos.

Ou seja, somente a alternativa B está correta.

Questão 39

Com relação a técnicas de pesquisa em arquivos, assinale a alternativa correta.

  • (A) Para a pesquisa binária funcionar, o arquivo precisa estar ordenado de acordo com algum campo aleatório.
  • (B) Para a pesquisa sequencial funcionar, o arquivo precisa estar ordenado.
  • (C) Para a pequisa binária funcionar, o arquivo precisa estar ordenado de acordo com o campo de busca.
  • (D) Para as pesquisas sequencial e binária funcionarem, o arquivo precisa estar ordenado de acordo com o campo de busca.
  • (E) Para as pesquisas sequencial e binária funcionarem, o arquivo não precisa estar ordenado.
Resolução

Outra questão sobre algoritmos de ordenação. Também vamos analisar cada alternativa.

A) É falsa. O arquivo precisa estar ordenado de acordo com o campo de busca e não de acordo com um campo aleatório.

B) Falsa, pois o arquivo não precisa estar ordenado.

D) Falsa. A pesquisa sequencial não requer que o arquivo esteja ordenado.

E) É falsa porque a pesquisa binária exige que o arquivo esteja ordenado.

Portanto, a alternativa correta é a C.

POSCOMP 2013

A questão a seguir é do POSCOMP 2013.

Questão 1

Um determinado serviço pode ser realizado por dois programas distintos, P1 e P2, utilizando algoritmos diferentes. O usuário fornece aos programas um número natural n0 e os programas fornecem uma resposta. O tempo que o programa P1 demora para responder é dado pela fórmula T1(n)=n4. Já o tempo da resposta do programa P2 é calculado por T2(n)=2n1. Em relação aos programas P1 e P2, assinale a alternativa correta.

  • (A) Como limnT2(n)=limnT1(n)=, então limnT2(n)T1(n)=limnT2(n)limnT1(n)=1 e, por isso, o programa P2 é mais rápido que o programa P1 para entradas maiores do que um certo número natural N.
  • (B) Como limnT2(n)=limnT1(n)=, então limn(T2(n)T1(n))=limnT2(n)limnT1(n)=0 e, por isso, ambos os programas levam o mesmo tempo para dar uma resposta.
  • (C) Como limnT2(n)=limnT1(n)=, então, a partir de um certo número natural N, ambos os programas levam o mesmo tempo para dar uma resposta.
  • (D) Como limn[T2(n)T1(n)]=, então o programa P1 é mais rápido que o programa P2 para entradas maiores do que um certo número natural N.
  • (E) Como limn[T2(n)T1(n)]=, então o programa P2 é mais rápido que o programa P1 para entradas maiores do que um certo número natural N.
Resolução

Por incrível que pareça, você não precisa se preocupar com os limites para resolver a questão. Basta observar que P2 é um programa com tempo exponencial e que P1 é um programa com tempo polinomial.

Vamos analisar as alternativas, pois ficará mais claro:

A) É falsa, pois afirma-se que P2 (exponencial) é mais rápido que P1 (polinomial). Só isso já invalida a alternativa. Além disso, o limite do quociente entre T2 e T1 está errado.

B) É falsa. Os dois programas não possuem o mesmo tempo de resposta. O limite da diferença T2 e T1 também está errado.

C) É falsa. Os dois programas não possuem o mesmo tempo de resposta.

E) É falsa. P2 não é mais rápido do que P1.

A alternativa D é a correta.

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