Turmas - 1º Semestre de 2022
Turmas
1º Semestre de 2022

(vale 1,0 ponto) A Relação de Equivalência Forte de Programas (EFP) define que um par de programas pertence à relação se as correspondentes funções computadas coincidem para:

a. uma dada máquina. Tal EFP fornece subsídios à análise do acoplamento por controle entre módulos.

b. um par de máquinas que não podem simular-se mutuamente. Tal EFP fornece subsídios para a construção da coesão sequencial entre módulos.

c. um par de máquinas que podem simular-se mutuamente. Tal EFP fornece subsídios para a construção da coesão comunicacional entre módulos.

d. qualquer máquina. Tal EFP fornece subsídios à análise da complexidade estrutural de programas.

e. uma dada máquina. Tal EFP fornece subsídios à análise da complexidade estrutural de programas.

(vale 1,0 ponto) Considere os algoritmos apresentados a seguir:

1. Números naturais:
   a. 0 é um número natural.
   b. o sucessor de um número natural é um outro número natural.
2. Estruturas de árvores:
   a. 0 é uma árvore (chamada árvore vazia)
   b. Se t1 e t2 são árvores, então a estrutura que consiste de um nó com dois ramos t1 e t2 é também uma árvore.
3. A função fatorial n! (para inteiros não negativos):
   a. 0! = 1
   b. n > 0: n! = n * (n – 1)!

São exemplos de algoritmos recursivos os que constam em:

a. III.

b. I e II.

c. I e III.

d. II e III.

e. I, II e III.

(vale 1,0 ponto) 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. Considere o programa recursivo apresentado a seguir:

função xpto(n, a, b)
 se (n > 1)
   então retornar b * xpto(n - 1, b, b + a);
   senão retornar b;
 fim se;
fim função;

função principal
 ler(n);
 se (n > 0)
   então escrever(xpto(n, 0, 1));
   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 5?

a. 7

b. 15

c. 30

d. 150

e. 240

(vale 1,0 ponto) Considere a especificação da máquina 4_REG apresentada a seguir:

4_REG = (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 4_REG, 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: Se nilA então vá_para R06 senão vá_para R02;
R06: Se nilB então vá_para R00 senão vá_para R07;
R07: Faça decB vá_para R08;
R08: Se nilB então vá_para R16 senão vá_para R09;
R09: Faça decB vá_para R10;
R10: Se nilB então vá_para R15 senão vá_para R11;
R11: Faça decB vá_para R12;
R12: Se nilB então vá_para R14 senão vá_para R13;
R13: Faça decB vá_para R06;
R14: Faça incD vá_para R15;
R15: Faça incD vá_para R16;
R16: Faça incD vá_para R00;

a. 3 unidades.

b. 4 unidades.

c. 5 unidades.

d. 6 unidades.

e. 7 unidades.

(vale 1,0 ponto) Desenvolver um programa monolítico, utilizando instruções rotuladas, sobre a máquina 2_REG, que implemente a função B = (A * 2) + (A - 2).

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

(vale 1,0 ponto) Desenvolver um programa monolítico, utilizando instrução rotulada, sobre uma máquina genérica, que calcule o valor da série.

S = (1 / n) - (2 / (n - 1)) + (3 / (n - 2)) - (4 / (n - 3)) + ... + n / 1

O valor de n será fornecido pelo usuário, devendo ser um valor inteiro e positivo.

Por exemplo, caso o valor fornecido pelo usuário para n seja 5, o programa deverá apresentar como resposta o valor 3.7, ou seja, 1/5 - 2/4 + 3/3 - 4/2 + 5/1.

Caso o usuário forneça um valor inválido para n, o programa deverá apresentar uma mensagem de erro.

R1: Faça ler(n) vá_para R2;
R2: Se (n > 0) então vá_para R3 Senão vá_para R12;
R3: Faça i = 1 vá_para R4;
R4: Faça s = 0 vá_para R5;
R5: Se (n > 0) então vá_para R6 Senão vá_para R11;
R6: Se (i % 2 == 0) então vá_para R7 Senão vá_para R8;
R7: Faça s = s - (i / n) vá_para R9;
R8: Faça s = s + (i / n) vá_para R9;
R9: Faça i = i + 1 vá_para R10;
R10: Faça n = n - 1 vá_para R5;
R11: Faça escrever(s) vá_para Rx;
R12: Faça escrever(erro) vá_para Rx;

(vale 1,0 ponto) Desenvolver um programa iterativo, sobre uma máquina genérica, que apresente o seguinte desenho, conforme o valor de n:

O valor de n será fornecido pelo usuário, devendo ser um valor inteiro e positivo.

Utilize escrever(\n) para escrever uma nova linha.

Caso o usuário forneça um valor inválido para n, o programa deverá apresentar uma mensagem de erro.

programa
  ler(n);
  se (n >= 0) então
    i = 0;
    enquanto (i < n) faça
      j = 0;
      enquanto (j < n) faça
        se (i > j) então
          escrever(+);
        senão
          se (i < j)
            então escrever(*);
            senão escrever(0);
          fim se;
        fim se;
        j = j + 1;
      fim enquanto;
      i = i + 1;
      escrever(\n);
    fim enquanto;
  senão
    escrever (erro);
  fim se;
fim programa.

(vale 1,0 ponto) Desenvolver um programa recursivo, sobre uma máquina genérica, que apresente o valor de S, dado pela fórmula:

S = N! / (P! * (N - P)!)

O valor de N e P serão fornecidos pelo usuário, devendo ser números inteiros e positivos, sendo o primeiro (N) sempre maior que o segundo (P).

Caso o usuário forneça valores inválidos para N ou P, o programa deverá apresentar uma mensagem de erro.

função fatorial(n)
  se (n > 0)
    então retornar n * fatorial(n - 1);
    senão retornar 1;
  fim se;
fim função;

programa
  ler(n);
  se (n > 0) então
    ler(p);
    se (p > 0) então
      se (n > p)
        então escrever(fatorial(n) / fatorial(p) * fatorial(n - p));
        senão escrever(erro);
      fim se;
    senão
      escrever(erro);
    fim se;
  senão
    escrever(erro);
  fim se;
fim programa.