Turmas - 1º Semestre de 2023
Turmas
1º Semestre de 2023

A Relação de Equivalência Forte de Programas é especialmente importante na Ciência da Computação, pois, ao agrupar diferentes programas em classes de equivalência de programas cujas funções computadas coincidem, fornece subsídios para analisar outras propriedades dos programas, como por exemplo, sua complexidade estrutural, legibilidade, tamanho, tempo de execução entre outros critérios. Analise as assertivas a seguir, sobre a Relação de Equivalência Forte de Programas.

1. Para todo programa monolítico, existe um programa recursivo fortemente equivalente.
2. Para todo programa monolítico, existe um programa iterativo fortemente equivalente.
3. Para todo programa iterativo, existe um programa recursivo fortemente equivalente.
4. Para todo programa recursivo, existe um programa iterativo fortemente equivalente.

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.

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 potência b^e (para expoentes não negativos):
   a. b⁰ = 1
   b. b > 0: b^e = b * b^(e-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.

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. 12

c. 20

d. 33

e. 54

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 4 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.

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

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 adicionar_b vá_para R5;
R5: Faça adicionar_b vá_para R1;

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

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

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, 5/1 - 4/2 + 3/3 - 2/4 + 1/5.

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 - (n / i) vá_para R9;
R8: Faça s = s + (n / i) 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;

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 (j < (n - i - 1)) então
          escrever(+);
        senão
          se (j > (n - i - 1))
            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.

Desenvolver um programa recursivo, sobre uma máquina genérica, que calcule o valor de e^x utilizando a fórmula

e^x = x⁰/0! + x¹/1! + x²/2! + x³/3! + ... + xⁿ/n!

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

O valor de x será fornecido pelo usuário, podendo ser um valor (inteiro ou real) qualquer.

Por exemplo, caso o valor fornecido pelo usuário para n seja 4 e para x seja 2, o programa deverá apresentar como resposta o valor 7, ou seja, 2⁰/0! + 2¹/1! + 2²/2! + 2³/3! + 2⁴/4!.

Caso o usuário forneça um valor inválido para n, 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;

função potencia(b, e)
  se (e > 0)
    então retornar b * potencia(b, e - 1);
    senão retornar 1;
  fim se;
fim função;

função constante(x, n)
  se (n > 1)
    então retornar potencia(x, n - 1) / fatorial(n - 1) + constante(x, n - 1);
    senão retornar 1;
  fim se;
fim função;

programa
  ler(n);
  se (n > 0) então
    ler(x);
    escrever(constante(x, n);
  senão
      escrever(erro);
  fim se;
fim programa.