Analise de Algoritmos Atividade 04

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
porque, em geral, várias opções podem ser implementadas. Porém, nem sempre a melhor
possível de ser obtida com essa abordagem. Um exemplo é o problema conhecido como
mochila 0-1. Uma mochila que suporta, no máximo, um peso P, deve ser carregada com
valiosos dentre n disponíveis, de modo a alcançar o maior valor total. Cada item i tem um
valor vi associado. 
Considerando a instância do problema da mochila 0-1, analise as afirmativas a seguir e 
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
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
verifique qual é a solução ótima. Compare essa solução com 
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 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 detodas 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 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: 
 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. 
 
 
 
 Pergunta 1 
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 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 
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 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 
1 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 falsas. 
Resposta Correta: 
As asserções I e II são proposições falsas. 
Comentário 
da resposta: 
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: 
 H(“x ← 0”) = verdadeiro 
 H(“enquanto verdadeiro faça x ← 1”) = falso. 
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 verdadeiro faç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 
1 em 1 pontos 
 
A recursão é uma poderosa técnica para modelagem e projeto de algoritmos. 
O uso dessa estratégia, porém, depende da correta identificação dos seus 
dois principais elementos: um caso base que finaliza as chamadas recursivas 
e o passo de recursão. Suponha a situação em que a operação de adição em 
uma linguagem de programação é feita por um componente externo. Esse 
componente recebe como parâmetro dois números a serem somados e, 
internamente, ele faz uso dos operadores ++ para incrementar o valor de um 
número em 1 e -- para decrementar em 1. 
 
Somador 
Entrada: Dois inteiros i e j a serem somados 
Saída: Valor de i + j 
1. se i = 0 então 
2. retorna j 
3. senão 
4. retorna Somador(- -i, ++j) 
 
Considerando o Algoritmo Somador apresentado, assinale a alternativa 
correta a respeito de seu funcionamento. 
 
Resposta 
Selecionada: 
 
O passo recursivo da função de recorrência associada é 
T(i, j) = T(i -1, j + 1) para i > 0. 
Resposta Correta: 
O passo recursivo da função de recorrência associada é 
T(i, j) = T(i -1, j + 1) para i > 0. 
Comentário 
da resposta:Resposta certa. A função de recorrência do algoritmo pode ser 
descrita como: 
 T( i, j ) = j, se i = 0 
 T( i, j ) = T(i - 1, j + 1), se i > 0 
Como o resultado das chamadas recursivas é o próprio 
resultado final do algoritmo, não existem etapas de 
combinação das soluções parciais. Para i = 3 e j = 7, o 
algoritmo faz a seguinte chamada recursiva, após a invocação 
Somador(3, 7): 
 Somador(2, 8) 
 Somador(1, 9) 
 Somador(0, 10) 
 
 Pergunta 5 
0 em 1 pontos 
 
A ordenação de dados em memória é uma das operações mais comuns 
executadas por algoritmos computacionais. Embora existam diferentes 
estratégias para esse tipo de operação, poucas delas conseguem alcançar um 
tempo computacional linear. 
 
Algoritmo Ordenação Linear Simplificada 
Entrada: Um vetor A de n inteiros cujos valores são 1 ou 2. 
Saída: Vetor A com os valores ordenados de forma não-decrescente 
1. Defina k ← 0 
2. para i ← 1 até n faça 
3. se A[ i ] = 1, então k ← k + 1 
4. para i ← 1 até k faça 
5. A[ i ] ← 1 
6. para i ← k + 1 até n faça 
7. A[ i ] ← 2 
8. retorna A 
 
 
 
Nesse contexto, considerando o algoritmo apresentado, analise as afirmativas 
a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s). 
 
I. ( ) Para um vetor A contendo m posições com valor 1 e n posições com valor 
2, o algoritmo realiza m + n operações de atribuições ao vetor A. 
II. ( ) O algoritmo é estável. 
III. ( ) Para qualquer sequência de valores aceitos pelo algoritmo, as primeiras 
posições do vetor A serão ocupadas pelo valor 2. 
IV. ( ) O maior valor possível para k é n. 
 
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 o funcionamento do algoritmo 
para diferentes sequências de valores 1 e 2 e verifique como 
o vetor de saída é construído. 
 
 
 Pergunta 6 
