Projeto e Analise de Algoritmo - Nota 10 - Semana 3 - Univesp

Prévia do material em texto

Fazer teste: Atividade para Avaliação - Semana 3Projeto e Análise de Algoritmos - EEM002 - Turma 001 3 - Solução de recorrências
Fazer teste: Atividade para Avaliação - Semana 3 
Informações do teste
Descrição
Instruções
Várias tentativas Este teste permite 3 tentativas. Esta é a tentativa número 1.
Forçar conclusão Este teste pode ser salvo e retomado posteriormente.
Suas respostas foram salvas automaticamente.
Atividade para avaliação
1. Para responder a esta atividade, selecione a(s) alternativa(s) que você considerar correta(s);
2. Após selecionar a resposta correta em todas as questões, vá até o �m da página e pressione “Enviar teste”.
3. A cada tentativa, as perguntas e alternativas são embaralhadas
Consulte os gabaritos dessa disciplina no menu lateral.
Olá, estudante!
Pronto! Sua atividade já está registrada no AVA.
PERGUNTA 1
Sobre as relações de comparação assintótica (para n su�cientemente grande) das funções: 2π, log(n), , n2 e n*log(n), assinale a alternativa correta.
As funções listadas possuem o mesmo comportamento assintótico para n su�cientemente grande, não sendo possível diferenciá-las.
A função n2 é a que possui maior crescimento assintótico dentre todas as funções mencionadas. 
função log(n) cresce mais rápido do que a função .
A função 2π cresce mais rápido do que a função n2
A função n*log(n) cresce mais lentamente do que a função log(n).
1 pontos   Salva
PERGUNTA 2
Dado o seguinte algoritmo recursivo que recebe como entrada um número inteiro positivo. 
  
Algoritmo A: rec1(n) 
1  se n <= 1 
2    então devolva n 
3    senão devolva rec1(n-1) + rec1(n-2) 
O algoritmo executa com complexidade de tempo O(n^2). 
O algoritmo é polinomial.
Para n su�cientemente longo, o tempo de espera pelo resultado será proibitivo.
Não é possível encontrar uma função f(n) tal que a complexidade do algoritmo seja O(f(n)).
O algoritmo possui equação de recorrência da forma: T(n) = T(n-1) + T(n-2) + θ(n).
1 pontos   Salva
PERGUNTA 3
Um determinado algoritmo recursivo possui o comportamento determinado pela seguinte relação de recorrência: T(n) = 4*T(n-2) + 1. É correto a�rmar que a classe desse algoritmo é: 
exponencial
quadrático
linear
cúbico
logarítmico
1 pontos   Salva
PERGUNTA 4
A notação Ω deve ser entendida como um limitante inferior assintótico. Uma maneira de provar que T(n) = Ω(f(n)) seria utilizar a de�nição de que T(n) >= c f(n), sendo necessário de�nir um valor positivo para a constante c, e um valor inicial n0 não negativo para n. Feito isso, precisa ser provado que a relação é válida para todo n >= n0. Sobre essa notação, assinale a alternativa
correta.
Se dizemos que T(n) = Ω(f(n)), então podemos concluir que T(n) >= f(n) para todo n. 
Assumindo que seja verdade que T(n) = Ω(f(n)), é possível atribuir um valor arbitrário para c e, logo em seguida, computar um valor adequado para n0 de modo que a relação T(n)>=c*f(n) seja verdade para todo n >= n0.
Uma maneira de provar que T(n) = 0.00001n2+100n+3 é Ω(n2) seria atribuir os valores c = 104 e n0 = 1 para as constantes. Nesse caso, o passo �nal seria provar que 0.00001n2+100n+3 >= cn2 para todo n maior ou igual a n0.
Se T(n) = 10n2+3n+1, a de�nição da notação Ω permite provar que T(n) = Ω(n2) e impede que seja provado que T(n) = Ω(n3), T(n) = Ω(n4) e T(n) = Ω(n5).
Uma maneira de provar que T(n) = 100n2 é Ω(n3) seria atribuir valores c = -1 e n0 = 0 para as constantes. Nesse caso, o passo �nal seria provar que 100n2 >= cn3 para todo n maior ou igual a n0.
1 pontos   Salva
PERGUNTA 5
A notação O deve ser entendida como um limitante superior assintótico. Assim, uma maneira de provar que T(n) = O(f(n)) seria utilizando a de�nição de que T(n) <= c f(n), sendo necessário de�nir um valor positivo para a constante c, e um valor inicial n0 não negativo. Nesse caso, precisa ser provado que a relação é válida para todo n >= n0. Sobre essa notação, assinale a
alternativa correta.
Uma maneira de provar que T(n) = 100n2 é O(n3) seria atribuir valores c = 1 e n0. = 10 para as constantes. Nesse caso, o passo �nal seria provar que 100n2 <= c n3 para todo n maior ou igual a n0.
Uma maneira de provar que T(n) = 0.00001n2 +100n+3 é O(n2 ) seria atribuir os valores c = 104 e n0 = 1 para as constantes. Nesse caso, o passo �nal seria provar que 0.00001n2+100n+3 <= cn2 para todo n maior ou igual a n0.
Se T(n) = 10n2+3n+1, a de�nição da notação O permite provar que T(n) = O(n2) e impede que seja provado que T(n) = O(n3), T(n) = O(n4) e T(n) = O(n5).
Se dizemos que T(n) = O(f(n)), então podemos concluir que T(n) <= f(n) para todo n.
Assumindo que seja verdade que T(n) = O(f(n)), é possível atribuir um valor arbitrário para c e, logo em seguida, computar um valor adequado para n0 de modo que a relação T(n)  <= c f(n) seja verdade para todo n >= n0.
1 pontos   Salva
PERGUNTA 6
Dadas as funções f(n), g(n) e h(n), e hipóteses de que pertencem a alguma classe dentro de  limites assintóticos usando a notação  O, Ω e θ, podemos a�rmar que: 
f(n) = O(g(n)) se, e somente se, g(n) = Ω(f(n)).
Se f(n) = Ω(g(n)) e g(n) = Ω(h(n)), então f(n) = θ(h(n)).
Se f(n) = Ω(g(n)) e g(n) = O(h(n)), então f(n) = θ(h(n)).
Se f(n) = O(g(n)) e g(n) = O(h(n)), então f(n) = θ(h(n)).
Se f(n) = O(g(n)) e g(n) = Ω(h(n)), então f(n) = θ(h(n)).
1 pontos   Salva
PERGUNTA 7
Ao tentar resolver uma equação de recorrência, um aluno percebeu que precisaria resolver o seguinte somatório: S = 2*1 + 3*3 + 4 * 9 + 5 * 27 + ... + (1+n)*3(n-1). Ao �nal de algumas tentativas, ele encontrou uma equação para S e conseguiu provar por indução que a sua equação é verdadeira. Qual das alternativas a seguir mostra uma equação correta que poderia ter sido
encontrada pelo aluno.
S = (2*3n + n*3(n+1) - 7)/4
S = (3 (n+1) + 2*n*3(n+1) - 19)/4
S = (3n + n*3n + 2)/4
S = (5*3n + n*3(n+1) - 16)/4
S = ((0.5 + n)*(3n))/2    - 0.25
1 pontos   Salva
PERGUNTA 8
Para um mesmo problema, o Algoritmo A foi provado como O(n2) e o Algoritmo B como O(n3). Nesse caso, assinale a alternativa correta.
O Algoritmo A executa mais rápido que o Algoritmo B.
O Algoritmo B executa mais rápido que o Algoritmo A.
O Algoritmo A executa mais rápido que o Algoritmo B quando fornecemos uma entrada su�cientemente grande.
O Algoritmo B executa mais rápido que o Algoritmo A quando fornecemos uma entrada su�cientemente grande.
As informações não são su�cientes para de�nir quem executará mais rápido na prática, independentemente do tamanho da entrada. 
1 pontos   Salva
PERGUNTA 9
Dados os dois algoritmos a seguir que recebem como entrada um número inteiro a e um número natural n. 
  
