Analise de algoritmos

Prévia do material em texto

Pergunta 1
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
Um típico problema em que algoritmos gulosos são aplicados é conhecido
comoagendamento para minimizar o tempo médio de finalização. Várias
estratégias têm sido propostas para oferecer uma solução em tempo
computacionalmente viável. Suponha um conjunto S = { a1, a2, …, an } de
tarefas, em que cada tarefa aidemanda pi unidades de tempo para ser concluída
a partir do momento em que é iniciada. As tarefas podem ser executadas
apenas uma por vez. Seja ci o tempo de finalização da tarefa ai, isto é, o tempo
em que a tarefa ai completa seu processamento.
 
Considerando que o objetivo é minimizar o tempo médio para finalização de
todas as tarefas, ou seja, minimizar , analise as afirmativas a seguir e assinale V
para a(s) verdadeira(s) e F para a(s) falsa(s).
 
I. ( ) Se as tarefas forem ordenadas pela quantidade de unidades de tempo para
serem finalizadas (pi), então a complexidade do algoritmo será O(n log n).
II. ( ) Um algoritmo guloso que processa as tarefas em ordem crescente de
piobtém a solução ótima para qualquer conjunto de tarefas.
III. ( ) Considerando S composto apenas de duas tarefas a1 e a2 com p1 = 3 e
p2 = 5, o tempo médio de finalização de S é independente da ordem de
execução das tarefas.
IV. ( ) Uma solução gulosa, baseada no tempo de processamento de cada tarefa,
apresenta uma estrutura local ótima em cada iteração.
 
Agora, assinale a alternativa que apresenta a sequência correta.
V, V, F, V.
V, V, F, V.
Resposta certa. Considerando S composto apenas de duas tarefas
a1 e a2 com p1 = 3 e p2 = 5, temos que, quando a2 é executada
primeiro que a1, o tempo médio para finalização de S é dado por (5
+ 8) / 2 = 6.5. Porém, quando a ordem de execução é inversa,
temos que o tempo médio é (3 + 8) / 2 = 5.5. Considerando a
ordenação das tarefas pela quantidade de unidades de tempo para
serem finalizadas (pi), o tempo de execução do algoritmo será
dominado superiormente por essa operação. Como não é possível
definir um valor máximo para todos os pi possíveis, então a
ordenação não pode ser feita em tempo linear. Nesse caso,
algoritmos como Merge Sort ou Quick Sort podem ser empregados
a fim de se alcançar o melhor desempenho na ordenação, ou seja,
O(n log n).
Pergunta 2
1 em 1 pontos
1 em 1 pontos
Resposta
Selecionada:
Resposta
Correta:
Comentário
da resposta:
O algoritmo counting sort tem larga aplicabilidade pelo seu desempenho linear
na ordenação de dados em memória. No entanto, o maior consumo de espaço
em memória pode restringir seu uso em determinados cenários. Outra
característica é sua estabilidade quanto ao posicionamento de elementos com o
mesmo valor.
 
Considerando que um vetor A de n posições é passado como parâmetro para o
algoritmo counting sort e que dois elementos nas posições i e j têm o mesmo
valor k (A[ i ] = A[ j ] = k), assinale a alternativa correta quanto ao funcionamento
do algoritmo. Assuma que um vetor B é retornado pelo algoritmo.
 
O algoritmo é estável, porque a posição C[ k ] do vetor auxiliar C é
decrementada após a alocação de k em B, e não é mais
incrementada.
O algoritmo é estável, porque a posição C[ k ] do vetor auxiliar C é
decrementada após a alocação de k em B, e não é mais
incrementada.
Resposta certa. Suponha que as posições i e j com i <j contenham
algum elemento k. Considere o último laço do algoritmo counting
sort, responsável pela construção do vetor B de saída. Como j > i,
o laço examina A[ j ] antes de examinar A[ i ]. Ao fazer isso, o
algoritmo coloca corretamente A[ j ] na posição m = C [ k ] de B.
Como C[ k ] é decrementado na linha 10 e nunca mais é
incrementado, temos a garantia de que quando o laço for examinar
A[ i ], teremos C[ k ] < m. Portanto, A[ i ] será colocado em uma
posição anterior no vetor de saída B, provando a estabilidade do
algoritmo.
Pergunta 3
h(“x ← 0”) = verdadeiro
h(“enquanto verdadeiro faça x ← 1”) = falso
Os conceitos de computabilidade de problemas são essenciais para a definição
de soluções que possam atender tanto a cenários teóricos como práticos. Em
particular, é importante dar atenção à decidibilidade dos problemas, já que ela
pode inviabilizar qualquer implementação computacional.
 
