Unidade 4 - Prova Analise de Algoritmos - Ronie Camilo - UAM - Polo Jacarei - SP

Prévia do material em texto

Curso GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 
202110.ead-14790.01 
Teste ATIVIDADE 4 (A4) 
Iniciado 01/06/21 19:12 
Enviado 15/06/21 00:41 
Status Completada 
Resultado da 
tentativa 
10 em 10 pontos 
Tempo decorrido 317 horas, 28 minutos 
Resultados 
exibidos 
Respostas enviadas, Respostas corretas, Comentários 
• Pergunta 1 
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 2 
1 em 1 pontos 
 
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: 
 
• 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 
 
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. 
 
Resposta Selecionada: 
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 Correta: 
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 
Comentário da 
resposta: 
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 
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 3 
1 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: 
 
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. 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 4 
1 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: 
V, V, F, V. 
Resposta Correta: 
V, V, F, V. 
Comentário 
da resposta: 
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 5 
1 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 problemainicial. 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 III. 
Resposta Correta: 
II e III. 
Comentário 
da resposta: 
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: 
• T(1) = Θ(1), se n = 1 
• T(n) = 8T(n/2) + Θ(n2), se n > 1 
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 6 
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 7 
1 em 1 pontos 
 
A construção de estratégias gulosas para a solução de problemas é uma abordagem muito comum, 
porque, em geral, várias opções podem ser implementadas. Porém, nem sempre a melhor solução é 
possível de ser obtida com essa abordagem. Um exemplo é o problema conhecido como problema da 
mochila 0-1. Uma mochila que suporta, no máximo, um peso P, deve ser carregada com os itens mais 
valiosos dentre n disponíveis, de modo a alcançar o maior valor total. Cada item i tem um peso pi e um 
valor vi associado. 
 
Considerando a instância do problema da mochila 0-1, analise as afirmativas a seguir e assinale V para 
a(s) verdadeira(s) e F para a(s) falsa(s). 
 
I. ( ) A solução ótima inclui os itens 2 e 3. 
II. ( ) Organizando os itens por ordem crescente de peso e selecionando cada item nessa ordem, somos 
conduzidos a uma solução sub-ótima. 
III. ( ) A estratégia gulosa de selecionar os itens com maior razão vi/pi conduz à solução ótima. 
IV. ( ) Qualquer solução contendo o item com maior valor por peso é sub-ótima. 
 
Agora, assinale a alternativa que apresenta a sequência correta. 
Resposta Selecionada: 
V, V, F, V. 
Resposta Correta: 
V, V, F, V. 
Comentário da 
resposta: 
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 
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 seafirma 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 9 
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 10 
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) 
 
 
Terça-feira, 15 de Junho de 2021 00h41min48s BRT