Atividade Objetiva 4 - Complexidade de Algoritmos - NOTA 0.8 de 1.0

Prévia do material em texto

Atividade 4 Resultados para CRISTIANO MECCHI
LOTO
Pontuação desta tentativa: 0,8 de 1
Enviado 12 out em 13:09
Esta tentativa levou 2.997 minutos.
0,2 / 0,2 ptsPergunta 1
Leia o texto a seguir:
Um exemplo clássico de algoritmo de backtracking é o problema das
n-Rainhas. É preciso colocar n-rainhas em um tabuleiro de xadrez
tamanho n, de modo que não haja duas rainhas atacando uma à outra.
Nesse problema, precisamos encontrar todos os arranjos possíveis
das posições das n-rainhas no tabuleiro, tendo uma restrição que é a
condição de ataque.
Considerando as informações apresentadas, avalie as seguintes
asserções e a relação proposta entre elas.
I. O backtracking é conhecido por resolver problemas
recursivamente um passo de cada vez.
PORQUE
II. Trata-se de uma estratégia que encontra a solução viável
removendo as soluções que não satisfazem as restrições do
problema em qualquer ponto do tempo.
A respeito dessas asserções, assinale a opção correta:
 
A asserção I é uma proposição verdadeira, e a II é uma proposição
falsa.
 
As asserções I e II são proposições verdadeiras, e a II é uma
justificativa da I.
Correto!Correto!
A+
A
A-
NOTA: 0.8 de 1.0
 
As asserções I e II são proposições verdadeiras, mas a II não é uma
justificativa da I.
 As asserções I e II são ambas proposições falsas. 
 
A asserção I é uma proposição falsa, e a II é uma proposição
verdadeira.
A alternativa está correta.
A asserção I é uma proposição verdadeira, pois o backtracking
é responsável em fazer uma busca em profundidade utilizando
recursividade, desse modo, é encontrada a solução para o
problema apresentado.
A asserção II é uma proposição verdadeira, pois a estratégia
constrói uma árvore de espaço de estados, encontra todas as
soluções possíveis e mantém apenas aquelas que satisfaçam a
restrição dada.
A asserção II justifica a asserção I pois a solução viável só é
encontrada a partir das chamadas recursivas e da execução de
um passo de cada vez.
0,2 / 0,2 ptsPergunta 2
Leia o texto a seguir:
Na programação de computadores existem diversas técnicas de
desenvolvimento de algoritmos com o objetivo de otimizar problemas.
Dentre as principais técnicas temos: os algoritmos gulosos; os
algoritmos que utilizam backtracking; e a divisão e conquista.
Considerando as informações apresentadas, avalie as afirmações a
seguir:
I. Os algoritmos gulosos trabalham em problemas em que, a cada
passo, existe uma escolha que é ótima para o problema até aquele
A+
A
A-
passo.
II. Os algoritmos de backtracking são a melhor escolha, uma vez que
evita explorar todas as soluções existentes para obter a solução ótima
global.
III. Algoritmos de pesquisa como quicksort e mergesort utilizam a
técnica de divisão e conquista para localizar um valor em um array.
É correto o que se afirma em:
 II e III, apenas. 
 I e III, apenas. Correto!Correto!
 III, apenas. 
 II, apenas. 
 I e II, apenas. 
A+
A
A-
A alternativa está correta.
A afirmação I é verdadeira. Os algoritmos gulosos tentam
encontrar uma solução ótima global para resolver um problema
e uma de suas propriedades é a “escolha gulosa” ou “escolha
gananciosa”, em que uma solução ótima global (geral) pode ser
alcançada escolhendo a escolha ótima em cada etapa.
A afirmação II é falsa. Algoritmos de backtracking consideram
todas as combinações possíveis para resolver um problema,
exploram todas as opções possíveis (ramificações de uma
árvore, por exemplo) na busca de uma solução ótima. Logo, em
muitos casos é menos eficiente que outras estratégias como a
divisão e conquista, por exemplo.
A afirmação III é verdadeira. Algoritmos de divisão e conquista
dividem uma entrada em subproblemas, os quais serão
resolvidos isoladamente para facilitar a busca pela solução do
problema principal. Os algoritmos quicksort e mergesort são
baseados na estratégia de dividir e conquistar, o que resulta em
melhores resultados de processamento na busca por um valor
em um array.
0,2 / 0,2 ptsPergunta 3
Observe a figura a seguir:
A+
A
A-
Na figura apresentada, temos uma árvore com a representação da
solução da sequência de Fibonacci para F(n), onde n=5. Observe que
o valor de Fibonacci para 3, 2 e 1 foram calculados mais de uma vez.
Para valores de n pequenos, esse não é um problema, mas
considerando que o valor de n seja um número muito grande, o
processamento seria prejudicado.
Considerando as informações apresentadas, assinale a opção correta.
 