Nesse contexto, considere a função h: P → B, em que P é um tipo de dado que
representa um programa e B um tipo de dado booleano (verdadeiro ou falso).
Quando h é aplicada a um programa que termina, ela retorna verdadeiro;
quando aplicada a um programa que não termina, o resultado é falso. Por
exemplo:
 
Tendo como base a função h descrita, e considerando os conteúdo estudado,
analise as asserções a seguir e a relação proposta entre elas.
 
I. A função h é computável.
1 em 1 pontos
Resposta Selecionada:
 
Resposta Correta:
 
Comentário
da resposta:
Porque:
II. Ela é capaz de retornar uma saída para qualquer instância de problema, em
um número finito de passos.
 
A seguir, assinale a alternativa correta.
As asserções I e II são proposições falsas.
 
As asserções I e II são proposições falsas.
 
H(“x ← 0”) = verdadeiro
H(“enquanto verdadeiro faça x ← 1”) = falso.
Resposta certa. Se for assumido que h é computável, então um
programa H que computa a função h pode ser escrito de modo
que:
Nesse caso, é possível definir um programa D como segue
D = “se H(D) então,
 enquanto verdadeiro, faça x ← 1
 se não x ← 0”.
Então, como o programa H aceita qualquer entrada, é possível
para ele uma instância de si próprio, tendo o programa D como
parâmetro, ou seja, H(H(D)). Logo, se H(D) é verdadeiro, então D
representa um programa que é equivalente a
“enquanto verdadeirofaça x ← 1”, cuja execução não termina e,
portanto, H(D) é falso. Por outro lado, se H(D) é falso, então D representa
um programa equivalente a “x ← 0”, cuja execução termina e, portanto,
H(D) é verdadeiro. Dessa forma, uma inconsistência é obtida.
Consequentemente, pode-se afirmar que o programa H não existe, o que,
por sua vez, leva à conclusão de que a função h não retorna para
qualquer instância e não é computável.
Pergunta 4
Conhecer os detalhes de funcionamento dos algoritmos mais tradicionais é
importante, para que as ideias implementadas por eles possam ser aproveitadas
na solução de problemas correlatos. Esse é o caso das estratégias empregadas
na ordenação linear de dados em memória.
 
Considerando esse contexto, analise as asserções a seguir e a relação proposta
entre elas.
 
I. Dado um conjunto de n inteiros no intervalo de 0 a k, é possível construir um
algoritmo que aprimore a entrada em um tempo Θ(n + k) e que responda
quantos números existem no intervalo [a ... b] em um tempo O(1).
Porque:
II. O aprimoramento da entrada, ou pré-processamento, pode ser feito com base
no algoritmo counting sort e a obtenção da quantidade de números no intervalo
informado acontece por meio de uma operação computacional elementar.
1 em 1 pontos
Resposta
Selecionada:
Resposta
Correta:
Comentário
da resposta:
As asserções I e II são proposições verdadeiras, e a II é uma
justificativa correta da I.
As asserções I e II são proposições verdadeiras, e a II é uma
justificativa correta da I.
Resposta certa. O algoritmo pode começar com os primeiros
passos executados pelo counting sort. Nesse caso, os três
primeiros laços atuarão no aprimoramento da entrada, o que
demandará um custo Θ(n + k), assim como o algoritmo counting
sort. Logo, o vetor auxiliar C, utilizado pelo algoritmo, conterá em
cada posição C[ i ] o número de elementos menores ou iguais a i
no vetor original. Para obter a quantidade de números presentes
no intervalo [a ... b], uma operação elementar de subtração C[ b ] -
C[ a - 1 ] pode ser executada. Nesse caso, ela demandará um
tempo O(1).
Pergunta 5
Algoritmos gulosos constituem uma poderosa ferramenta para a solução de
problemas em um tempo computacionalmente viável. No entanto, dependendo
das características do problema, estratégias gulosas não são capazes de
alcançar soluções ótimas. Um exemplo é o problema de devolver um valor
(troco) com o uso da menorquantidade de moedas possível.
 
