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 chamadaALGSORT(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 chamadaALGSORT(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.
Nenhum comentário:
Postar um comentário