Questões do ENADE sobre Complexidade de Algoritmos #02

Por
|  

Esta postagem é a continuação da postagem Questões do ENADE sobre Complexidade de Algoritmos #01, onde apresento a resolução de algumas questões do ENADE sobre Complexidade de Algoritmos.

ENADE 2011

A questão a seguir é do ENADE de 2011 de Computação.

Questão 24

As filas de prioridades (heaps) são estruturas de dados importantes no projeto de algoritmos. Em especial, heaps podem ser utilizados na recuperação de informação em grandes bases de dados constituídos por textos. Basicamente, para se exibir o resultado de uma consulta, os documentos recuperados são ordenados de acordo com a relevância presumida para o usuário. Uma consulta pode recuperar milhões de documentos que certamente não serão todos examinados. Na verdade, o usuário examina os primeiros m documentos dos n recuperados, em que m é da ordem de algumas dezenas.

Considerando as características dos heaps e sua aplicação no problema descrito acima, avalie as seguintes afirmações.

  • I) Uma vez que o heap é implementado como uma árvore binária de pesquisa essencialmente completa, o custo computacional para sua construção é $O(n \log n)$.
  • II) A implementação de heaps utilizando-se vetores é eficiente em tempo de execução e em espaço de armazenamento, pois o pai de um elemento armazenado na posição i se encontra armazenado na posição $2i+1$.
  • III) O custo computacional para se recuperar de forma ordenada os m documentos mais relevantes armazenados em um heap de tamanho n é $O(m \log n)$.
  • IV) Determinar o documento com maior valor de relevância armazenado em um heap tem custo computacional $O(1)$.

Estão certos apenas os itens

  • (A) I e II.
  • (B) II e III.
  • (C) III e IV.
  • (D) I, II e IV.
  • (E) I, III e IV.
Resolução

A afirmação I está incorreta. Um heap é uma árvore binária, mas não é de pesquisa. Isto é, um heap não satisfaz a propriedade na qual o filho esquerdo de um nó é menor ou igual ao pai e o filho direito é maior.

A afirmação II está incorreta. O pai do elemento na posição i encontra-se na posição $(i-1)/2$. As afirmações III e IV estão corretas. Portanto, a alternativa C é a correta.

ENADE 2014

As questões a seguir são do ENADE 2014. Em 2014, o INEP separou as provas de Ciência da Computação, Sistemas de Informação e Engenharia da Computação. Anteriormente, as provas desses cursos ficavam num único caderno.

Questão 12 (Ciência da Computação)

Analise o custo computacional dos algoritmos a seguir, que calculam o valor de um polinômio de grau n, da forma: $P(x) = a_nx^n+a_{n-1}x^{n-1}+\ldots +a_1x+a_0$, onde os coeficientes são números de ponto flutuante armazenados no vetor a[0..n], e o valor de n é maior que zero. Todos os coeficientes podem assumir qualquer valor, exceto o coeficiente $a_n$ que é diferente de zero.

Algoritmo 1:

soma = a[0]
Repita para i = 1 até n
   Se a[i] ≠ 0.0 então
      potência = x
      Repita para j = 2 até i
         potência = potência * x
      Fim repita
      soma = soma + a[i] * potencia
   Fim se
Fim repita
Imprima(soma)

Algoritmo 2:

soma = a[n]
Repita para i = n-1 até 0 passo -1
   soma = soma * x + a[i]
Fim repita
Imprima(soma)

Com base nos algoritmos 1 e 2, avalie as asserções a seguir e a relação proposta entre elas.

I. Os algoritmos possuem a mesma complexidade assintótica.

PORQUE

II. Para o melhor caso, ambos os algoritmos possuem complexidade $O(n)$.

A respeito dessas asserções, assinale a opção correta.

  • (A) As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
  • (B) As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
  • (C) A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
  • (D) A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
  • (E) As asserções I e II são proposições falsas.
Resolução

O algoritmo 2 é a regra de Horner, que possui complexidade $O(n)$ em qualquer caso.

O melhor caso do algoritmo 1 ocorre quando todos os coeficientes, exceto $a_n$, são iguais a zero. Nesse caso, teremos n comparações a[i] ≠ 0.0. Quando i = n, os comandos do bloco se são finalmente executados. A complexidade, nesse caso, é dada por

$$\begin{align*}T_2(n) &= n + \sum_{j=2}^n 1\\&=n + (n-1) \\&= 2n-1 \\&= O(n)\end{align*}$$

