Questões Resolvidas do POSCOMP 2002 (Parte 2)

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

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

Índice

• Questão 30
• Questão 33
• Questão 39
• Questão 40
• Questão 52
• Referências

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: (W₁, W₂, W₃, W₄, W₅) = (6, 10, 9, 5, 12)
valores: (P₁, P₂, P₃, P₄, P₅) = (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.