Análise de Algoritmos ATIVIDADE 4

Prévia do material em texto

• 
• Pergunta 1 
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 2 
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 3 
0 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: 
 
Como A[ i ] = A[ j ] no vetor de origem, então as posições relativas entre esses 
elementos podem ser alteradas no vetor de saída B. 
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 incorreta. Analise como o algoritmo counting sort executa a 
ordenação de um vetor A qualquer contendo dois ou mais valores iguais. 
Observe como o vetor auxiliar C é usado para posicionar os elementos em B. 
 
 
 
• Pergunta 4 
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 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 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çãofechada 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 5 
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 6 
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 7 
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 8 
0 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: 
F, F, V, V. 
Resposta Correta: 
V, V, F, V. 
Comentário 
da resposta: 
Resposta incorreta. Observe como a estratégia gulosa proposta nas 
afirmativas funciona e verifique se ela conduz a uma solução ótima para 
qualquer valor informado. Além disso, a estratégia gulosa de ordenar as tarefas 
por tempo de processamento, do menor para o maior, e executá-las nessa 
ordem conduz a uma solução ótima para qualquer entrada. De fato, é preciso 
observar que o problema exibe uma subestrutura local ótima: se executarmos 
a primeira tarefa em uma solução ótima, obteremos uma solução ótima, 
executando as tarefas restantes de uma forma que minimize o tempo médio de 
conclusão. 
 
• Pergunta 9 
1 em 1 pontos 
 
Algoritmos gulosos constituem uma poderosa ferramenta para asoluçã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 10 
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.