Algoritmo Troco em Moedas
Entrada: Um inteiro n e um conjunto de moedas (c1, c2, …, cr) com
c1 > c2 > … > cr.
Saída: Conjunto de moedas (d1, d2, …, dr) tal que e k é mínimo
1. C ← ∅
2. para i = 1, …, r faça
3. enquanto n ≥ ci faça
4. C ← C ∪ { ci }
5. n ← n - ci
6. retorna C
 
 
Considerando o algoritmo guloso apresentado para esse problema, analise as
afirmativas a seguir.
 
I. A execução do algoritmo com os parâmetros (c1 = 20, c2 = 15, c3 = 7, c4 = 1) e
n = 22 produz uma solução ótima.
II. Para n = 48 e (c1 = 25, c2 = 10, c3 = 5, c4 = 1), nenhuma moeda c3 comporá a
solução final.
III. A complexidade O(n) do algoritmo constitui o melhor desempenho
conseguido para esse tipo de problema.
IV. O algoritmo sempre obtém a solução ótima para o conjunto de moeda (c1 =
25, c2 = 10, c3 = 5, c4 = 1).
1 em 1 pontos
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
 
Está correto o que se afirma em:
II e IV.
II e IV.
a1 = ⌊n/c1⌋ e nq = n mod c1
a2 = ⌊nq/c2⌋ e nd = nq mod c2
a3 = ⌊nd/c3⌋ e nk = nq mod c2
a4 = nk
Resposta certa. Para as entradas (c1 = 20, c2 = 15, c3 = 7, c4 = 1)
en = 22, o algoritmo não produz a solução ótima, já que ele vai retornar o
conjunto C = { c1, c4, c4 } de 3 moedas, enquanto a solução ótima é C = {
c2, c3 } de 2 moedas. Para as entradas n = 48 e (c1 = 25, c2 = 10, c3 = 5,
c4 = 1), a solução produzida pelo algoritmo é C = { c1, c2, c2, c1, c1, c1 }
e não contém a moeda c3. Embora o algoritmo tenha complexidade O(n),
uma versão dele com desempenho O(1) pode ser obtida com as seguintes
operações:
O conjunto final C será { a1 × d1, a2 × d2, a3 × d3, a4 × d4 }.
Finalmente, para o conjunto de moedas (c1 = 25, c2 = 10, c3 = 5,
c4= 1) o algoritmo sempre obtém a solução ótima.
Pergunta 6
Resposta
Selecionada:
Resposta Correta:
Vários problemas que surgem em contextos práticos demandam análises
elaboradas, para que uma solução possa ser proposta. E, muitas vezes, o
conceito de computabilidade precisa ser considerado, já que a característica do
problema pode impactar na elaboração de uma solução computacional.
 
Nesse contexto, e considerando os conteúdos estudados sobre problemas P e
NP, analise as asserções a seguir e a relação proposta entre elas.
 
I. O problema de analisar centenas de milhares de registros para verificar quais
deles totalizam um dado valor pode ser resolvido em tempo polinomial.
Porque:
II. Um procedimento computacional simples pode ser construído para somar
esses registros e responder se o valor contabilizado é igual ao valor informado.
 
A seguir, assinale a alternativa correta:
A asserção I é uma proposição falsa, e a II é uma proposição
verdadeira.
1 em 1 pontos
Comentário
da resposta:
A asserção I é uma proposição falsa, e a II é uma proposição
verdadeira.
Resposta certa. A respeito da complexidade do problema, é
preciso identificar que se trata de procurar, dentro de um conjunto
de números (registros), quais subconjuntos somam certo valor (o
valor informado). Dentro da teoria da computabilidade, esse
problema é conhecido como o problema da soma de
subconjunto, e ele pertence à classe dos problemas NP. Logo, não
se conhece ainda um algoritmo capaz de resolver esse problema
em um tempo polinomial. Logo, a primeira asserção é falsa.
Porém, outra característica dos problemas NP é que eles podem
ser verificados em tempo polinomial. Por isso, é possível
implementar um procedimento computacional simples para somar
esses registros e responder se o valor contabilizado é igual ao
valor suspeito. Logo, a segunda asserção é verdadeira.
Pergunta 7
Resposta
Selecionada:
Resposta
Correta:
Comentário
da resposta:
As classes de computabilidade possibilitam que os problemas sejam
organizados de acordo com as suas características de tratabilidade
computacional. Conhecer as relações entre essas classes e os problemas
categorizados nelas é de grande importância para projetar algoritmos que
possam ser aplicados em cenários reais.
 