A recorrência elimina chamadas duplicadas como as F(2), F(1) e F(3)
apresentadas na figura.
 
A estratégia de recursão resolve o problema de chamadas duplicadas,
otimizando o algoritmo.
 
A programação dinâmica, assim como o algoritmo da mochila e de
backtracking, otimizam a execução desse algoritmo de Fibonacci.
 
O algoritmo de força bruta é a estratégia ideal para otimizar o algoritmo
de Fibonacci.
A+
A
A-
 
Podemos otimizar o algoritmo da sequência de Fibonacci utilizando
programação dinâmica.
Correto!Correto!
A alternativa está correta, pois para resolver o problema de
chamadas duplicadas, podemos utilizar a programação
dinâmica. Nesta abordagem, modelamos uma solução como se
fôssemos resolvê-la recursivamente, mas resolvemos do zero,
memorizando as soluções para os subproblemas (passos) que
tomamos para chegar ao topo.
0 / 0,2 ptsPergunta 4
Leia o texto a seguir:
Um algoritmo de pesquisa binária executa a estratégia de divisão e
conquista. Esse algoritmo pode ser descrito assim: pesquise um array
ordenado dividindo repetidamente o intervalo de pesquisa pela
metade; comece com um intervalo cobrindo todo o array. Se o valor da
chave de pesquisa for menor que o item no meio do intervalo, reduza o
intervalo para a metade inferior. Caso contrário, reduza-o para a
metade superior. Verifique repetidamente até que o valor seja
encontrado ou o intervalo esteja vazio.
Considerando as informações apresentadas, avalie as afirmações
abaixo:
I. Existem dois fundamentos da estratégia de divisão e conquista: um
deles é a condição de parada e o outro é a fórmula relacional.
II. Algoritmos como busca binária e busca sequencial são conhecidos
como divisão e conquista, tendo como complexidade O(log n).
III. Esse algoritmo consiste em duas etapas: dividir uma entrada (etapa
1, divisão) com o objetivo de encontrar uma solução para cada
subproblema (etapa 2, conquista).
É correto o que se afirma em:
 III, apenas. 
A+
A
A-
 II e III, apenas. 
 II, apenas. 
 I e III, apenas. ocê respondeuocê respondeu
 I, apenas. esposta corretaesposta correta
A alternativa está incorreta, pois apenas a afirmação I é
verdadeira.
A afirmação I é verdadeira, pois a estratégia de divisão e
conquista possui o fundamento da fórmula relacional (o
problema é quebrado recursivamente em subproblemas, os
quais serão resolvidos separadamente), e também o
fundamento da condição de parada (é a condição usada para
que a divisão e conquista deixe de ser aplicada).
A afirmação II é falsa, pois a busca sequencial não utiliza a
estratégia de divisão e conquista. Esse tipo de busca usa a
leitura sequencial dos dados em memória.
A afirmação III é falsa, pois os algoritmos de divisão e conquista
utilizam três etapas: divida o problema em subproblemas
(divisão); resolva cada subproblema (conquista); juste as
soluções dos subproblemas (combine).
0,2 / 0,2 ptsPergunta 5
Leia o texto a seguir:
Trata-se de uma técnica algorítmica onde o objetivo é obter todas as
soluções para um problema usando a abordagem de força bruta.
Consiste em construir um conjunto de todas as soluções de forma
incremental usando chamadas recursivas. Uma vez que um problema
teria restrições, as soluções que não as satisfazem serão removidas.
Qual tipo de algoritmo é definido no texto apresentado?
A+
A
A-
 Algoritmo de árvore binária. 
 Algoritmo de divisão e conquista. 
 Algoritmo de busca em largura. 
 Algoritmo de busca heurística. 
 Algoritmo de backtracking. Correto!Correto!
A alternativa está correta, pois backtracking é um algoritmo que
utiliza técnicasrecursivas para testar todas as soluções
possíveis e escolhe a melhor delas. Desse modo, o algoritmo
considera todas as combinações possíveis de saída para
resolver um problema computacional.
Pontuação do teste: 0,8 de 1
A+
A
A-