Ap02 Equivalência de Máquinas e Programas (2)

Prévia do material em texto

Ciência da ComputaçãoCiência da Computação
Teoria da Computação
Prof. Giovanni Ely Rocco (gerocco@ucs.br)
 
Equivalência de MáquinasEquivalência de Máquinas
As máquinas podem se simular mutuamente,
mesmo que a simulação use programas diferentes?
Sejam M e N duas máquinas arbitrárias,
N simula M, se, e somente se, 
para qualquer programa P para M
existe um programa Q para N,
tais que, para os mesmos conjuntos de
valores de entrada e saída (XM→ XN e YM→ YN)
as funções computadas coincidem, ou seja, <P,M> = <Q,N>;
NQ
YN
XN MP
YM
XM
… e N simula fortemente M se, e somente se,
N simula M e M simula N.
 
Equivalência de ProgramasEquivalência de Programas
As funções computadas coincidem
para uma máquina?
Sejam P e Q programas arbitrários
e M uma dada máquina
P ≡M Q se, e somente se, <P,M> = <Q,M>.
Relação de Equivalência de Programas
em uma Máquina
Sejam P e Q programas arbitrários
e M qualquer máquina
P ≡ Q se, e somente se, <P,M> = <Q,M>.
Relação de
Equivalência Forte
de Programas
 
Equivalência de ProgramasEquivalência de Programas
A equivalência forte de programas:
* permite identificar diferentes programas
 em uma mesma classe de equivalência;
 (cujas funções computadas coincidem para qualquer máquina);
* as funções computadas por estes programas possui
 as mesmas operações e testes efetuados na mesma ordem;
* fornece subsídios para analisar
 a complexidade estrutural de programas.
B
T
F
V
A
Partida
Parada
T
V
FT
B
T
F
V
A
Partida
Parada
T
V
FT
T
F
V
 
Equivalência de ProgramasEquivalência de Programas
Equivalência Forte de Programas
* Programa Iterativo → Monolítico
 Para qualquer programa iterativo Pi
 existe um programa monolítico Pm, tal que Pi ≡ Pm
* Programa Monolítico → Recursivo
 Para qualquer programa monolítico Pm
 existe um programa recursivo Pr, tal que Pm ≡ Pr
* Programa Iterativo → Recursivo
 Para qualquer programa iterativo Pi
 existe um programa recursivo Pr, tal que Pi ≡ Pr
 
Equivalência de ProgramasEquivalência de Programas
Equivalência Forte de Programas
* Programa Monolítico → Iterativo
 Dado um programa monolítico Pm qualquer
 não necessariamente existe um programa iterativo Pi, tal que Pm ≡ Pi
* Programa Recursivo → Monolítico
 Dado um programa recursivo Pr qualquer
 não necessariamente existe um programa monolítico Pm, tal que Pr ≡ Pm
Prova (contra-prova)?
Programa: Duplicar um valor,
em uma máquina de um registrador.
Monolítico? Iterativo? Recursivo?
Duplica
resultado
F
V
Decrementa
valor
Partida
ParadaZero?
B
T
F
V
A
Partida
Parada
T
V
FT
 
Equivalência de ProgramasEquivalência de Programas
Equivalência Forte de Programas
Programas Iterativos
Programas Monolíticos
Programas Recursivos
Assim, pode-se concluir que:
 para todo programa iterativo,
 existe uma monolítico equivalente fortemente;
e para todo programa monolítico
 existe um recursivo equivalente fortemente.
Mas a inversa não é verdadeira:
programas recursivos são
 mais gerais que os monolíticos;
programas monolíticos são
 mais gerais que os iterativos.
Obs: As três classes de formalismos possuem o mesmo poder computacional, pois
para efeitos de análise de poder computacional pode-se considerar
diferentes máquinas para os diferentes programas.
 
Equivalência de ProgramasEquivalência de Programas
Verificação de Equivalência Forte de Programas
* Máquina de Traços
 produz um histórico (denominado 'traço')
 da ocorrência das operações do programa.
 Dois programas são equivalentes fortemente se
 são equivalentes em qualquer máquina de traços.
* Programa Monolítico com Instruções Rotuladas Compostas
 constituem uma forma alternativa de definir programas monolíticos.
 Basicamente, uma instrução rotulada composta combina
 as duas formas básicas (operação e teste) em uma única forma.
A verificação de equivalência forte entre dois programas
é realizada pela classe mais simples de programas, os monolíticos,
pois não é conhecido um algoritmo genérico para verificação mais geral,
ou seja, para os programas recursivos não se sabe se o problema é solucionável.
 
Equivalência de ProgramasEquivalência de Programas
Verificação de Equivalência Forte de Programas
M
áq
u
in
a 
d
e 
T
ra
ço
s
M = (Op*, Op*, Op*, idOp*, idOp*, ΠF, ΠT)
Op*: Conjunto de Palavras e Operações onde Op={F,G,...}
 corresponde aos conjuntos de valores de memória, entrada e saída
idOp*: Função identidade em Op*
 corresponde às funções de entrada e de saída