1 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: 
 
A descoberta de um algoritmo polinomial para um problema 
NP-completo pode tornar a igualdade P = NP verdadeira. 
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 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 7 
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 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: 
 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. 
 
 
 Pergunta 8 
1 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 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. Observa-se que, se P = NP, então X pode ser 
resolvido em tempo polinomial, já que X pertence à classe NP. 
Inversamente, suponha 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 9 
0 em 1 pontos 
 
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 
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, 
chamada MultiplicaRecursivo, 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: 
Resposta Selecionada: 
II e IV. 
Resposta Correta: 
II e III. 
Comentário da 
resposta: 
Resposta incorreta. Procure construir o algoritmo recursivo, para 
avaliar cada uma das afirmações. Em seguida, verifique a 
complexidade da recorrência que descreve o algoritmo. 
 
 
 Pergunta 10 
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. 
 
 
Quinta-feira, 10 de Junho de 2021 19h56min46s BRT 
 
• A ordenação de dados em memória é uma das operações 
mais comuns executadas por algoritmos computacionais. 
Embora existam diferentes estratégias para esse tipo de 
operação, poucas delas conseguem alcançar um tempo 
computacional linear. 

 
• Algoritmo Ordenação Linear Simplificada 

Entrada: Um vetor A de n inteiros cujos valores são 1 ou 2.

Saída: Vetor A com os valores ordenados de forma não-
decrescente

1. Defina k ȼ 0 

2. para i ȼ 1 até n faça 

3.        se A[ i ] = 1, então k ȼ k + 1 

4. para i ȼ 1 até k faça 

5.        A[ i ] ȼ 1       

6. para i ȼ k + 1 até n faça 

7.         A[ i ] ȼ 2 

8. retorna A
•  

 

Nesse contexto, considerando o algoritmo apresentado, 
analise as afirmativas a seguir e assinale V para a(s) 
verdadeira(s) e F para a(s) falsa(s).

 

I. ( ) Para um vetor A contendo m posições com valor 1 e n 
posições com valor 2, o algoritmo realiza m + n operações 
de atribuições ao vetor A.

II. ( ) O algoritmo é estável.

III. ( ) Para qualquer sequência de valores aceitos pelo 
algoritmo, as primeiras posições do vetor A serão ocupadas 
pelo valor 2.

IV. ( ) O maior valor possível para k é n.

 

Agora, assinale a alternativa que apresenta a sequência 
correta:
Algoritmo Ordenação Linear 
Simplificada 

Resposta Selecionada:
Resposta Correta:
 V, V, F, V.
 V, V, F, V.
Comentário 
da 
respost
a:
Resposta certa. Para 
u m a e n t r a d a 
composta de m 
va lores 1 e n 
v a l o r e s 2 , o 
primeiro laço do 
a l g o r i t m o v a i 
finalizar com o 
valor de k = m e, 
p o r t a n t o , o 
segundo laço vai 
r e a l i z a r m 
a t r ibu ições ao 
vetor A. O último 
laço realiza tantas 
a t r ibu ições ao 
vetor A quanto o 
n ú m e r o d e 
v a l o r e s 2 
p r e s e n t e s n a 
entrada, ou seja, 
n a t r i b u i ç õ e s . 
Portanto, serão 
realizadas m + n 
atribuições a A. 
C o m o o s 
elementos com 
mesmo valor não 
têm sua ordem 
alterada no vetor 
d e s a í d a , o 
algoritmo é dito 
e s t á v e l . O 
segundo laço do 
a l g o r i t m o é 
responsável pela 
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.
• 



• Pergunta 3 



1 em 1 pontos

Resposta Selecionada:
Resposta Correta:
 V, V, F, V.
 V, V, F, V.
Comentário 
da 
respost
a:
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 os itens 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 
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 ís t ica é sua estab i l idade 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 
Selecion
ada:
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.
 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 
