analise de algoritmos_semana 4

Prévia do material em texto

• Pergunta 1 
0 em 1 pontos 
 
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: 
• h(“x ← 0”) = verdadeiro 
• h(“enquanto verdadeiro faça x ← 1”) = falso 
 
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. 
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. 
 
Resposta 
Selecionada: 
 
As asserções I e II são proposições verdadeiras, e a II é 
uma justificativa correta da I. 
Resposta Correta: 
As asserções I e II são proposições falsas. 
Comentário da 
resposta: 
Resposta incorreta. Verifique os conceitos de 
computabilidade e como eles podem ser empregados para 
determinar se um programa retorna algum resultado para 
qualquer instância do problema informado. 
 
 
• Pergunta 2 
1 em 1 pontos 
 
Os conceitos que fundamentam a construção de estratégias gulosas são 
importantes para que uma modelagem precisa possa ser empregada durante 
 
a proposição de soluções. Essa análise deve preceder, inclusive, a etapa de 
projeto de um algoritmo guloso. 
 
Nesse contexto, dado um conjunto { x1, x2, …, xn } de pontos na reta dos 
números reais, analise as asserções a seguir e a relação proposta entre elas. 
 
I. É possível projetar uma estratégia gulosa para encontrar o menor conjunto 
de intervalos fechados de comprimento 1 (um) contendo todos os pontos. 
Porque: 
II. A cada etapa da estratégia gulosa uma escolha local ótima pode ser feita 
de modo a garantir a obtenção de uma solução final ótima. 
Resposta 
Selecionada: 
 
As asserções I e II são proposições verdadeiras, e a II é 
uma justificativa correta da I. 
Resposta Correta: 
As asserções I e II são proposições verdadeiras, e a II é 
uma justificativa correta da I. 
Comentário 
da resposta: 
Resposta certa. Considere o intervalo mais à esquerda. 
Sabemos que esse intervalo deve conter o ponto mais à 
esquerda. Então, sabemos que seu lado esquerdo é 
exatamente o ponto mais à esquerda. Portanto, simplesmente 
removemos qualquer ponto que não pertença ao conjunto 
informado e que esteja a uma unidade de distância do ponto, 
uma vez que eles estão contidos neste único intervalo. Em 
seguida, nós apenas repetimos esse processo até que todos 
os pontos sejam cobertos. Como em cada etapa há uma 
escolha claramente ótima de onde colocar o intervalo mais à 
esquerda, essa solução final é ótima. Portanto, ambas as 
afirmativas são verdadeiras e a II justifica a primeira. 
 
 
• Pergunta 3 
0 em 1 pontos 
 
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. 
Resposta 
Selecionada: 
 
Para todo problema cuja solução possa ser testada em 
tempo polinomial, existe um algoritmo polinomial que o 
resolve. 
Resposta 
Correta: 
 
A descoberta de um algoritmo polinomial para um problema 
NP-completo pode tornar a igualdade P = NP verdadeira. 
Comentário da 
resposta: 
Resposta incorreta. Verifique as definições de classes de 
computabilidade e como os problemas são classificados de 
acordo com suas características computacionais. 
 
 
 
• Pergunta 4 
1 em 1 pontos 
 
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: 
 
Resposta 
Selecionada: 
 
A asserção I é uma proposição falsa, e a II é uma 
proposição verdadeira. 
Resposta Correta: 
A asserção I é uma proposição falsa, e a II é uma 
proposição verdadeira. 
 
Comentário 
da resposta: 
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 5 
0 em 1 pontos 
 
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. 
 
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. 
Resposta Selecionada: 
F, V, F, V. 
Resposta Correta: 
V, V, F, V. 
Comentário da 
resposta: 
Resposta incorreta. Analise as opções possíveis para o carregamento da mochila e 
verifique qual é a solução ótima. Compare essa solução com as estratégias 
apresentadas. 
 
• Pergunta 6 
1 em 1 pontos 
 
Um típico problema em que algoritmos gulosos são aplicados é conhecido 
como agendamento 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 ai demanda 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 cio 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 
pi obté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. 
Resposta Selecionada: 
V, V, F, V. 
Resposta Correta: 
V, V, F, V. 
Comentário 
da resposta: 
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 7 
0 em 1 pontos 
 
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. 
Resposta 
Selecionada: 
 
As asserções I e II são proposições falsas. 
Resposta Correta: 
As asserções I e II são proposições verdadeiras, e a II é 
uma justificativa correta da I. 
Comentário da 
resposta: 
Resposta incorreta. Observe as definições relacionadas às 
classes P e NP e veja como elas estão relacionadas com o 
conceito denotado pelo operador ≤p apresentado. 
 
 
 
• Pergunta 8 
1 em 1 pontos 
 
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. 
 
 
Resposta 
Selecionada: 
 
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 
Correta: 
 
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. 
Comentário 
da resposta: 
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 9 
0 em 1 pontos 
 
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. 
 
Resposta 
Selecionada: 
 
A asserção I é uma proposição falsa, e a II é uma 
proposição verdadeira. 
Resposta Correta: 
 
As asserções I e II são proposições verdadeiras, e a II é 
uma justificativa correta da I. 
Comentário 
da resposta: 
Resposta incorreta. Verifique se é possível adaptar o 
algoritmo counting sort, para contemplar a operação de 
consulta à quantidade de números no intervalo informado. 
Além disso, analise o custo computacional associado às 
modificações. 
 
• Pergunta 10 
1 em 1 pontos 
 
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 menor quantidade 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). 
 
Está correto o que se afirma em: 
Resposta Selecionada: 
II e IV. 
Resposta Correta: 
II e IV. 
Comentário 
da resposta: 
Resposta certa. Para as entradas (c1 = 20, c2 = 15, c3 = 7, c4 = 
1) e n = 22, o algoritmo não produz asoluçã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: 
• 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 
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.