Algoritmo A: rec1(a, n) 
1   se n = 0 
2     então devolva 1 
3     senão devolva a*rec1(a, n-1) 
  
Algoritmo B: rec2(a, n) 
1   se n = 0  
2      então devolva 1 
3      senão term = rec2(a, piso(n/2)) 
4         mult = term * term 
5         se n ímpar 
6               então mult = mult * a 
7         devolva mult 
  
Assinale a alternativa correta: 
O Algoritmo A possui a seguinte relação de recorrência se n >= 1: T(n) = T(n-1).
O Algoritmo B fará muito mais chamadas recursivas do que o Algoritmo A para n su�cientemente grande.
O Algoritmo B possui a seguinte relação de recorrência se n >= 1: T(n) = T(piso(n/2)) + θ(1)
O Algoritmo B possui a seguinte relação de recorrência se n >= 1: T(n) = T(n-1) + θ(1).
O Algoritmo A fornece uma resposta diferente do Algoritmo B para uma mesma entrada.
1 pontos   Salva
PERGUNTA 10
Dados os dois algoritmos a seguir que recebem como entrada um vetor A e um número inteiro n positivo e maior que zero. 
Algoritmo A: somaRec(A, n) 
1 se n = 1 
2   então devolva A[1] 
3   senão x = somaRec(A, n-1) 
4     devolva A[n] + x 
  
Algoritmo B: somaIter(A, n) 
1 soma <- 0 
2 para j <- 1 até n faça 
3    soma <- soma + A[j] 
4 devolva soma 
  
Assinale a alternativa correta: 
A complexidade de tempo dos algoritmos é diferente, dado que um deles é recursivo e o outro é iterativo.
A prova de correção do Algoritmo B deve ser feita utilizando indução matemática.
Os algoritmosproduzem saídas diferentes para as mesmas entradas. 
O Algoritmo A possui complexidade de tempo O(n).
A prova de correção do Algoritmo A deve ser feita utilizando a técnica dos invariantes do laço de repetição.
1 pontos   Salva
? Estado de Conclusão da Pergunta:
 Salvar todas as respostas Salvar e Enviar
https://ava.univesp.br/webapps/blackboard/execute/courseMain?course_id=_2041_1
https://ava.univesp.br/webapps/blackboard/content/listContent.jsp?course_id=_2041_1&content_id=_353731_1&mode=reset