respost
a:
R e s p o s t a c e r t a . 
Suponha que as 
posições i e j com 
i <j contenham 
algum elemento 
• 



• Pergunta 4 



1 em 1 pontosOs 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 
Selecion
ada:
 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 
respost
a:
R e s p o s t a c e r t a . 
C o n s i d e r e o 
intervalo mais à 
e s q u e r d a . 
S a b e m o s q u e 
esse in te rva lo 
deve conter o 
p o n t o m a i s à 
esquerda. Então, 
sabemos que seu 
lado esquerdo é 
e x a t a m e n t e o 
p o n t o m a i s à 
e s q u e r d a . 
P o r t a n t o , 
s i m p l e s m e n t e 
r e m o v e m o s 
qualquer ponto 
que não pertença 
a o c o n j u n t o 
informado e que 
e s t e j a a u m a 
u n i d a d e d e 
d i s t â n c i a d o 
ponto, uma vez 
que eles estão 
cont idos neste 
único intervalo. 
Em seguida, nós 
apenas repetimos 
esse processo 
até que todos os 
• 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

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, 
chamada MultiplicaRecursivo, 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 
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

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
Resposta Selecionada:
Resposta Correta: II e III.
 II e III.
Comentário 
da 
respost
a:
• R e s p o s t a c e r t a . 
C o n s i d e r a n d o a 
estratégia de divisão 
das matrizes originais 
em 4 submatrizes, o 
algoritmo recursivo pode 
ser descrito como a 
seguir:

A l g o r i t m o 
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 

• 



• Pergunta 6 



0 em 1 pontos

O algoritmo counting sort constitui uma alternativa eficiente 
para a ordenação de dados em memória, já que ele 
demanda um tempo computacional da ordem de Θ(n). 
No entanto, ele faz maior uso do espaço em memória, 
por precisar que vetores auxiliares sejam criados durante 
sua execução. 

 

Considerando a execução do algoritmo sobre um vetor A 
= {4, 1, 5, 0, 1, 6, 5, 1, 5, 3}, em que todos os valores são 
menores que k = 7, analise as afirmativas a seguir.

 

I. Após o primeiro laço que inicializa cada posição do 
vetor auxiliar C com zero, o segundo laço finaliza com o 
vetor C = { 1, 3, 0, 1, 1, 3, 1 }.

II. Ao término do terceiro laço, o vetor auxiliar C definido 
no corpo do algoritmo terá os seguintes valores 
armazenados {0, 3, 3, 4, 5, 8, 9}.

III. A primeira iteração do último laço do algoritmo faz 
com que o valor 3 seja atribuído à posição 4 do vetor A.

IV. A posição 4 corresponde à última posição do vetor A a 
ser preenchida pelo laço final do algoritmo.

 

Está correto apenas o que se afirma em:
Resposta Selecionada:
Resposta Correta:
 I e IV.
 I, II e III.
• 



• Pergunta 7 



1 em 1 pontos

Comentário 
da 
respost
a:
Resposta incorreta. 
Execute o passo 
a p a s s o d o 
a l g o r i t m o e 
a n a l i s e a 
configuração dos 
vetores à medida 
que a ordenação 
O s p r o b l e m a s q u e p r e c i s a m s e r r e s o l v i d o s 
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 
Selecion
ada:
 A descoberta de 
um algoritmo 
polinomial para 
um problema 
NP-completo 
pode tornar a 
igualdade P = 
NP verdadeira.
Resposta 
Correta:
 A descoberta de 
um algoritmo 
polinomial para 
um problema 
NP-completo 
pode tornar a 
igualdade P = 
NP verdadeira.
Comentário 
da 
respost
a:
Resposta certa. O 
p r o b l e m a d e 
encontrar uma 
r o t a ó t i m a 
visitando pontos 
específicos uma 
única vez é uma 
a p l i c a ç ã o d o 
p r o b l e m a d o 
Caixeiro Viajante, 
que é da classe 
NP. Problemas da 
classe NP-difícil 
s a t i s f a z e m 
a p e n a s u m a 
c o n d i ç ã o d o s 
p r o b l e m a s d a 
c l a s s e N P 
(problemas NP-
c o m p l e t o 
s a t i s f a z e m à s 
duas condições e 
são NP-difíceis), 
ou seja, se um 
a l g o r i t m o 
p o l i n o m i a l f o r 
encontrado para 
ele, então todos 
os problemas NP 
• 



