Turmas - 2º Semestre de 2018
Turmas
2º Semestre de 2018

Relacione os itens que se correspondem:

1. Programa
2. Máquina
3. Computação
4. Função computada
5. Programas equivalentes em uma máquina
6. Equivalência forte de programas
7. Máquinas equivalentes

(  ) Função parcial que representa o mapeamento de valores do conjunto de entrada no conjunto de valores de saída realizado por um certo programa.

(  ) Interpretador para as operações e testes referenciados num programa.

(  ) Programas que possuem a mesma função computada em qualquer máquina.

(  ) Conjunto de instruções que determinam a ordem em que operações e testes são executados.

(  ) Sequência de estados que representam a execução de um programa numa certa máquina.

Assinale a alternativa que apresenta a sequência correta:

a. 5, 7, 6, 3, 4.

b. 4, 2, 6, 1, 3.

c. 4, 2, 5, 1, 3.

d. 6, 7, 5, 1, 3.

e. 6, 7, 5, 3, 4.

Analise as assertivas a seguir:

1. A importância prática de se avaliar a equivalência forte de programas é que a mesma permite analisar programas do ponto de vista da sua complexidade estrutural, ou outros critérios considerados relevantes (legibilidade, manutenibilidade, entre outros), uma vez que do ponto de vista funcional eles são equivalentes.
2. Os requisitos que devem ser satisfeitos por um modelo matemático para ele ser denominado “máquina” são: a) possuir memória para armazenamento de valores, b) capacidade de recepção e envio de dados para o meio externo, e c) atribuir significado para os identificados de operação e de teste usados nos programas através de funções apropriadas.
3. Programas iterativos são estruturados por meio de identificadores de operações e testes, execução sequencial, desvio condicional e desvio incondicional.

A análise permite concluir que:

a. Apenas a afirmativa I está correta.

b. Apenas a afirmativa II está correta.

c. Apenas a afirmativa III está correta.

d. Apenas as afirmativas I e II estão corretas.

e. Apenas as afirmativas II e III estão corretas.

Considere o programa recursivo apresentado a seguir:

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

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

a. 14.

b. 30.

c. 55.

d. 91.

e. 140.

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 2 unidades?

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

a. 1 unidade.

b. 2 unidades.

c. 3 unidades.

d. 4 unidades.

e. 5 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 calcule o valor da série infinita S = 1 + 1/2 + 1/4 + 1/6 + 1/8 + 1/10 + .... 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 5, o programa deverá apresentar como resposta o valor 2.04, ou seja, 1 + 1/2 + 1/4 + 1/6 + 1/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.

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, que calcule o valor da série infinita H = 1¹/1! - 2²/2! + 3³/3! - 4⁴/4! + .... 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 5, o programa deverá apresentar como resposta o valor 18.88, ou seja, 1¹/1! - 2²/2! + 3³/3! - 4⁴/4! + 5⁵/5!. Caso o usuário forneça um valor inválido para o número de termos, o programa deverá apresentar uma mensagem de erro.

programa
  ler(termos);
  se (termos > 0) então
    sinal = 1;
    H = 0;
    termo = 1;
    fatorial = 1;
    enquanto (termo <= termos) faça
      potencia = 1;
      aux = termo;
      enquanto (aux > 0) faça
        potencia = potencia * termo;
        aux = aux - 1;
      fim enquanto;
      H = H + potencia / fatorial * sinal;
      sinal = sinal * (-1);
      termo = termo + 1;
      fatorial = fatorial * termo;
    fim enquanto;
    escrever(H);
  senão
    escrever(erro);
  fim se;
fim programa.

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 apresente a série de Fibonacci. A série de Fibonacci é formada pela sequência 1, 1, 2, 3, 5, 8, 13, 21, 34, .... A série de Fibonacci é de grande importância matemática, e a lei básica é que a partir do terceiro termo, todos os termos são a soma dos dois últimos. O número de termos a serem impressos será fornecido pelo usuário, devendo ser um valor inteiro e positivo. Por exemplo, caso o número de termos a serem impressos fornecido pelo usuário seja 7, o programa deverá apresentar como resposta a sequência de valores 1, 1, 2, 3, 5, 8, 13. Caso o usuário forneça um valor inválido para o número de termos, o programa deverá apresentar uma mensagem de erro.

y₁ = 1
y₂ = y₁ + 2 = 3
y₃ = y₂ + 2 = 5
y₄ = y₃ + 2 = 7
y₅ = y₄ + 2 = 9

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(termos, primeiro, segundo)
  se (termos > 1) então
    escrever(segundo);
    segundo = segundo + primeiro;
    primeiro = segundo - primeiro;
    fibonacci(termos - 1, primeiro, segundo);
  senão
    escrever(segundo);
  fim se;
fim função;

função principal
  ler(termos);
  se (termos > 0)
    então fibonacci(termos, 0, 1);
    senão escrever(erro);
  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 implemente a função B = (A / 3) + (A * 2).

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