Questões Resolvidas do POSCOMP 2002 (Parte 2)

Por
| 

Esta postagem é a segunda parte das postagens com a resolução de questões do POSCOMP 2002.

Questões Resolvidas do POSCOMP 2002 Parte 2

Na primeira parte, eu resolvi todas as questões entre 21 e 29.

Índice

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

Questão 30

Assunto: paradigmas de projeto de algoritmos.

Considere um problema em que são dados 5 objetos com os seguintes pesos e valores:

pesos: (W1, W2, W3, W4, W5) = (6, 10, 9, 5, 12)
valores: (P1, P2, P3, P4, P5) = (8, 5, 10, 15, 7).

Além disso, é dada uma mochila que suporta até 30 unidades de peso, para transportar os objetos. O objetivo do problema é preencher a mochila de tal forma que o valor total dos objetos a serem transportados seja o maior possível, mas sem exceder o limite de peso suportado pela mochila. Qual das seguintes alternativas corresponde ao valor máximo obtido no preenchimento da mochila:

  • (A) 12.2
  • (B) 21.5
  • (C) 30.34
  • (D) 38.83
  • (E) 43.1

Resolução

O problema pode ser resolvido utilizando o algoritmo da mochila fracionada.

Primeiramente, tentamos inserir o objeto de maior valor, que tem preço igual a 15 e o peso é 5 (peso restante: 25, valor total: 15).

O segundo objeto com o maior valor tem preço 10 e peso 9 (peso restante: 16, valor total: 25).

O terceiro objeto com o maior valor tem preço 8 e peso 6 (peso restante: 10, valor total: 33).

O quarto objeto com o maior valor tem preço 7 e peso 12, porém restam apenas 10 unidades de peso na mochila. O valor correspondente a 10 unidades de peso desse objeto pode ser obtido através da regra de três

$$\begin{align*}12x&= 7\times 10\\12x&=70\\x&=\frac {70}{12}\\x&\cong 5.83\end{align*}$$

Com isso, o valor total é $33+5.83=38.83$, que é o valor máximo que podemos obter preenchendo a mochila.

Portanto, a alternativa correta é a D.

Ir para o índice

Questão 33

Assunto: complexidade de algoritmos.

Professor Mac Sperto propôs o seguinte algoritmo de ordenação, chamado de Super Merge, similar ao merge sort: divida o vetor em 4 partes do mesmo tamanho (ao invés de 2, como é feito no merge sort). Ordene recursivamente cada uma das partes e depois intercale-as por um procedimento semelhante ao procedimento de intercalação do merge sort. Qual das alternativas abaixo é verdadeira?

  • (A) Super Merge não está correto. Não é possível ordenar quebrando o vetor em 4 partes
  • (B) Super Merge está correto, mas consome tempo O(merge sort)
  • (C) Super Merge está correto, mas consome tempo maior que O(merge sort)
  • (D) Super Merge está correto, mas consome tempo menor que O(merge sort)
  • (E) Nenhuma das afirmações acima está correta

Resolução

A partir das informações do enunciado, é possível concluir que a equação de recorrência do algoritmo proposto é

$$T(n)=4T(n/4)+\Theta(n)$$

O primeiro termo representa o tempo para ordenar as 4 partes do vetor recursivamente. O segundo termo é o tempo necessário para intercalar os 4 vetores, que possuem comprimento aproximadamente igual a $n/4$.

Aplicando o teorema mestre ou o método de Akra-Bazzi, podemos resolver essa recorrência. Optaremos pelo teorema mestre.

De acordo com o teorema, temos que $a=4,\, b=4,\, f(n)=\Theta(n)$. Além disso, $n^{\log_b a}=n^{\log_4 4}=n$. Portanto, a recorrência satisfaz segundo caso do teorema mestre, pois $f(n)=\Theta\left(n^{\log_b a}\right)$.

Ou seja, $T(n)=\Theta\left(n^{\log_b a}\log n\right)=\Theta(n\log n)$. Dessa forma, concluímos que o algoritmo do professor Mac Sperto tem a mesma complexidade do Merge Sort.

Logo, a opção certa é a B.

Ir para o índice

Questão 39

Assunto: teoria dos grafos.

O menor número possível de arestas em um grafo conexo com n vértices é:

  • (A) 1
  • (B) n/2
  • (C) n - 1
  • (D) n
  • (E) n2

Resolução

Em Teoria dos Grafos, há um teorema que diz que um grafo conexo com o menor número de arestas é uma árvore e, consequentemente, possui n-1 arestas.

Logo, a opção certa é a C.

Ir para o índice

Questão 40

Assunto: teoria dos grafos.

Considere um grafo G satisfazendo as seguintes propriedades:

  • G é conexo
  • Se removemos qualquer aresta de G, o grafo obtido é desconexo.

Então é correto afirmar que o grafo G é:

  • (A) Um circuito
  • (B) Não bipartido
  • (C) Uma árvore
  • (D) Hamiltoniano
  • (E) Euleriano

Resolução

Se um grafo conexo se torna desconexo ao remover qualquer uma das suas arestas, então o grafo é uma árvore. Isso é provado via teorema.

Portanto, a alternativa correta é a C.

Ir para o índice

Questão 52

Assunto: computação gráfica.

Filtro da mediana é:

  • (A) Indicado para detectar bordas em imagens.
  • (B) Indicado para atenuar ruído com preservação de bordas (i.e rápidas transições de nível em imagens).
  • (C) Indicado para detectar formas específicas em imagens.
  • (D) Indicado para detectar tonalidades específicas em uma imagem.
  • (E) Nenhuma das respostas acima.

Resolução

O filtro da mediana é utilizado para atenuar ruídos da imagem. Particularmente, esse filtro é utilizado para atenuação do ruído "sal e pimenta" e uma de suas propriedades é a capacidade de preservar detalhes da imagem, como as bordas [1].

Portanto, a alternativa correta é a B.

Ir para o índice

Referências

  • [1] FISHER R.; PERKINS S.; WALKER A.; WOLFART E. (2003). Median Filter. Acesso em 27 de março 2018.

Siga o blog

Redes sociais: Facebook, Twitter, Google+, YouTube, Pinterest, Instagram

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