• Pergunta 8 



1 em 1 pontos

• A recursão é uma poderosa técnica para modelagem e 
projeto de algoritmos. O uso dessa estratégia, porém, 
depende da correta identificação dos seus dois principais 
elementos: um caso base que finaliza as chamadas 
recursivas e o passo de recursão. Suponha a situação em 
que a operação de adição em uma linguagem de 
programação é feita por um componente externo. Esse 
componente recebe como parâmetro dois números a serem 
somados e, internamente, ele faz uso dos operadores ++ 
para incrementar o valor de um número em 1 e -- para 
decrementar em 1. 

 
• Somador

Entrada: Dois inteiros i e j a serem somados

Saída: Valor de i + j

1. se i = 0 então

2.        retorna j 

3. senão 

4.        retorna Somador(- -i, ++j)
•  

Considerando o Algoritmo Somador apresentado, assinale a 
alternativa correta a respeito de seu funcionamento.
Somador

Entrada: Dois inteiros i e j a 
serem somados

Saída: Valor de i + j

1. se i = 0 então

2.        retorna j 

3. senão 

4.        retorna Somador(- -i, +
+j)
Resposta 
Selecion
ada:
Resposta 
Correta:
 O passo recursivo 
da função de 
recorrência 
associada é T(i, 
j) = T(i -1, j + 1) 
para i > 0.
 O passo recursivo 
da função de 
recorrência 
associada é T(i, 
j) = T(i -1, j + 1) 
para i > 0.
Comentário 
da 
respost
a:
• Resposta certa. A 
f u n ç ã o d e 
r e c o r r ê n c i a d o 
algoritmo pode ser 
descrita como:
• T( i, j ) 
= j, se i = 0
• T( i, j ) 
= T(i - 1, j + 
1), se i > 0
• Como o resultado 
d a s c h a m a d a s 
recursivas é o próprio 
resultadofinal do 
a l g o r i t m o , n ã o 
existem etapas de 
• Algoritmos gulosos constituem uma poderosa ferramenta 
p a r a a s o l u ç ã o d e p r o b l e m a s e m u m t e m p o 
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:
Algoritmo Troco em Moedas

Entrada: Um inteiro n e um 
Resposta Selecionada:
Resposta Correta: II e IV.
 II e IV.
Comentário 
da 
respost
a:
• Resposta certa. Para 
as entradas (c1 = 20, 
c2 = 15, c3 = 7, c4 = 
1 ) e n = 2 2 , 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 , c 4 = 1 ) , a 
solução produzida 
pelo algoritmo é C = { 
c1, c2, c2, c1, c1, 
c1 } e não contém a 
moeda c3. Embora o 
a l g o r i t m o t e n h a 
complexidade O(n), 
uma versão dele com 
desempenho O(1) 
pode ser obtida com 
a s s e g u i n t e s 
operações:
• a1 = 
⌊n/c1⌋ e nq 
= n mod c1
• a2 = 
⌊nq/c2⌋ e 
nd = nq mod 
c2
• a3 = 
⌊nd/c3⌋ e nk 
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 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 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 
respost
a:
R e s p o s t a c e r t a . 
Considerando S 
composto apenas 
de duas tarefas 
a1 e a2 com p1 = 
3 e p2 = 5, temos 
que, quando a2 é 
e x e c u t a d a 
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 
q u e o t e m p o 
médio é (3 + 8) / 
2 = 5 . 5 . 
Considerando a 
ordenação das 
t a r e f a s p e l a 
quant idade de 
u n i d a d e s d e 
t e m p o p a r a 
serem finalizadas 
(pi), o tempo de 
e x e c u ç ã o d o 
a lgor i tmo será 
d o m i n a d o 
s u p e r i o r m e n t e 
p o r e s s a 
operação. Como 
não é possível 
definir um valor 
m á x i m o p a r a 
t o d o s o s p i  
13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_67… 1/9
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
0 em 1 pontos
13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_67… 2/9
Resposta
Selecionada:
Resposta
Correta: 
Comentário
da resposta:
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.
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 verdadeiras, e a II é uma
justificativa correta da I.
As asserções I e II são proposições falsas.
 
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 3
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:
1 em 1 pontos
13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_67… 3/9
Resposta
Selecionada:
Resposta Correta:
Comentário
da resposta:
A asserção I é uma proposição falsa, e a II é uma proposição
verdadeira.
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 4
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.
Para todo problema cuja solução possa ser testada em tempo
polinomial, existe um algoritmo polinomial que o resolve.
A descoberta de um algoritmo polinomial para um problema NP-
completo pode tornar a igualdade P = NP verdadeira.
Resposta incorreta. Verifique as definições de classes de
computabilidade e como os problemas são classificados de acordo
com suas características computacionais.
 
