P1 - 2017/1 - Turma B - Teoria da Computação -UFRGS

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Teoria da Computação – INF05501 – Prova 1 – Turma B
26 de Abril de 2017
Nome: RESOLUÇÃO Cartão UFRGS:
Questões:
1. [3pt]Considere os programas P1 e P2 para a máquina Norma2.
P1 = P2 =
a) Considere o valor de entrada 2. Apresente e compare a computação de P1 e a com-
putação de P2 para essa mesma entrada, indicando qual delas possui o menor número
de passos. Rótulos de instruções podem ser escritos diretamente ao lado dos nodos do
fluxograma (ao invés de traduzir todo o fluxograma para instruções rotuladas).
Conversão do diagrama de P1 para instru-
ções rotuladas:
1: if X=0 then goto 2 else goto 4
2: do Y:=Y+1 goto 3
3: do Y:=Y+1 goto 0
4: do X:=X-1 goto 5
5: do X:=X-1 goto 6
6: do Y:=Y+1 goto 1
Computação de P1 para entrada 2:
Rótulo X Y
1 2 0
4 2 0
5 1 0
6 0 0
1 0 1
2 0 1
3 0 2
0 0 3
Conversão do diagrama de P2 para instru-
ções rotuladas:
1: do Y:=Y+1 goto 2
2: if X=0 then goto 3 else goto 4
3: do Y:=Y+1 goto 0
4: do X:=X-1 goto 5
5: do X:=X-1 goto 6
6: do Y:=Y+1 goto 2
Computação de P2 para entrada 2:
Rótulo X Y
1 2 0
2 2 1
4 2 1
5 1 1
6 0 1
2 0 2
3 0 2
0 0 3
Ambas computações 〈P1,Norma2〉(2) e 〈P2,Norma2〉(2) possuem o mesmo tamanho
(8 passos).
1
b) O programa P1 é fortemente equivalente a P2? Justifique.
Não. Serem P1 e P2 fortemente equivalentes significa que ambos possuem a mesma
função computada em todas as máquinas possíveis.
Considere um máquina Norma20 similar à máquina Norma2, porém que interprete
o rótulo de instrução Y := Y + 1 como a operação que incrementa Y mas tam-
bém atribui zero ao registrador X. Nesse caso, teríamos 〈P1,Norma20〉(2) = 4 e
〈P2,Norma20〉(2) = 2
c) O programa P1 é Norma2-equivalente a P2? Justifique.
Sim. A função computada de ambos os programas na máquina Norma2 é a mesma.
Em outras palavras, 〈P1,Norma2〉 = 〈P2,Norma2〉 = (x 7→ dx/2e+ 2)
2. [1pt]Considere as seguintes afirmações:
I Em qualquer máquina podemos encontrar um programa recursivo fortemente equiva-
lente a um programa iterativo qualquer.
Verdadeiro. Para programa iterativo I há um programa monolítico M fortemente equi-
valente. Para M, há um programa recursivo R fortemente equivalente. R é fortemente
equivalente a I por transitividade.
II Se duas máquinas M1 e M2 possuem os mesmos conjuntos de entrada e de saída e M1
simula fortemente M2, então certamente M2 simula fortemente M1.
Falso. Norma2 simula fortemente um_reg, porém um_reg não simula fortemente
Norma2.
III A noção de equivalência entre máquinas é baseada na noção de simulação entre má-
quinas. Uma máquina universal é aquela que simula qualquer outra máquina.
Verdadeiro.
Estão corretas somente as afirmações
A. I e II
B. I, II e III
C. II e III
D. I e III
E. todas as afirmações estão erradas
2
3. [2pt]Considere o seguinte programa monolítico P = (I, 1) para a máquina dois_reg, onde I é:
1 : do subtrai_a goto 2
2 : if a_zero then goto 0 else goto 3
3 : do subtrai_a goto 4
4 : do adiciona_b goto 2
a) Considere a enumeração de operações (adiciona_b = 1, subtrai_a = 2) e a enume-
ração de testes (a_zero = 1). Descreva (na forma de expressão aritmética) o número
natural que codifica o programa P .
i1 = (0, 2, 2, 2)
i2 = (1, 1, 0, 3)
i3 = (0, 2, 4, 4)
i4 = (0, 1, 2, 2)
î1 = 20 · 32 · 52 · 72
î2 = 21 · 31 · 50 · 73
î3 = 20 · 32 · 54 · 74
î4 = 20 · 31 · 52 · 72
P̂ = 2î1 · 3î2 · 5î3 · 7î4
b) Descreva a função computada 〈P,dois_reg〉.
〈P,um_reg〉(x) =
{
0 se x = 0
x− 1 se x > 0
4. [2pt]Apresente um programa para a máquina Norma que implemente a rotina
A := maior(B,C)
isto é, faça o registrador A receber o maior valor dentre os valores armazenados nos re-
gistradores B e C. A rotina deve preservar os valores dos registradores B e C, e os
registradores auxiliares que forem utilizados devem conter o valor 0 ao final da execução.
Todas as subrotinas utilizadas devem ser declaradas.
Uma das respostas possíveis:
3
5. [2pt]Considere a seguinte descrição para a máquinaNorma321. Assim como Norma, Norma321
é uma máquina constituída por um número arbitrário de registradores que armazenam
números naturais, na qual a entrada é feita pelo registrador X e a saída, pelo registrador
Y . Contudo, Norma321 disponibiliza diferentes operações e testes, conforme descrito
abaixo:
Reg = {X,Y,A,B,C, . . . }
Norma321 = ((Reg → N),N,N, ent, sai,ΠF ,ΠT )
onde
• ent(x) = {X 7→ x, Y 7→ 0, A 7→ 0, B 7→ 0, . . .}
• sai({X 7→ x, Y 7→ y,A 7→ a,B 7→ b, . . . }) = y
• dom(ΠF ) = {mais3R,menos2R}R∈Reg onde
– ΠF (mais3R) soma (em naturais) o valor 3 ao número armazenado no registrador
R, sem alterar os valores armazenados nos demais registradores.
– ΠF (menos2R) subtrai (em naturais, saturando em 0) o valor 2 do número arma-
zenado no registrador R, sem alterar os valores armazenados nos demais registra-
dores.
• dom(ΠT ) = {igual1R}R∈Reg onde igual1R retorna true se o valor armazenado em R
for igual a 1, e false caso contrário.
A máquina Norma321 simula a máquina Norma? Justifique sua resposta, descrevendo
detalhes da simulação (caso simule), ou apresentando um contraexemplo (caso não simule).
A máquina Norma321 simula a Máquina Norma. Para cada programa P em Norma, é
possível construir um programa equivalente Q em Norma321, trocando as operações e testes
de P pelas seguintes subrotinas em Norma321:
menos2(R)
Partida
Parada
mais3(R)
R:=R+1
4