A4 ANALISE DE ALGORITMOS UAM

Prévia do material em texto

Curso GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 
202110.ead-14790.01 
Teste ATIVIDADE 4 (A4) 
 Status Completada 
Resultado da 
tentativa 
9 em 10 pontos 
 
 
 Pergunta 1 
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: 
o T( i, j ) = j, se i = 0 
o 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): 
o Somador(2, 8) 
o Somador(1, 9) 
o Somador(0, 10) 
 
 
 
 Pergunta 2 
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 3 
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: 
 
o x · y = 0, se x = 0 
o x · y = ⌊x/2⌋ · (y + y), se x é par 
o 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 4 
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 5 
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 6 
1 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: 
I, II e III. 
Resposta Correta: 
I, II e III. 
Comentário 
da resposta: 
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. 
 
 
 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: 
o a1 = ⌊n/c1⌋ e nq = n mod c1 
o a2 = ⌊nq/c2⌋ e nd = nq mod c2 
o a3 = ⌊nd/c3⌋ e nk = nq mod c2 
o 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 
0 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: 
 
As asserções I e II são proposições verdadeiras, mas a II 
não é uma justificativa correta da I. 
 
Resposta Correta: 
A asserção I é uma proposição falsa, e a II é uma 
proposição verdadeira. 
 
Comentário da 
resposta: 
Resposta incorreta. Considere o problema sob a 
perspectiva dos conceitos de computabilidade e busque 
identificar a sua classificação. 
 
 
 
 Pergunta 9 
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 umalgoritmo 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 10 
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 v i/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.