A4 - Análise de Algoritmos Respondido

Prévia do material em texto

· Pergunta 1
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, e a II é 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 2
0 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, F.
	Resposta Correta:
	 
V, V, F, V.
	Comentário da resposta:
	Resposta incorreta. Analise as opções possíveis para o carregamento da mochila e verifique qual é a solução ótima. Compare essa solução com as estratégias apresentadas.
	
	
	
· Pergunta 3
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 4
0 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:
	 
II e III.
	Resposta Correta:
	 
I, II e III.
	Comentário da resposta:
	Resposta incorreta. Execute o passo a passo do algoritmo e analise a configuração dos vetores à medida que a ordenação acontece.
	
	
	
· Pergunta 5
0 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 verdadeiras, e a II é uma justificativa correta da I.
	Resposta Correta:
	 
As asserções I e II são proposições falsas.
	Comentário da resposta:
	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
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 7
0 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:
	 
F, V, F, V.
	Resposta Correta:
	 
V, V, F, V.
	Comentário da resposta:
	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 8
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)
	
	
	
· Pergunta 9
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 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.