Considere um problema Y que pode ser resolvido usando um número polinomial de
passos computacionais, acrescido de um número polinomial de chamadas a um outro
problema X. Essa relação pode ser denotada por Y ≤p X. Isso quer dizer que X é pelo
menos tão difícil quanto Y com relação ao tempo polinomial. Sabendo que, se X
pode ser resolvido em tempo polinomial, isso vai implicar que Y também pode
ser resolvido em tempo polinomial, analise as asserções a seguir e a relação
proposta entre elas.
 
I. Se X é um problema NP-completo, então X pode ser resolvido em tempo
polinomial se, e somente se, P = NP.
Porque:
II. Nesse caso, qualquer outro problema Y pertencente a NP poderá ser
resolvido em tempo polinomial.
 
A seguir, assinale a alternativa correta.
As asserções I e II são proposições verdadeiras, e a II é uma
justificativa correta da I.
As asserções I e II são proposições verdadeiras, e a II é uma
justificativa correta da I.
Resposta certa. Observa-se que, se P = NP, então X pode ser resolvido em
tempo polinomial, já que X pertence à classe NP. Inversamente, suponha
1 em 1 pontos
que X possa ser resolvido em tempo polinomial. Se Y é qualquer outro
problema em NP, então Y ≤p X e, como por hipótese, se X pode ser
resolvido em tempo polinomial, então Y também pode, logo, temos
que Y pode ser resolvido em tempo polinomial.
Consequentemente, temos que NP ⊆P. Mas, como é provado que
P ⊆NP, concluímos que P = NP.
Pergunta 8
Resposta
Selecionada:
Resposta
Correta:
Comentário
da resposta:
Os problemas que precisam ser resolvidos computacionalmente podem ser
classificados de acordo com a sua computabilidade. Essa classificação é
importante, considerando que ela tem efeito direto sobre a viabilidade de
construção de um algoritmo útil em cenários práticos.
 
Considerando essas informações e os conteúdos estudados, assinale a
alternativa correta a respeito dessa classificação de problemas.
A descoberta de um algoritmo polinomial para um problema NP-
completo pode tornar a igualdade P = NP verdadeira.
A descoberta de um algoritmo polinomial para um problema NP-
completo pode tornar a igualdade P = NP verdadeira.
Resposta certa. O problema de encontrar uma rota ótima visitando
pontos específicos uma única vez é uma aplicação do problema do
Caixeiro Viajante, que é da classe NP. Problemas da classe NP-
difícil satisfazem apenas uma condição dos problemas da classe
NP (problemas NP-completo satisfazem às duas condições e são
NP-difíceis), ou seja, se um algoritmo polinomial for encontrado
para ele, então todos os problemas NP poderão ser reduzidos a
esse problema, o que possibilitará que estes sejam resolvidos em
tempo polinomial.
Pergunta 9
A construção de estratégias gulosas para a solução de problemas é uma
abordagem muito comum, porque, em geral, várias opções podem ser
implementadas. Porém, nem sempre a melhor solução é possível de ser obtida
com essa abordagem. Um exemplo é o problema conhecido como problema da
mochila 0-1. Uma mochila que suporta, no máximo, um peso P, deve ser
carregada com os itens mais valiosos dentre n disponíveis, de modo a alcançar
o maior valor total. Cada item i tem um peso pi e um valor vi associado.
1 em 1 pontos
1 em 1 pontos
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
Considerando a instância do problema da mochila 0-1, analise as afirmativas a
seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s).
 
