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(n2)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(nlgn). - (D) O tempo de execução de
ALGSORT
é Θ(n2) 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
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)+k∑i=02(n−2i−1)
O valor de k é determinado pelo caso base. Quando n é ímpar, o caso base é T(1)=1. Dessa forma,
T(n−2k)=T(1)n−2k=1k=n−12
Continuando os cálculos, temos
T(n)=T(1)+2n−12∑i=0(n−2i−1)=1+12(n2−1)=12(n2+1)
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)=Θ(n2) 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 log2n 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 log2n 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, P1 e P2, utilizando algoritmos diferentes. O usuário fornece aos programas um número natural n≥0 e os programas fornecem uma resposta. O tempo que o programa P1 demora para responder é dado pela fórmula T1(n)=n4. Já o tempo da resposta do programa P2 é calculado por T2(n)=2n−1. Em relação aos programas P1 e P2, assinale a alternativa correta.
- (A) Como limn→∞T2(n)=limn→∞T1(n)=∞, então limn→∞T2(n)T1(n)=limn→∞T2(n)limn→∞T1(n)=1 e, por isso, o programa P2 é mais rápido que o programa P1 para entradas maiores do que um certo número natural N.
- (B) Como limn→∞T2(n)=limn→∞T1(n)=∞, então limn→∞(T2(n)−T1(n))=limn→∞T2(n)−limn→∞T1(n)=0 e, por isso, ambos os programas levam o mesmo tempo para dar uma resposta.
- (C) Como limn→∞T2(n)=limn→∞T1(n)=∞, então, a partir de um certo número natural N, ambos os programas levam o mesmo tempo para dar uma resposta.
- (D) Como limn→∞[T2(n)−T1(n)]=∞, então o programa P1 é mais rápido que o programa P2 para entradas maiores do que um certo número natural N.
- (E) Como limn→∞[T2(n)−T1(n)]=∞, então o programa P2 é mais rápido que o programa P1 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 P2 é um programa com tempo exponencial e que P1 é um programa com tempo polinomial.
Vamos analisar as alternativas, pois ficará mais claro:
A) É falsa, pois afirma-se que P2 (exponencial) é mais rápido que P1 (polinomial). Só isso já invalida a alternativa. Além disso, o limite do quociente entre T2 e T1 está errado.
B) É falsa. Os dois programas não possuem o mesmo tempo de resposta. O limite da diferença T2 e T1 também está errado.
C) É falsa. Os dois programas não possuem o mesmo tempo de resposta.
E) É falsa. P2 não é mais rápido do que P1.
A alternativa D é a correta.
Nenhum comentário:
Postar um comentário