ΠF: Conjunto de Interpretações de Operações tal que
 para cada identificador de operação F de Op, πF: Op*→ Op* é tal que,
 para qualquer w є Op* resulta na concatenação de F a direita: πF:(w) = wF
ΠT: Conjunto de Interpretações de Testes tal que
 para cada identificador de teste T: πT: Op*→{verdadeiro,falso} em ΠT
A máquina de traços não executa operações,
 o efeito de cada operação interpretada é simplesmente
 acrescentar o identificador à direita do valor atual de memória:
o valor de saída consiste em um histórico das operações executadas; e
para defini-la precisa-se apenas especificar as interpretações dos testes.
 
Equivalência de ProgramasEquivalência de Programas
Instruções Rotuladas Compostas
Formato:
r1: se T então faça F vá_para r2
 senão faça G vá_para r3
Em um Programa Monolítico,
o formato acima é abreviada por: r1:(F,r2),(G,r3)
T FV G
r1
F
r2 r3
Teste =
verdadeiro
Teste =
falso
r2 e r3
são rótulos sucessores de r1
r1 é rótulo antecessor
de r2 e r3
 
Equivalência de ProgramasEquivalência de Programas
Instruções Rotuladas Compostas
Fluxograma → Instruções Rotuladas Compostas
1. Rotula-se cada nó do fluxograma
 (partida, operação e parada);
2. o nó “partida” é o rótulo inicial;
3. segue-se o caminho do fluxograma
 (próxima operação executada);
4. a “parada” é identificada
 por palavra vazia (ε);
r1:(F,r2),(F,r2)
F
r1
r2
Operação
Teste
T FV G
r1
F
r2 r3
r1:(F,r2),(G,r3)
Parada
Parada
r
ε
r:(parada,ε),(parada,ε)
 
Equivalência de ProgramasEquivalência de Programas
Instruções Rotuladas Compostas
Fluxograma → Instruções Rotuladas Compostas
5. nos testes, para cada caminho (V ou F)
 representa-se o próximo nó (operação)
 (os testes são únicos por simplificação);
6. os ciclos devem ser
 representados (ω),
 observando-se os
 ciclos infinitos. 
Testes Encadeados
T
F
V
G
r1
F
r2
r3
T
FH
r4
V
r1:(F,r2),(G,r3)
Testes Encadeados 
em Ciclo Infinito
T
F
V
r1
F
r2
T
F
r1:(F,r2),(ciclo,ω)
 ω:(ciclo,ω),(ciclo,ω)
 
Verificação de Equivalência de ProgramasVerificação de Equivalência de Programas
Instruções Rotuladas Compostas
1:(G,2),(F,3)
2:(G,2),(F,3)
3:(F,4),(G,5)
4:(F,4),(G,5)
5:(F,6),(ciclo,ω)
6:(parada,ε),(G,7)
7:(G,7),(G,7)
22
T FV FG
33
T VG77
F
T
F
VF
66
T
F
Paradaεε
Partida11
T FV GF44 55
V
Instruções Rotuladas Compostas
Simplificada
1:(G,2),(F,3)
2:(G,2),(F,3)
3:(F,4),(G,5)
4:(F,4),(G,5)
5:(F,6),(ciclo,ω)
6:(parada,ε),(ciclo,(ciclo,ωω))
7:(G,7),(G,7)7:(G,7),(G,7)
ω:(ciclo,ω),(ciclo,ω)
Identificação
de Ciclos Infinitos:
A0 = { ε }
A1 = { 6, ε }
A2 = { 5, 6, ε }
A3 = { 3, 4, 5, 6, ε }
A4 = { 1, 2, 3, 4, 5, 6, ε }
A5 = { 1, 2, 3, 4, 5, 6, ε }
Exemplo
 
Verificação de Equivalência de ProgramasVerificação de Equivalência de Programas
22
T FV FG
33
T VG77
F
T
F
VF
66
T
F
Paradaεε
Partida11
T FV GF44 55
V
Exemplo
1313
99
T FV FG
1010
T VF
T FVF
1212
Parada εε
Partida88
T FV G
1111
F
IR Composta Simplificada (Q)
1:(G,2),(F,3)
2:(G,2),(F,3)
3:(F,4),(G,5)
4:(F,4),(G,5)
5:(F,6),(ciclo,ω)
6:(parada,ε),(ciclo,ω)
ω:(ciclo,ω),(ciclo,ω)
IR Composta Simplificada (R)
 8:(G,9),(F,10)
 9:(G,9),(F,10)
10:(F,10),(G,11)
11:(F,12),(ciclo,ω)
12:(parada,ε),(ciclo,ω)
 ω:(ciclo,ω),(ciclo,ω)
 
Verificação de Equivalência de ProgramasVerificação de Equivalência de Programas
Exemplo
r:(F1,r1),(F2,r2)
s:(G1,s1),(G2,s2)
São consistentes se,
e somente se,
F1 = G1 e F2 = G2
União DisjuntaIQ e IR
 1:(G,2),(F,3)
 2:(G,2),(F,3)
 3:(F,4),(G,5)
 4:(F,4),(G,5)
 5:(F,6),(ciclo,ω)
 6:(parada,ε),(ciclo,ω)
 8:(G,9),(F,10)
 9:(G,9),(F,10)
