Questões do POSCOMP sobre Complexidade de Algoritmos #04

As questões desta postagem são das provas do POSCOMP 2012 e 2013 sobre 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(n − 1) + 2n − 2$
• (B) $T(n) = T(n − 2) + 2n − 2$
• (C) $T(n) = T(n − 2) + n − 1$
• (D) $T(n) = T(n − 2) + (n − 1)^2$
• (E) $T(n) = T\left(\cfrac{n}{2}\right) 2 + 2n$

Resolução

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

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(n-2)$.

Somando as expressões, temos

$$T(n)=T(n-2)+2n-2$$

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(n\lg n)$.
• (D) O tempo de execução de ALGSORT é $\Theta(n^2)$ 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

$$\begin {align*}T(n)&=T(n-2)+2(n-1)\\&=T(n-4)+2(n-3)+2(n-1)\\&=T(n-6)+2(n-5)+2(n-3)+2(n-1)\\&=T(n-2k)+\sum_{i=0}^{k} 2(n-2i-1)\end {align*}$$

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

$$\begin {align*}T(n-2k)=T(1)\\n-2k=1\\k=\frac{n-1}{2}\end {align*}$$

Continuando os cálculos, temos

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

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)=\Theta(n^2)$ 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 $\log_2 n$ 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 $\log_2 n$ 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, $P_1$ e $P_2$, utilizando algoritmos diferentes. O usuário fornece aos programas um número natural $n\geq 0$ e os programas fornecem uma resposta. O tempo que o programa $P_1$ demora para responder é dado pela fórmula $T_1(n) = n^4$. Já o tempo da resposta do programa $P_2$ é calculado por $T_2(n) = 2^{n−1}$. Em relação aos programas $P_1$ e $P_2$, assinale a alternativa correta.

• (A) Como $\lim_{n\rightarrow\infty} T_2(n)=\lim_{n\rightarrow\infty} T_1(n)=\infty$, então $\lim_{n\rightarrow\infty}\cfrac{T_2(n)}{T_1(n)}=\cfrac{\lim_{n\rightarrow\infty}T_2(n)}{\lim_{n\rightarrow\infty}T_1(n)} = 1$ e, por isso, o programa $P_2$ é mais rápido que o programa $P_1$ para entradas maiores do que um certo número natural $N$.
• (B) Como $\lim_{n\rightarrow\infty} T_2(n)=\lim_{n\rightarrow\infty} T_1(n)=\infty$, então $\lim_{n\rightarrow\infty}(T_2(n)-T_1(n))=\lim_{n\rightarrow\infty}T_2(n)-\lim_{n\rightarrow\infty}T_1(n)=0$ e, por isso, ambos os programas levam o mesmo tempo para dar uma resposta.
• (C) Como $\lim_{n\rightarrow\infty} T_2(n)=\lim_{n\rightarrow\infty} T_1(n)=\infty$, então, a partir de um certo número natural $N$, ambos os programas levam o mesmo tempo para dar uma resposta.
• (D) Como $\lim_{n\rightarrow\infty}\left[T_2(n)-T_1(n)\right]=\infty$, então o programa $P_1$ é mais rápido que o programa $P_2$ para entradas maiores do que um certo número natural $N$.
• (E) Como $\lim_{n\rightarrow\infty}\left[T_2(n)-T_1(n)\right]=\infty$, então o programa $P_2$ é mais rápido que o programa $P_1$ 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 $P_2$ é um programa com tempo exponencial e que $P_1$ é um programa com tempo polinomial.

Vamos analisar as alternativas, pois ficará mais claro:

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

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

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

E) É falsa. $P_2$ não é mais rápido do que $P_1$.

A alternativa D é a correta.