ANÁLISE DE ALGORITMOS ATIVIDADE 4

Prévia do material em texto

17/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-29778933.06
https://fmu.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_670400… 1/9
Usuário
Curso
Teste
Iniciado
Enviado
Status
Resultado da
tentativa
Tempo decorrido 67 horas, 28 minutos
Resultados exibidos Respostas enviadas, Respostas corretas, Comentários
Pergunta 1
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.
Qualquer problema NP-difícil é possível de ter um certificado
verificado em tempo polinomial.
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.
Pergunta 2
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.
0 em 1 pontos
0 em 1 pontos
17/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-29778933.06
https://fmu.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_670400… 2/9
Resposta Selecionada:  
Resposta Correta:  
Comentário
da resposta:
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:
V, V, F, F.
V, V, F, V.
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 3
Resposta
Selecionada:
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.
1 em 1 pontos
17/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-29778933.06
https://fmu.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_670400… 3/9
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. 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 4
Resposta
Selecionada:
Resposta
Correta:
Comentário
da resposta:
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:
As asserções I e II são proposições verdadeiras, mas a II não é
uma justificativa correta da I.
A asserção I é uma proposição falsa, e a II é uma proposição
verdadeira.
Resposta incorreta. Considere o problema sob a perspectiva dos
conceitos de computabilidade e busque identificar a sua
classificação.
0 em 1 pontos
17/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-29778933.06
https://fmu.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_670400… 4/9
Pergunta 5
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 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
problema de multiplicação de matrizes quadradas (mesmo número de linhas e
colunas), cujo algoritmo iterativo é apresentado a seguir:
Algoritmo MultiplicaMatrizQuadrada
0 em 1 pontos
0 em 1 pontos
17/06/2021 GRA0559 ANÁLISEDE ALGORITMOS GR0075211 - 202110.ead-29778933.06
https://fmu.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_670400… 5/9
Resposta Selecionada:  [Sem Resposta]
Resposta Correta:  
Comentário
da resposta:
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.
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 7
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.
0 em 1 pontos
17/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-29778933.06
https://fmu.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_670400… 6/9
Resposta Selecionada:  
Resposta Correta:  
Comentário
da resposta:
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 e IV.
I, II e III.
Resposta incorreta. Execute o passo a passo do algoritmo e
analise a configuração dos vetores à medida que a ordenação
acontece.
Pergunta 8
Resposta
Selecionada:
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.
Para a soma dos números i = 3 e j = 7, o algoritmo realiza 2
chamadas recursivas.
0 em 1 pontos
17/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-29778933.06
https://fmu.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_670400… 7/9
Resposta
Correta:
Comentário
da resposta:
O passo recursivo da função de recorrência associada é T(i, j) =
T(i -1, j + 1) para i > 0.
Resposta incorreta. Busque explicitar a função de recorrência que
descreve o algoritmo e execute o seu passo a passo, para os
parâmetros informados nas alternativas.
Pergunta 9
Resposta Selecionada:  
Resposta Correta:  
Comentário
da resposta:
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:
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
0 em 1 pontos
17/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-29778933.06
https://fmu.blackboard.com/webapps/late-course_content_soap-BBLEARN/Controller?ACTION=OPEN_TEST_PLAYER&COURSE_ID=_670400… 8/9
soluções ótimas.
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. 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 em 1 pontos
17/06/2021 GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-29778933.06
Quinta-feira, 17 de Junho de 2021 21h17min38s BRT
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