Turmas - 1º Semestre de 2024
Turmas
1º Semestre de 2024

(POSCOMP, 2022) Sobre os testes de condições em linguagem de programação, é correto afirmar que:

a. Um teste de condição pode ser realizado através da instrução while.

b. A componente else do if é obrigatório.

c. if-else a condição é avaliada e, caso seja verdadeira, é executada a instrução associada ao else.

d. if-else permite a existência de instruções que não são executadas em um programa.

e. if-else não pode ser executado de forma encadeada.

(POSCOMP, 2019) Um procedimento recursivo é aquele que contém em sua descrição:

a. Uma prova de indução matemática.

b. Duas ou mais chamadas a procedimentos externos.

c. Uma ou mais chamadas a si mesmo.

d. Somente chamadas externas.

e. Uma ou mais chamadas a procedimentos internos.

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)
 se (n > 1)
   então retornar (n - 1) * 2 + xpto(n - 1) + 1;
   senão retornar 1;
 fim se;
fim função;

função principal
 ler(n);
 se (n > 0)
   então escrever(xpto(n));
   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. 12

b. 16

c. 20

d. 24

e. 25

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

R01: Faça subtrair_a vá_para R02;
R02: Faça subtrair_a vá_para R03;
R03: Faça subtrair_a vá_para R04;
R04: Faça subtrair_a vá_para R05;
R05: Faça subtrair_a vá_para R06;
R06: Faça subtrair_a vá_para R07;
R07: Faça subtrair_a vá_para R08;
R08: Faça subtrair_a vá_para R09;
R09: Se a_zero então vá_para R00 senão vá_para R10;
R10: Faça adicionar_b vá_para R06;

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 4_REG apresentado a seguir, qual das computações corresponde a execução do programa, caso a entrada fornecida pelo 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;

(R01, (4, 0, 0, 0))
(R02, (4, 0, 0, 0))
(R03, (3, 0, 0, 0))
(R04, (3, 1, 0, 0))
(R05, (3, 1, 0, 1))
(R02, (3, 1, 0, 1))
(R03, (2, 1, 0, 1))
(R04, (2, 2, 0, 1))
(R05, (2, 2, 0, 2))
(R02, (2, 2, 0, 2))
(R03, (1, 2, 0, 2))
(R04, (1, 3, 0, 2))
(R05, (1, 3, 0, 3))
(R02, (1, 3, 0, 3))
(R03, (0, 3, 0, 3))
(R04, (0, 4, 0, 3))
(R05, (0, 4, 0, 4))
(R06, (0, 4, 0, 4))
(R07, (0, 4, 0, 4))
(R08, (0, 3, 0, 4))
(R09, (0, 3, 0, 4))
(R10, (0, 2, 0, 4))
(R11, (0, 2, 0, 4))
(R12, (0, 1, 0, 4))
(R13, (0, 1, 0, 4))
(R06, (0, 0, 0, 4))
(R00, (0, 0, 0, 4))

(R01, (4, 0, 0, 0))
(R02, (4, 0, 0, 0))
(R03, (3, 0, 0, 0))
(R04, (3, 1, 0, 0))
(R05, (3, 1, 0, 1))
(R02, (3, 1, 0, 1))
(R03, (2, 1, 0, 1))
(R04, (2, 2, 0, 1))
(R05, (2, 2, 0, 2))
(R02, (2, 2, 0, 2))
(R03, (1, 2, 0, 2))
(R04, (1, 3, 0, 2))
(R05, (1, 3, 0, 3))
(R02, (1, 3, 0, 3))
(R03, (0, 3, 0, 3))
(R04, (0, 4, 0, 3))
(R05, (0, 4, 0, 4))
(R06, (0, 4, 0, 4))
(R07, (0, 4, 0, 4))
(R08, (0, 3, 0, 4))
(R09, (0, 3, 0, 4))
(R10, (0, 2, 0, 4))
(R11, (0, 2, 0, 4))
(R12, (0, 1, 0, 4))
(R13, (0, 1, 0, 4))
(R06, (0, 0, 0, 4))

