Turmas - 1º Semestre de 2019
Turmas
1º Semestre de 2019

Analise as assertivas a seguir:

1. A equivalência forte de programas permite analisar programas do ponto de vista da sua complexidade estrutural, ou outros critérios considerados relevantes (legibilidade, etc.), uma vez que do ponto de vista funcional eles são equivalentes.
2. Dado um programa P qualquer (monolítico, iterativo ou recursivo), é sempre possível obter um outro programa P’ (monolítico, iterativo ou recursivo) tal que P’ seja fortemente equivalente a P.
3. Uma função computada é um mapeamento entre o conjunto de valores de entrada e o conjunto de valores de saída, realizado através de uma sequência finita de computações.
4. A classe dos programas interativos está contida na classe dos programas monolíticos, que por sua vez está contida na classe dos programas recursivos e vice-versa.

Quais das assertivas apresentadas estão corretas?

a. Apenas as assertivas I e II.

b. Apenas as assertivas I e III.

c. Apenas as assertivas II e III.

d. Apenas as assertivas II e IV.

e. Apenas as assertivas III e IV.

Computação é a sequencia de estados que representa a execução de um programa numa certa máquina. Considerando o programa monolítico, utilizando instruções rotuladas, sobre a máquina 2_REG apresentado a seguir, qual das computações corresponde a execução do programa, caso a entrada fornecida pelo usuário seja 4.

R1: Faça subtrair_a vá_para R2;
R2: Se a_zero então vá_para Rx senão vá_para R3;
R3: Faça adicionar_b vá_para R4;
R4: Faça subtrair_a vá_para R5;
R5: Se a_zero então vá_para Rx senão vá_para R6;
R6: Faça adicionar_b vá_para R7;
R7: Faça adicionar_b vá_para R3;

a.

(R1, (4, 0))
(R2, (3, 0))
(R3, (3, 0))
(R4, (3, 1))
(R5, (2, 1))
(R6, (2, 1))
(R7, (2, 2))
(R3, (2, 3))
(R4, (2, 4))
(R5, (1, 4))
(R6, (1, 4))
(R7, (1, 5))
(R3, (1, 6))
(R4, (1, 7))
(R5, (0, 7))
(Rx, (0, 7))

b.

(R1, (3, 0))
(R2, (3, 0))
(R3, (3, 1))
(R4, (2, 1))
(R5, (2, 1))
(R6, (2, 2))
(R7, (2, 3))
(R3, (2, 4))
(R4, (1, 4))
(R5, (1, 4))
(R6, (1, 5))
(R7, (1, 6))
(R3, (1, 7))
(R4, (0, 7))
(R5, (0, 7))
(Rx, (0, 7))

c.

(R1, (4, 0))
(R2, (3, 0))
(R3, (3, 0))
(R4, (3, 1))
(R5, (2, 1))
(R6, (2, 1))
(R7, (2, 2))
(R3, (2, 3))
(R4, (2, 4))
(R5, (1, 4))
(R6, (1, 4))
(R7, (1, 5))
(R3, (1, 6))
(R4, (1, 7))
(R5, (0, 7))

d.

(R1, (3, 0))
(R2, (3, 0))
(R3, (3, 1))
(R4, (2, 1))
(R5, (2, 1))
(R6, (2, 2))
(R7, (2, 3))
(R3, (2, 4))
(R4, (1, 4))
(R5, (1, 4))
(R6, (1, 5))
(R7, (1, 6))
(R3, (1, 7))
(R4, (0, 7))
(R5, (0, 7))

e.

(R1, (4, 0))
(R2, (3, 0))
(R3, (3, 0))
(R4, (3, 1))
(R5, (2, 1))
(R6, (2, 1))
(R7, (2, 2))
(R3, (2, 3))
(R4, (2, 4))
(R5, (1, 4))
(R6, (1, 4))
(R7, (1, 5))
(R3, (1, 6))
(R4, (1, 6))
(R5, (0, 6))
(Rx, (0, 7))

Considere o programa recursivo apresentado a seguir:

função ff(n)
  se (n == 1)
    então retornar 1;
  fim se;

  se (n % 2 == 0)
    então retornar ff(n / 2);
  fim se;

  retornar ff((n-1)/2) + ff((n+1)/2);
fim função;

função principal
  ler(a);
  se (a > 0)
    então escrever(ff(a));
    senão escrever(erro);
  fim se;
fim função;

Qual será o resultado da execução desse programa recursivo, caso o usuário forneça como entrada para o mesmo o valor 7?

a. 1.

b. 2.

c. 3.

d. 4.

e. 5.

Considere a especificação da máquina 4REG apresentada a seguir:

4REG = (N⁴, N, N, armazenar, retornar, {decA, incB, decB, incC, decC, incD}, {nilA, nilB, nilC}), onde:

1. armazenar → armazena o valor fornecido pelo usuário no registrador A, zerando os demais;
2. retornar → retorna o valor armazenado no registrador D;
3. decA → decrementa o registrador A em uma unidade, caso o mesmo seja maior do que zero;
4. incB → incrementa o registrador B em uma unidade;
5. decB → decrementa o registrador B em uma unidade, caso o mesmo seja maior do que zero;
6. incC → incrementa o registrador C em uma unidade;
7. decC → decrementa o registrador C em uma unidade, caso o mesmo seja maior do que zero;
8. incD → incrementa o registrador D em uma unidade;
9. nilA → retornar verdade caso o valor do registrador A seja zero, caso contrário, falso;
10. nilB → retornar verdade caso o valor do registrador B seja zero, caso contrário, falso;
11. nilC → retornar verdade caso o valor do registrador C seja zero, caso contrário, falso;

Qual será o resultado da execução do programa monolítico, utilizando instruções rotuladas, sobre a máquina 4REG, caso a entrada do usuário seja 5 unidades?

R01: Se nilA então vá_para R00 senão vá_para R02;
R02: Faça decA vá_para R03;
R03: Faça incB vá_para R04;
R04: Faça incD vá_para R05;
R05: Faça incD vá_para R06;
R06: Faça incD vá_para R07;
R07: Se nilA então vá_para R08 senão vá_para R02;
R08: Faça decB vá_para R09;
R09: Faça incC vá_para R10;
R10: Faça incD vá_para R11;
R11: Faça incD vá_para R12;
R12: Se nilB então vá_para R13 senão vá_para R08;
R13: Faça decC vá_para R14;
R14: Faça incD vá_para R15;
R15: Se nilC então vá_para R00 senão vá_para R13;

a. 10 unidade.

b. 15 unidades.

c. 20 unidades.

d. 25 unidades.

e. 30 unidades.

(Diverio, 2000) Um fluxograma nada mais é do que uma representação gráfica de um algoritmo, através de formas geométricas previamente convencionados, permitindo a descrição clara e precisa da sequência de um processo, facilitando a compreensão da lógica utilizada pelo programador. Diante disso, escreva um programa monolítico, utilizando fluxograma, sobre uma máquina genérica, que leia três números do usuário e os apresente em ordem decrescente. Por exemplo, caso os números fornecidos pelo usuário sejam 5, 7 e 4, o programa deverá apresentar como resposta a sequência 7, 5 e 4.

Programas iterativos substituem desvios incondicionais por estruturas cíclicas, permitindo um melhor controle e manutenção de programas. A noção de programa iterativo deu origem às técnicas de programação estruturada, inspirando toda uma geração de linguagens de programação, como Pascal e C. Diante disso, escreva um programa iterativo, sobre uma máquina genérica, equivalente a função recursiva apresentada a seguir.

função xpto (n)
  se (n == 1 || n == 2)
    então retornar n;
    senão retornar xpto(n - 1) + n * xpto(n – 2);
  fim se;
fim função;

função xpto (n)
  se (n == 1 || n == 2) então
    retornar n;
  senão
    a = 2;
    b = 1;
    i = 3;
    enquanto (i <= n) faça
      aux = a;
      a = a + i * b;
      b = aux;
      i = i + 1;
    fim enquanto;
    retornar a;
  fim se;
fim função;

A seguinte função calcula o maior divisor comum dos inteiros estritamente positivos m e n.

função Euclides (m, n)
  faça
    r = m % n;
    m = n;
    n = r;
  enquanto (r != 0);
  retornar m; 
fim função;

Recursão é um método de programação no qual uma função pode chamar a si mesma. Muitos problemas em computação tem a propriedade de que cada instância sua contém uma instância menor do mesmo problema. Diante disso, escreva um programa recursivo, sobre uma máquina genérica, que seja equivalente a função Euclides.

função Euclides (m, n)
  se (m % n == 0)
    então retornar n;
    senão retornar Euclides(n, m % n);
  fim se;
fim função;

(Diverio, 2000) Um programa monolítico é estruturado usando desvios condicionais e incondicionais, não fazendo uso explícito de mecanismos auxiliares de programação que permitam uma melhor estruturação do controle, como iteração, subdivisão e recursão, de modo que a lógica é distribuída por todo o bloco (monólito) que constitui o programa. Desenvolver um programa monolítico, utilizando instruções rotuladas, sobre a máquina 2_REG, que apresente a média da somatória de 1 a n. Por exemplo, caso o valor de n seja 7, o programa deverá apresentar como resposta 4, ou seja, (1 + 2 + 3 + 4 + 5 + 6 + 7) / 7.

R1: Se a_zero então vá_para Rx senão vá_para R2;
R2: Faça adicionar_b vá_para R3;
R3: Faça subtrair_a vá_para R4;
R4: Faça subtrair_a vá_para R1;