I. ( ) A solução ótima inclui os itens 2 e 3.
II. ( ) Organizando os itens por ordem crescente de peso e selecionando cada
item nessa ordem, somos conduzidos a uma solução sub-ótima.
III. ( ) A estratégia gulosa de selecionar os itens com maior razão vi/pi conduz à
solução ótima.
IV. ( ) Qualquer solução contendo o item com maior valor por peso é sub-ótima.
 
Agora, assinale a alternativa que apresenta a sequência correta.
V, V, F, V.
V, V, F, V.
Resposta certa. A seleção dos itens 2 e 3 é a única que conduz à
solução ótima com o valor da mochila em 220. Se ositens forem
selecionados de acordo com a razão vi/pi, o item 1 será o primeiro
selecionado (60/10), seguido do item 2 (100/20), o que levará a
uma mochila de valor 160. As demais estratégias também levarão
a soluções sub-ótimas.
Pergunta 10
Uma estratégia muito utilizada no desenvolvimento de algoritmos recursivos é
aplicar a técnica de divisão e conquista. Nesse caso, o problema original é
dividido em problemas menores, os quais são solucionados e, posteriormente,
combinados para formar a solução do problema inicial. Um exemplo é o
problema de multiplicação de matrizes quadradas (mesmo número de linhas e
colunas), cujo algoritmo iterativo é apresentado a seguir:
 
Algoritmo MultiplicaMatrizQuadrada
Entrada: Duas matrizes A e B quadradas de tamanho n
Saída: Matriz C = A × B
1. Defina uma matriz C quadrada de tamanho n
1 em 1 pontos
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
2. para i ← 1 até n faça
3. para j ← 1 até n faça
4. cij ← 0
5. para k ← 1 até n faça
6. cij ← cij + aik × bkj
7. retorna C
 
Suponha, então, uma versão recursiva desse algoritmo,
chamadaMultiplicaRecursivo, pode ser obtida por meio da divisão das matrizes
A, B e C em 4 matrizes de tamanho n/2 (assuma que n é potência exata de 2),
conforme imagem a seguir:
 
 
Considerando essas informações e os conteúdos estudados, analise as
seguintes afirmativas.
 
I. O algoritmo MultiplicaRecursivo terá desempenho superior que a versão
iterativa apresentada.
II. O caso base do algoritmo será se n = 1, então retorna c11 = a11 × b11.
III. Serão necessárias 8 chamadas recursivas ao algoritmo MultiplicaRecursivo,
para a construção de todas as submatrizes Cij.
IV. A etapa de divisão das matrizes A, B e C em submatrizes pode impactar no
desempenho geral do algoritmo.
 
Está correto apenas o que se afirma em:
II e III.
II e III.
Resposta certa. Considerando a estratégia de divisão das matrizes
originais em 4 submatrizes, o algoritmo recursivo pode ser descrito
como a seguir:
Algoritmo MultiplicaRecursivo
Entrada: Duas matrizes A e B quadradas de tamanho n
Saída: Matriz C = A × B
01. Defina uma matriz C quadrada de tamanho n
02. se n = 1 então
03. retorna c11 = a11 × b11
04. se não
05. Particionar as matrizes A, B e C em 4 submatrizes
06. C11 = MultiplicaRecursivo(A11, B11) +
MultiplicaRecursivo(A12, B21)
07. C12 = MultiplicaRecursivo(A11, B12) +
MultiplicaRecursivo(A12, B22)
08. C21 = MultiplicaRecursivo(A21, B11) +
MultiplicaRecursivo(A22, B21)
T(1) = Θ(1), se n = 1
T(n) = 8T(n/2) + Θ(n2), se n > 1
09. C22 = MultiplicaRecursivo(A21, B12) +
MultiplicaRecursivo(A22, B22)
10. retorna C
Como cada uma das submatrizes tem n2/4 entradas, cada uma
das 4 adições de submatrizes demanda um tempo Θ(n2). Logo, a
equação de recorrência que descreve o algoritmo é dada por:
Pela aplicação do teorema mestre, a solução fechada da
recorrência é T(n) = Θ(n3), ou seja, não há diferença de
desempenho entre ambas versões do algoritmo. Além disso, como
a etapa de divisão das matrizes é Θ(n2), no pior caso, ela não tem
impacto sobre a complexidade geral do algoritmo.