0 em 1 pontos
13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_67… 4/9
Pergunta 5
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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.
F, V, F, V.
V, V, F, V.
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
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
0 em 1 pontos
1 em 1 pontos
13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_67… 5/9
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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
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
13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_67… 6/9
T(1) = Θ(1), se n = 1
T(n) = 8T(n/2) + Θ(n2), se n > 1
06. C11 = MultiplicaRecursivo(A11, B11) +
MultiplicaRecursivo(A12, B21)
07. C12 = MultiplicaRecursivo(A11, B12) +
MultiplicaRecursivo(A12, B22)
08. C21 = MultiplicaRecursivo(A21, B11) +
MultiplicaRecursivo(A22, B21)
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çãode 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.
Pergunta 7
A ordenação de dados em memória é uma das operações mais comuns
executadas por algoritmos computacionais. Embora existam diferentes
estratégias para esse tipo de operação, poucas delas conseguem alcançar um
tempo computacional linear.
 
Algoritmo Ordenação Linear Simplificada
Entrada: Um vetor A de n inteiros cujos valores são 1 ou 2.
Saída: Vetor A com os valores ordenados de forma não-decrescente
1. Defina k ← 0
2. para i ← 1 até n faça
3. se A[ i ] = 1, então k ← k + 1
4. para i ← 1 até k faça
5. A[ i ] ← 1 
6. para i ← k + 1 até n faça
7. A[ i ] ← 2
8. retorna A
 
 
Nesse contexto, considerando o algoritmo apresentado, analise as afirmativas a
seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s).
 
I. ( ) Para um vetor A contendo m posições com valor 1 e n posições com valor
2, o algoritmo realiza m + n operações de atribuições ao vetor A.
II. ( ) O algoritmo é estável.
III. ( ) Para qualquer sequência de valores aceitos pelo algoritmo, as primeiras
posições do vetor A serão ocupadas pelo valor 2.
IV. ( ) O maior valor possível para k é n.
 
1 em 1 pontos
13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_67… 7/9
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
Agora, assinale a alternativa que apresenta a sequência correta:
V, V, F, V.
V, V, F, V.
Resposta certa. Para uma entrada composta de m valores 1 e n
valores 2, o primeiro laço do algoritmo vai finalizar com o valor de k
= m e, portanto, o segundo laço vai realizar m atribuições ao vetor
A. O último laço realiza tantas atribuições ao vetor A quanto o
número de valores 2 presentes na entrada, ou seja, n atribuições.
Portanto, serão realizadas m + n atribuições a A. Como os
elementos com mesmo valor não têm sua ordem alterada no vetor
de saída, o algoritmo é dito estável. O segundo laço do algoritmo é
responsável pela atribuição das primeiras posições do vetor com
valor 1. Finalmente, como o valor k é incrementado para cada valor
1 encontrado no vetor, o seu maior valor possível acontece quando
a entrada é composta de apenas valores 1. Neste caso, k = n.
Pergunta 8
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).
0 em 1 pontos
13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_67… 8/9
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
 
