ATIVIDADE 4

Prévia do material em texto

19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 1/16
Usuário BRUNO CESAR LIMA
Curso GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-8658.04
Teste ATIVIDADE 4 (A4)
Iniciado 18/06/21 23:10
Enviado 19/06/21 18:03
Status Completada
Resultado da tentativa 10 em 10 pontos  
Tempo decorrido 18 horas, 52 minutos
Resultados exibidos Respostas enviadas, Respostas corretas, Comentários
Pergunta 1
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
1 em 1 pontos
19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 2/16
Resposta Selecionada: 
Resposta Correta: 
Comentário
da
resposta:
 
 
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:
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 2
1 em 1 pontos
19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 3/16
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.
19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 4/16
Resposta Selecionada: 
Resposta Correta: 
Comentário
da
resposta:
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.
T(1) = Θ(1),                          se n = 1
T(n) = 8T(n/2) + Θ(n2),       se n > 1
Resposta certa. Considerando a estratégia de divisão das matrizes originais em 4 submatrizes, o algoritmo
recursivo pode ser descrito como a seguir:
Algoritmo MultiplicaRecursivo
Entrada: Duas matrizes A e B quadradas de tamanho n
Saída: Matriz C = A × B
01. Defina uma matriz C quadrada de tamanho n
02. se n = 1 então
03. retorna c11 = a11 × b11
04. se não
05.      Particionar as matrizes A, B e C em 4 submatrizes
06.      C11 = MultiplicaRecursivo(A11, B11) + MultiplicaRecursivo(A12, B21)
07.      C12 = MultiplicaRecursivo(A11, B12) + MultiplicaRecursivo(A12, B22)
08.      C21 = MultiplicaRecursivo(A21, B11) + MultiplicaRecursivo(A22, B21)
09.      C22 = MultiplicaRecursivo(A21, B12) + MultiplicaRecursivo(A22, B22)
10. retorna C
Como cada uma das submatrizes tem n2/4 entradas, cada uma das 4 adições de submatrizes demanda um tempo
Θ(n2). Logo, a equação de recorrência que descreve o algoritmo é dada por:
19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 5/16
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 3
Resposta
Selecionada:
Resposta
Correta:
Comentário
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.
1 em 1 pontos
19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 6/16
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 4
Resposta Selecionada: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.
1 em 1 pontos
19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 7/16
 
Resposta Correta:
 
Comentário da
resposta:
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
 
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 certa. O pseudocódigo do algoritmo recursivo que implementa a recorrência é descrito a
seguir:
 
Algoritmo Multiplicador
1. se x = 0, então
2. retorna 0
19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 8/16
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
Pergunta 5
Resposta
Selecionada:
Resposta Correta:
Comentário
Os problemas que precisam ser resolvidos computacionalmente podem ser classificados de acordo com a sua computabilidade.
Essa classificação é importante, considerando que ela tem efeito direto sobre a viabilidade de construção de um algoritmo útil em
cenários práticos.
 
Considerando essas informações e os conteúdos estudados, assinale a alternativa correta a respeito dessa classificação de
problemas.
A descoberta de um algoritmo polinomial para um problema NP-completo pode tornar a igualdade P = NP
verdadeira.
A descoberta de um algoritmo polinomial para um problema NP-completo pode tornar a igualdade P = NP
verdadeira.
1 em 1 pontos
19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 9/16
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 6
Resposta Selecionada:
 
Vários problemas que surgem em contextos práticos demandam análises elaboradas, para que uma solução possa ser proposta.
E, muitas vezes, o conceito de computabilidade precisa ser considerado, já que a característica do problema pode impactar na
elaboração de uma solução computacional.
 
Nesse contexto, e considerando os conteúdos estudados sobre problemas P e NP, analise as asserções a seguir e a relação
proposta entre elas.
 
I. O problema de analisar centenas de milhares de registros para verificar quais deles totalizam um dado valor pode ser resolvido
em tempo polinomial.
Porque:
II. Um procedimento computacional simples pode ser construído para somar esses registros e responder se o valor contabilizado
é igual ao valor informado.
 
A seguir, assinale a alternativa correta:
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
 
1 em 1 pontos
19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 10/16
Resposta Correta:
 
Comentário
da
resposta:
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
 
Resposta certa. A respeito da complexidade do problema, é preciso identificar que se trata de procurar, dentro de
um conjunto de números (registros), quais subconjuntos somam certo valor (o valor informado). Dentro da teoria
da computabilidade, esse problema é conhecido como o problema da soma de subconjunto, e ele pertence à
classe dos problemas NP. Logo, não se conhece ainda um algoritmo capaz de resolver esse problema em um
tempo polinomial. Logo, a primeira asserção é falsa. Porém, outra característica dos problemas NP é que eles
podem ser verificados em tempo polinomial. Por isso, é possível implementar um procedimento computacional
simples para somar esses registros e responder se o valor contabilizado é igual ao valor suspeito. Logo, a segunda
asserção é verdadeira.
Pergunta 7
A construção de estratégias gulosas para a solução de problemas é uma abordagem muito comum, porque, em geral, várias
opções podem ser implementadas. Porém, nem sempre a melhor solução é possível de ser obtida com essa abordagem. Um
exemplo é o problema conhecido como problema da mochila 0-1. Uma mochila que suporta, no máximo, um peso P, deve ser
carregada com os itens mais valiosos dentre n disponíveis, de modo a alcançar o maior valor total. Cada item i tem um peso pi e
um valor vi associado.
1 em 1 pontos
19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 11/16
Resposta Selecionada: 
Considerando a instância do problema da mochila 0-1, analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para
a(s) falsa(s).
 
I. ( ) A solução ótima inclui os itens 2 e 3.
II. ( ) Organizando os itens por ordem crescente de peso e selecionando cada item nessa ordem, somos conduzidos a uma
solução sub-ótima.
III. ( ) A estratégia gulosa de selecionar os itens com maior razão vi/pi conduz à solução ótima.
IV. ( ) Qualquer solução contendo o item com maior valor por peso é sub-ótima.
 
Agora, assinale a alternativa que apresenta a sequência correta.
V, V, F, V.
19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 12/16
Resposta Correta: 
Comentário
da
resposta:
V, V, F, V.
Resposta certa. A seleção dos itens 2 e 3 é a única que conduz à solução ótima com o valor da mochila em 220. Se
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 160. As demais estratégias também levarão a soluções sub-
ótimas.
Pergunta 8
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 propostaentre 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.
1 em 1 pontos
19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 13/16
Resposta Selecionada:
 
Resposta Correta:
 
Comentário
da
resposta:
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 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 9
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.
1 em 1 pontos
19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 14/16
Resposta Selecionada:
 
Resposta Correta:
 
Comentário
da
resposta:
 
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.
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. 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 10
1 em 1 pontos
19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 15/16
Resposta Selecionada: 
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:
II e IV.
19/06/2021 Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0559 ...
https://unp.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_668480_1 16/16
Sábado, 19 de Junho de 2021 18h03min50s BRT
Resposta Correta: 
Comentário
da
resposta:
II e IV.
a1 = ⌊n/c1⌋ e nq = n mod c1
a2 = ⌊nq/c2⌋ e nd = nq mod c2
a3 = ⌊nd/c3⌋ e nk = nq mod c2
a4 = nk
Resposta certa. Para as entradas (c1 = 20, c2 = 15, c3 = 7, c4 = 1) 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:
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.