10:(F,10),(G,11)
11:(F,12),(ciclo,ω)
12:(parada,ε),(ciclo,ω)
 ω:(ciclo,ω),(ciclo,ω)
Para verificar se Q ≡ R
basta verificar se (I,1) ≡ (I,8):
B0 = { (1,8) }
B1 = { (2,9), (3,10) }
B2 = { (4,10), (5,11) }
B3 = { (6,12), (ω,ω) }
B4 = { (ε,ε) }
B5 = Ø
Logo (I,1) ≡ (I,8) e, portanto, Q ≡ R
São equivalentes fortemente se,
e somente se,
r = s = ε
ou r ≠ ε e s ≠ ε
e r e s são consistentes
Rótulos Consistentes e Rótulos Equivalentes Fortemente
 
ExercíciosExercícios
Considerando os seguintes programas...
Programa 1 Programa 2
enquanto T
 faça (F)
Programa 3
P4 é R onde
 R def se T então (F;R) senão √
T VF F
Partida
Parada
São equivalentes?
 
ExercíciosExercícios
Considerando os seguintes programas...
Programa 1 Programa 2
enquanto T
 faça (F)
Programa 3
P4 é R onde
 R def se T então (F;R) senão √
T VF F
Partida
Parada
São equivalentes?
Instruções Rotuladas Compostas
1:(F,2),(parada,ε)
2:(F,2),(parada,ε)
 
ExercíciosExercícios
Considerando o seguinte programa...
se T1
 então (X; enquanto T2
 faça (faça (V;W)
 até T3; Y))
 senão (√)
Programa monolítico?
Instruções Rotuladas Compostas?
T1 VF
V
Partida
Parada T2
W
F
V
VF T3
X
Y
1
2
ε
3
4
5
 
ExercíciosExercícios
Considerando o seguinte programa...
se T1
 então (X; enquanto T2
 faça (faça (V;W)
 até T3; Y))
 senão (√)
Programa monolítico?
Instruções Rotuladas Compostas?
1:(X,2),(parada,ε)
2:(V,3),(parada,ε)
3:(W,4),(W,4)
4:(Y,5),(V,3)
5:(V,3),(parada,ε)
T1 VF
V
Partida
Parada T2
W
F
V
VF T3
X
Y
1
2
ε
3
4
5
 
ExercíciosExercícios
T1 VF
V
Partida
Parada T2
W
F
V
V
F
T3
X
Y
T1 VF
V
Partida
Parada T2
W
F
V
V
F
T3
X
Y Demonstrar que esses
programas não são equivalentes.
 
ExercíciosExercícios
T1 VF
V
Partida
Parada T2
W
F
V
V
F
T3
X
Y
ε
1
2
3
4
5
Instruções rotuladas compostas: 
 1:(X,2),(parada,ε)
 2:(V,3),(parada,ε)
 3:(W,4),(W,4)
 4:(Y,5),(V,3)
 5:(V,3),(parada,ε)
 6:(X,7),(parada,ε)
 7:(V,8),(parada,ε)
 8:(W,9),(W,9)
 9:(Y,10),(V,8)
 10:(X,7),(X,7)
ε
6
7
8
9
10
Conclui-se que os programas não são equivalentes.
T1 VF
V
Partida
Parada T2
W
F
V
V
F
T3
X
Y
Rótulos Consistentes
 (1,6)√√
 (2,7)√√ (ε,ε)
 (3,8)√√ (ε,ε)
(4,9)√√ (4,9)√√ 
 (5,10)χχ (3,8)√√ B = { (5,10) }
 
ExemploExemplo
Zero FV
Partida
Parada
ZeroV F
Sub
Add
Sub
Zero FV
Partida
Parada
Sub
Add
Sub
Os programas são equivalentes?
 
ExemploExemplo
1
ε
2
3Zero
FV
Partida
Parada
ZeroV F
Sub
Add
Sub
4
Este programa retorna 
zero se ímpar e um se par.
5
ε
6
7Zero
FV
Partida
Parada
Sub
Add
Sub
8
Este programa não funciona para o mesmo 
propósito, pois apresenta problema de 
estruturação lógica (com estruturação 
iterativa não é possível nessa máquina).
Os programas são equivalentes?
Instruções rotuladas compostas: Rótulos Consistentes:
1:(Add,2),(Sub,3) 5:(Add,6),(Sub,7) (1,5)√√ 
2:(parada,ε),(parada,ε) 6:(parada,ε),(parada,ε) (2,6)√√ 
3:(parada,ε),(Sub,4) 7:(Sub,8),(Sub,8) (3,7)χχ 
4:(Add,2),(Sub,3) 8:(Add,6),(Sub,7)
Como (I,1) ≡≡ (I,5), os programas não são equivalentes!
	Slide 1
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50