Está correto o que se afirma em:
III e IV.
II e IV.
Resposta incorreta. Analise o funcionamento do algoritmo para as
diferentes entradas e tente observar o padrão de formação das
soluções ótimas.
Pergunta 9
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
O algoritmo counting sort constitui uma alternativa eficiente para a ordenação de
dados em memória, já que ele demanda um tempo computacional da ordem de
Θ(n). No entanto, ele faz maior uso do espaço em memória, por precisar que
vetores auxiliares sejam criados durante sua execução.
 
Considerando a execução do algoritmo sobre um vetor A = {4, 1, 5, 0, 1, 6, 5, 1,
5, 3}, em que todos os valores são menores que k = 7, analise as afirmativas a
seguir.
 
I. Após o primeiro laço que inicializa cada posição do vetor auxiliar C com zero, o
segundo laço finaliza com o vetor C = { 1, 3, 0, 1, 1, 3, 1 }.
II. Ao término do terceiro laço, o vetor auxiliar C definido no corpo do algoritmo
terá os seguintes valores armazenados {0, 3, 3, 4, 5, 8, 9}.
III. A primeira iteração do último laço do algoritmo faz com que o valor 3 seja
atribuído à posição 4 do vetor A.
IV. A posição 4 corresponde à última posição do vetor A a ser preenchida pelo
laço final do algoritmo.
 
Está correto apenas o que se afirma em:
I, II e III.
I, II e III.
Resposta certa. O segundo laço do algoritmo é responsável por
contabilizar a frequência de cada valor do vetor A. Então, como
existem: 1 ocorrência de 0; 3 ocorrências de 1; 0 ocorrências de 2;
1 ocorrência de 3; 1 ocorrência de 4; 3 ocorrências de 5 e 1
ocorrência de 6, o vetor C terá os seguintes valores, ao término do
segundo laço {1, 3, 0, 1, 1, 3, 1}. O terceiro laço realiza uma soma
acumulada de cada posição. Porém, como o primeiro índice do
vetor é 0, as somas devem ser decrementadas de 1. Neste caso,
ao término desse laço, o valor de C será {0, 3, 3, 4, 5, 8, 9}. A
primeira iteração do último laço posiciona o elemento 3 na quarta
posição de A, já que C[ 3 ] = 4. O último valor a ser posicionado no
vetor A é o elemento 4. Mas como C[ 4 ] = 5, ele é alocado na
posição 5 do vetor.
1 em 1 pontos
13/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01
https://anhembi.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_67… 9/9
Pergunta 10
Resposta Selecionada:
 
Resposta Correta:
 
Comentário
da resposta:
x · y = 0, se x = 0
x · y = ⌊x/2⌋ · (y + y), se x é par
x · y = ⌊x/2⌋ · (y + y) + y, se x é ímpar
O conceito de recursão é antigo e já era explorado muito antes do
desenvolvimento da computação. No entanto, até hoje, vários problemas são
modelados com funções de recorrência e estas dão subsídio ao
desenvolvimento de várias soluções computacionais. Uma das recorrências
antigas, usadas pela civilização egípcia, é conhecida como multiplicação por
duplicação. A equação de recorrência que a define é descrita a seguir:
 
 
Considerando essa equação de recorrência, assinale a alternativa que indica o
algoritmo recursivo que implementa corretamente a multiplicação por duplicação.
O algoritmo Multiplicador recebe como entrada dois inteiros x e y a serem
multiplicados, e retorna o valor de x · y.
Algoritmo Multiplicador
1. se x = 0, então
2. retorna 0
3. se não
4. x’ ← ⌊x/2⌋
5. y’ ← y + y
6. prod ← Multiplicador (x’, y’)
7. retorna prod
 
Algoritmo Multiplicador
1. se x = 0, então
2. retorna 0
3. se não
4. x’ ← ⌊x/2⌋
5. y’ ← y + y
6. prod ← Multiplicador (x’, y’)
7. se x é ímpar, então
8. prod ← prod + y
9. retorna prod
 
Resposta incorreta. Construa o algoritmo primeiramente com foco
no seu funcionamento geral. De maneira incremental, vá
detalhando o que acontece em cada passo recursivo.
0 em 1 pontos
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 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 > … >