Complexidade de Algoritmos - Atividade Objetiva 02

Prévia do material em texto

Pergunta 1
0,2 / 0,2 pts
	Leia o texto a seguir:
 
Uma variável possui papel fundamental em um código, sendo responsável por guardar dados para uma manipulação posterior. Uma variável do tipo inteiro pode ser utilizada em uma estrutura de repetição e, desse modo, podemos, por exemplo, gerar uma sequência somente com números divisíveis por 2 (números pares).
 
Considere o código a seguir:
 
	1
	for(int x = 1; x < 10; x++)
	2
	        if(x % 4 != 0 && x % 2 == 0)
	3
	                for(int y = 1; y < 5; y++)
	4
	                        Console.WriteLine(y);
 
 
	Considerando o código apresentado, avalie as afirmações abaixo:
 
I. A linha 4 representa 8 instruções que serão executadas por esse programa.
II. Esse algoritmo tem um tempo de execução quadrático ou O(n²).
III. A linha 2 será executada quando o valor de x for par e divisível por 4.
 
É correto o que se afirma em:
Resposta corretaCorreto!
  
I, apenas.
 
  
III, apenas.
 
  
II, apenas.
 
  
II e III, apenas.
 
  
I e II, apenas.
 
A alternativa está correta.
A afirmação I é verdadeira, pois o laço “for” externo executará 9 vezes (de 1 a 9, exceto o 10) o bloco que se inicia na linha 2. Como a única condição para entrar no bloco “if” da linha 2 é que o valor de x não seja divisível por 4 E o valor de x seja par (ou divisível por 2), então a linha 4 será executada 8 vezes apresentando os valores 12341234.
A afirmação II é falsa, pois o algoritmo somente seria quadrático se o tempo de execução variasse em função de uma variável n. Observe que os valores limites das estruturas de repetição for (tanto para o x quanto para o y) não varia, ou seja, o algoritmo é constante (o tempo de execução sempre será o mesmo).
A afirmação III é falsa, pois a linha 2 será executada quando o valor de x for divisível por 2 (ou seja, quando for par) e quando o valor de x não for divisível por 4.
 
Pergunta 2
0,2 / 0,2 pts
	Leia o texto e observe o código a seguir:
 
A linguagem C#, assim como outras, permite que criemos funções para organizar o nosso código. Dentro dessas funções, podemos adicionar estruturas de repetição, estruturas condicionais e invocar outras funções nativas da linguagem.
 
	1
	public void print(int str){
	2
	         Console.WriteLine(str);
	3
	}
	4
	 
	5
	public static void Main (string[] args) {
	6
	        Program x = new Program();
	7
	       
	8
	         int cont, y;
	9
	         y = 10; cont = 0;
	10
	        while(cont < y){
	11
	                x.print(cont);
	12
	                cont++;
	13
	         }
	14
	}       
 
 
	Considerando o código apresentado, avalie as afirmações abaixo:
 
I. O código apresentará os números de 0 até 10 na tela pela função print.
II. Esse algoritmo executará, no melhor caso, pelo menos 30 instruções.
III. No pior caso, esse é um algoritmo com crescimento de tempo linear.
 
É correto o que se afirma em:
 
  
I e II, apenas.
 
Resposta correta
  
II, apenas.
 
  
III, apenas.
 
Você respondeu
  
I, apenas.
 
  
II e III, apenas.
 
A alternativa está incorreta, pois apenas as afirmações II e III são verdadeiras.
A afirmação I é falsa, pois o código apresentará os números de 0 a 9 na tela.
A afirmação II é verdadeira, pois a estrutura “while” (linha 10) executará 10 vezes. Como as linhas 11 e 12 estão internas a esse laço “while”, então cada uma será executada 10 vezes também. Logo somente no “while” serão 30 instruções. Devemos também considerar que temos mais 4 instruções antes de entrar no laço “while”; por fim, a linha 2 também será executada 10 vezes, sempre que o laço “while” a chamar. Logo teremos mais de 30 instruções.
A afirmação III é falsa, pois o crescimento desse algoritmo é constante, e não linear. Isso ocorre porque o valor de 'y' é fixo em 10, o que significa que o número de iterações do loop é sempre o mesmo, independentemente do tamanho da entrada. Como resultado, o tempo de execução do algoritmo não é afetado pelo tamanho da entrada e permanece constante. O crescimento de tempo desse algoritmo poderia ser considerado linear se o y fosse variável, em que o “while” seria executado em função dessa variável y. Logo, quando y fosse 10, teríamos 30 instruções, quando y fosse 100, teríamos 300 instruções, e assim por diante, em um crescimento linear. Mas, como y está fixado com valor 10, o resultado será constante.
 
