Logo Passei Direto
Buscar

Teoria da Computação: Exercícios

Ferramentas de estudo

Questões resolvidas

4. A respeito de equivalência forte, determine verdadeiro ou falso e justifique:

a. ( ) Se os programas P e Q são fortemente equivalentes, então eles possuem as mesmas instruções.
b. ( ) Dois programas que são fortemente equivalentes devem computar a mesma função em todas as máquinas.
c. ( ) Dois programas P e Q, fortemente equivalentes, podem computar uma mesma função f em uma máquina M1 e uma mesma função g, diferente de f, em uma máquina M2.
d. ( ) Para todo programa iterativo, existe um programa recursivo fortemente equivalente.

5. Determine verdadeiro ou falso e justifique:

a. ( ) Para qualquer programa monolítico P, existe um programa iterativo Q que computa a mesma função.

b. ( ) Se dois programas são fortemente equivalentes, então a sequência de operações e testes por eles executadas é a mesma.

c. ( ) A análise da equivalência forte permite identificar programas com estruturas diferentes mas com computações isomórficas.

d. ( ) Para todo programa monolítico P, existe um programa iterativo Q tal que para qualquer máquina M, a função computada por P em M é a mesma função computada por Q em M.

Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Questões resolvidas

4. A respeito de equivalência forte, determine verdadeiro ou falso e justifique:

a. ( ) Se os programas P e Q são fortemente equivalentes, então eles possuem as mesmas instruções.
b. ( ) Dois programas que são fortemente equivalentes devem computar a mesma função em todas as máquinas.
c. ( ) Dois programas P e Q, fortemente equivalentes, podem computar uma mesma função f em uma máquina M1 e uma mesma função g, diferente de f, em uma máquina M2.
d. ( ) Para todo programa iterativo, existe um programa recursivo fortemente equivalente.

5. Determine verdadeiro ou falso e justifique:

a. ( ) Para qualquer programa monolítico P, existe um programa iterativo Q que computa a mesma função.

b. ( ) Se dois programas são fortemente equivalentes, então a sequência de operações e testes por eles executadas é a mesma.

c. ( ) A análise da equivalência forte permite identificar programas com estruturas diferentes mas com computações isomórficas.

d. ( ) Para todo programa monolítico P, existe um programa iterativo Q tal que para qualquer máquina M, a função computada por P em M é a mesma função computada por Q em M.

Prévia do material em texto

UNIVERSIDADE FEDERAL DE PELOTAS 
 Teoria da Computação 
Lista de Exercícios 4 
Profa Simone André da Costa 
 
 
1. Converta os seguintes programas iterativos em programas monolíticos fortemente equivalentes. 
Programa Iterativo P1 
(Se T1 então F senão enquanto T2 faça (G; F; Até T3 faça (F))) 
 
Programa Iterativo P2 
Até T1 faça (F; G); Enquanto T2 faça (F; (Se T3 então I senão G)) 
 
Programa Iterativo P3 
 F; G; (Se T então F; G senão Até T faça (G; Enquanto T faça (F))) 
 
Programa Iterativo P4 
 Enquanto T faça (F); (Se T então Enquanto T faça (G) senão I); H 
 
2. Converta os programas monolíticos obtidos na questão 1 em programas recursivos fortemente 
equivalentes. 
 
3. O que significa dizer que dois programas, P e Q, são fortemente equivalentes? 
 
4. A respeito de equivalência forte, determine verdadeiro ou falso e justifique: 
a. ( ) Se os programas P e Q são fortemente equivalentes, então eles possuem as mesmas 
instruções. 
b. ( ) Dois programas que são fortemente equivalentes devem computar a mesma função em 
todas as máquinas. 
c. ( ) Dois programas P e Q, fortemente equivalentes, podem computar uma mesma função 
f em uma máquina M1 e uma mesma função g, diferente de f, em uma máquina M2. 
d. ( ) Para todo programa iterativo, existe um programa recursivo fortemente equivalente. 
 
 
5. Determine verdadeiro ou falso e justifique: 
a. ( ) Para qualquer programa monolítico P, existe um programa iterativo Q que computa a 
mesma função. 
b. ( ) Se dois programas são fortemente equivalentes, então a sequência de operações e testes 
por eles executadas é a mesma. 
c. ( ) A análise da equivalência forte permite identificar programas com estruturas diferentes 
mas com computações isomórficas. 
d. ( ) Para todo programa monolítico P, existe um programa iterativo Q tal que para qualquer 
máquina M, a função computada por P em M é a mesma função computada por Q em M. 
 
6. Descreva o procedimento para provar que nem todo programa recursivo pode ser traduzido para 
um monolítico fortemente equivalente (não precisa fazer a prova, mas descrever o que é 
necessário para concluí-la).

Mais conteúdos dessa disciplina