Portanto, a asserção II é verdadeira. O cálculo anterior considerou apenas as comparações a[i] ≠ 0.0 e as multiplicações do laço de repetição interno. Isso obviamente não influencia na ordem de complexidade.

O pior caso do algoritmo 1 ocorre quando não há coeficientes iguais a zero. Realizando a contagem de multiplicações e das comparações a[i] ≠ 0.0, obtém-se

$$\begin{align*}T_2(n) &= \sum_{i=1}^n \left(1+\sum_{j=2}^i 1\right)\\&=\sum_{i=1}^n(1+i-1)\\&=\sum_{i=1}^n i \\&= \frac{n(n+1)}{2} \\&= O(n^2)\end{align*}$$

Ou seja, os dois algoritmos possuem complexidades diferentes no pior caso. Portanto, a asserção I é falsa, pois a complexidade deveria ser a mesma nos três casos para que isso fosse verdade.

Com isso, concluímos que a alternativa correta é a D.

Questão 22 (Ciência da Computação)

Considere o processo de fabricação de um produto siderúrgico que necessita passar por n tratamentos térmicos e químicos para ficar pronto. Cada uma das n etapas de tratamento é realizada uma única vez na mesma caldeira. Além do custo próprio de cada etapa do tratamento, existe o custo de se passar de uma etapa para outra, uma vez que, dependendo da sequência escolhida, pode ser necessário alterar a temperatura da caldeira e limpá-la para evitar a reação entre os produtos químicos utilizados. Assuma que o processo de fabricação inicia e termina com a caldeira limpa. Deseja-se projetar um algoritmo para indicar a sequência de tratamentos que possibilite fabricar o produto com o menor custo total. Nessa situação, conclui-se que

  • (A) a solução do problema é obtida em tempo de ordem $O(n\log n)$, utilizando-se um algoritmo ótimo de ordenação.
  • (B) uma heurística para a solução do problema de coloração de grafos solucionará o problema em tempo polinomial.
  • (C) o problema se reduz a encontrar a árvore geradora mínima para o conjunto de etapas do processo, requerendo tempo de ordem polinomial para ser solucionado.
  • (D) a utilização do algoritmo de Dijkstra para se determinar o caminho de custo mínimo entre o estado inicial e o final soluciona o problema em tempo polinomial.
  • (E) qualquer algoritmo conhecido para a solução do problema descrito possui ordem de complexidade de tempo não-polinomial, uma vez que o problema do caixeiro viajante se reduz a ele.
Resolução

Cada etapa do tratamento pode ser vista como um vértice de um grafo. A transição entre cada etapa pode ser representada como uma aresta cujo peso é o custo dessa transição.

Na prática, o enunciado deseja um percurso que passe por cada vértice (tratamento) uma única vez, partindo de um vértice inicial (caldeira limpa) e terminando no mesmo vértice, de tal forma que o custo total seja o menor possível.

Em outras palavras, deseja-se a solução do problema do caixeiro viajante, cujo algoritmo para resolver tem complexidade exponencial.

Portanto, a alternativa correta é a E.

Questão 10 (Sistemas de Informação)

A área de complexidade de algoritmos abrange a medição da eficiência de um algoritmo frente à quantidade de operações realizadas até que ele encontre seu resultado final.

A respeito desse contexto, suponha que um arquivo texto contenha o nome de N cidades de determinado estado, que cada nome de cidade esteja separado do seguinte por um caracter especial de fim de linha e classificado em ordem alfabética crescente. Considere um programa que realize a leitura linha a linha desse arquivo, à procura de nome de cidade.

Com base nessa descrição, verifica-se que a complexidade desse programa é

  • (A) O(1), em caso de busca sequencial.
  • (B) O(N), em caso de busca sequencial.
  • (C) $O(\log_2 N)$, em caso de busca binária.
  • (D) O(N), em caso de transferência dos nomes para uma árvore binária e, então, realizar a busca.
  • (E) $O(\log_2 N)$, em caso de transferência dos nomes para uma árvore binária e, então, realizar a busca.
Resolução

Como o programa faz a leitura linha a linha, então trata-se de uma busca sequencial (ou linear), que verifica cada elemento do conjunto de dados (lista de nomes) até encontrar o elemento procurado. Tal busca tem complexidade O(n). Logo, a alternativa correta é a B.

Nota

Para mais postagens sobre provas do ENADE de computação, acesse a tag .

Se você também tiver interesse em questões sobre o POSCOMP, acesse a tag .

Siga o blog por e-mail

Receba notificações de novas postagens e novidades do blog por e-mail.

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