Turmas - 1º Semestre de 2026
Turmas
1º Semestre de 2026

1. Ybadoo
2. Turmas
3. 1º Semestre de 2026
4. Teoria da Computação
5. Primeira Avaliação
6. Questão 03

Questão 03

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 por meio de uma sequência finita de computações.
4. A classe dos programas iterativos está contida na classe dos programas recursivos, que, por sua vez, está contida na classe dos programas monolíticos.

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.

Solução da Questão 03

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

A Relação de Equivalência Forte de Programas permite identificar diferentes programas em uma mesma classe de equivalência, ou seja, distinguir diferentes programas cujas funções computadas coincidem, para qualquer máquina, fornecendo subsídios para analisar propriedades de programas como complexidade estrutural, por exemplo.

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

Relativamente à Relação de Equivalência Forte de Programas, programas recursivos são mais gerais que os monolíticos, os quais, por sua vez, são mais gerais que os iterativos.

III Uma função computada é um mapeamento entre o conjunto de valores de entrada e o conjunto de valores de saída, realizado por meio de uma sequência finita de computações.

Esta é a definição formal e amplamente aceita de uma função computável: um mapeamento bem definido entre um domínio de entrada e um domínio de saída, efetivado por um procedimento algorítmico composto por uma sequência finita e determinística de operações.

IV A classe dos programas iterativos está contida na classe dos programas recursivos, que, por sua vez, está contida na classe dos programas monolíticos.

A hierarquia correta, induzida pela Relação de Equivalência Forte de Programas, é que a classe dos programas iterativos está contida na classe dos programas monolíticos, que, por sua vez, está contida na classe dos programas recursivos.

Conforme exposto, a resposta correta é:

B apenas as assertivas I e III.