Pergunta 3
0,2 / 0,2 pts
Analise com atenção os três algoritmos apresentados a seguir:
 
Figura 1 - Algoritmo A com um laço de repetição for
 
Figura 2 - Algoritmo B com um laço de repetição for
 
Figura 3 - Algoritmo C com laço de repetição while
 
Considerando as informações apresentadas, assinale a opção correta.
Resposta correta
  
No pior caso, o algoritmo A (figura 1) executará 308 instruções para um n igual a 102.
 
  
No pior caso, o algoritmo B (figura 2) executará 3n+2 instruções, assim como o algoritmo A (figura 1).
 
Você respondeu
  
No pior caso, tanto o algoritmo C (figura 3) quanto o algoritmo A (figura 1) são O(n).
 
A alternativa está incorreta, pois o algoritmo C sempre executará o laço for 0 vezes, afinal, esse é o valor máximo que a variável i pode alcançar. Desse modo, o algoritmo C terá 0 instrução, não tendo um crescimento linear. O algoritmo A tem um tempo de execução 3n+2, logo, podemos pegar o valor de n (que nesse é 102) e jogar nessa equação, logo, 3*102 + 2 = 306 + 2 = 308.
  
No pior caso, o algoritmo C (figura 3) e o algoritmo A (figura 1), terão o mesmo número de instruções.
 
  
No pior caso, os tempos de execução dos algoritmos A e B (figura 1 e figura 2, respectivamente) são iguais.
 
 
Pergunta 4
0,2 / 0,2 pts
	Leia o texto a seguir:
 
O pseudocódigo apresentado é responsável por receber um valor de temperatura e verificar se tal valor está em um determinado intervalo.
 
	Início
	          se temperatura > 40
	                   escreva(“ligar ar-condicionado”)
	                   escreva(“fechar as janelas”)
	          Senão
	                   escreva(“abrir as janelas”)
	          fim-se
	fim      
	Considerando que o valor da variável temperatura é igual a 40, podemos afirmar que o algoritmo apresentado é um
  
algoritmo exponencial.
 
  
algoritmo quadrático.
 
  
algoritmo linear.
 
Resposta correta
  
algoritmo constante.
 
Você respondeu
  
algoritmo de recorrência.
 
A alternativa está incorreta, pois um algoritmo de recorrência chama a mesma função mais de uma vez, ou seja, é recursivo. Observe que o tempo de execução desse algoritmo não depende do tamanho de entrada de n. Independentemente do valor da temperatura, sempre teremos um número constante de instruções, por isso é considerado como sendo um algoritmo de tempo constante.
 
Pergunta 5
0,2 / 0,2 pts
Leia o texto a seguir:
Às vezes, um problema é muito difícil ou muito complexo para ser resolvido porque é muito grande. Se o problema puder ser dividido em versões menores de si mesmo, poderemos encontrar uma maneira de resolver uma dessas versões menores e, em seguida, conseguirmos encontrar uma solução para o problema inteiro. Essa é a ideia por trás da recursão.
Considerando as informações apresentadas, avalie as afirmações a seguir:
I. Algoritmos recursivos dividem um problema em partes menores até atingir uma condição de parada.
II. Existe a recursividade direta e indireta, sendo esta última caracterizada pela ausência de condição de parada.
III. A recursividade foi criada para resolver problemas de modo mais rápido e eficiente que aqueles problemas resolvidos por algoritmos iterativos.
IV. Recursividade pode ser definida em termos de si mesma: "Recursão: [...] para obter mais informações, consulte Recursão".
É correto o que se afirma em:
Você respondeu
  
I e III, apenas.
 
Resposta correta
  
I e IV, apenas.
 
  
III e IV, apenas.
 
  
II e IV, apenas.
 
  
II e III, apenas.
 
Alternativa incorreta, pois somente os itens I  e IV são verdadeiros.
A afirmação I é verdadeira, pois essa é a definição de recursividade: o objetivo é dividir um determinado problema até chegar a uma condição de parada e, ao atingi-la, os valores são retornadose a solução é dada.
A afirmação II é falsa, pois toda solução recursiva precisa ter uma condição de parada, senão o algoritmo ficaria executando em um loop infinito.
A afirmação III é falsa, pois a ideia por trás da recursividade é facilitar a solução de problemas; porém, todo problema que pode ser resolvido de modo iterativo pode ser resolvido com recursividade, o que modificará a dificuldade de implementação. Desse modo, não é possível afirmar que um problema recursivo será mais (ou menos) eficiente que um algoritmo iterativo.
A afirmação IV é verdadeira, pois a definição apresentada, por si só, já é recursiva, uma vez que ela “chama” a si própria.
Pontuação do teste: 1 de 1