(R01, (4, 0, 0, 0))
(R02, (3, 0, 0, 0))
(R03, (3, 1, 0, 0))
(R04, (3, 1, 0, 1))
(R05, (3, 1, 0, 1))
(R02, (2, 1, 0, 1))
(R03, (2, 2, 0, 1))
(R04, (2, 2, 0, 2))
(R05, (2, 2, 0, 2))
(R02, (1, 2, 0, 2))
(R03, (1, 3, 0, 2))
(R04, (1, 3, 0, 3))
(R05, (1, 3, 0, 3))
(R02, (0, 3, 0, 3))
(R03, (0, 4, 0, 3))
(R04, (0, 4, 0, 4))
(R05, (0, 4, 0, 4))
(R06, (0, 4, 0, 4))
(R07, (0, 3, 0, 4))
(R08, (0, 3, 0, 4))
(R09, (0, 2, 0, 4))
(R10, (0, 2, 0, 4))
(R11, (0, 1, 0, 4))
(R12, (0, 1, 0, 4))
(R13, (0, 0, 0, 4))
(R06, (0, 0, 0, 4))
(R00, (0, 0, 0, 4))

(R01, (4, 0, 0, 0))
(R02, (3, 0, 0, 0))
(R03, (3, 1, 0, 0))
(R04, (3, 1, 0, 1))
(R05, (3, 1, 0, 1))
(R02, (2, 1, 0, 1))
(R03, (2, 2, 0, 1))
(R04, (2, 2, 0, 2))
(R05, (2, 2, 0, 2))
(R02, (1, 2, 0, 2))
(R03, (1, 3, 0, 2))
(R04, (1, 3, 0, 3))
(R05, (1, 3, 0, 3))
(R02, (0, 3, 0, 3))
(R03, (0, 4, 0, 3))
(R04, (0, 4, 0, 4))
(R05, (0, 4, 0, 4))
(R06, (0, 4, 0, 4))
(R07, (0, 3, 0, 4))
(R08, (0, 3, 0, 4))
(R09, (0, 2, 0, 4))
(R10, (0, 2, 0, 4))
(R11, (0, 1, 0, 4))
(R12, (0, 1, 0, 4))
(R13, (0, 0, 0, 4))
(R06, (0, 0, 0, 4))

(R01, (4, 0, 0, 0))
(R02, (4, 0, 0, 0))
(R03, (3, 0, 0, 0))
(R04, (3, 1, 0, 0))
(R05, (3, 1, 0, 1))
(R02, (3, 1, 0, 1))
(R03, (2, 1, 0, 1))
(R04, (2, 2, 0, 1))
(R05, (2, 2, 0, 2))
(R02, (2, 2, 0, 2))
(R03, (1, 2, 0, 2))
(R04, (1, 3, 0, 2))
(R05, (1, 3, 0, 3))
(R02, (1, 3, 0, 3))
(R03, (0, 3, 0, 3))
(R04, (0, 4, 0, 3))
(R05, (0, 4, 0, 4))
(R06, (0, 4, 0, 4))
(R07, (0, 3, 0, 4))
(R08, (0, 3, 0, 4))
(R09, (0, 2, 0, 4))
(R10, (0, 2, 0, 4))
(R11, (0, 1, 0, 4))
(R12, (0, 1, 0, 4))
(R13, (0, 0, 0, 4))
(R06, (0, 0, 0, 4))
(R00, (0, 0, 0, 4))

(Diverio, 2000) Funções computadas permitem introduzir algumas importantes relações de equivalência de programas e máquinas, em especial, a relação de equivalência forte de programas, no qual um par de programas pertence à relação se as correspondentes funções computadas coincidem para qualquer máquina. As funções computadas por programas fortemente equivalentes têm a propriedade de que os mesmos testes e as mesmas operações são efetuados na mesma ordem, independentemente do significado dos mesmos. Desenvolva um programa monolítico que seja fortemente equivalente ao programa recursivo apresentado a seguir.

função R()
  B;
  se T
    então retornar R();
  fim se;
fim função;

função S()
  A;
  R();
  se U
    então retornar S();
  fim se;
fim função;

função principal()
  S();
fim função;

R1: Faça A vá_para R2;
R2: Faça B vá_para R3;
R3: Se T então vá_para R2 senão vá_para R4;
R4: Se U então vá_para R1 senão 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 = 1;
    enquanto (i <= n) faça
      j = 1;
      enquanto (j <= n) faça
        se (i == 1) então
          escrever(0);
        senão
          se (i == n) então
            escrever(0);
          senão
            se (j == 1) então
              escrever(0);
            senão
              se (j == n) então
                escrever(0);
              senão
                escrever(*);
              fim se;
            fim se;
          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 apresente a somatória dos termos da série de Fibonacci.

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

Por exemplo, caso o número de termos fornecido pelo usuário seja 7, o programa deverá apresentar como resposta o valor 20, ou seja, 0 + 1 + 1 + 2 + 3 + 5 + 8.

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

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

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