P1 - 2017/1 - Turma A - 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 A
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 computaçã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 Y:=Y+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 1 1
1 1 2
4 1 2
5 0 2
6 0 3
1 0 4
2 0 4
3 0 5
0 0 6
Conversão do diagrama de P2 para instruções
rotuladas:
1: do X:=X+1 goto 2
2: if X=0 then goto 0 else goto 3
3: do X:=X-1 goto 4
4: do Y:=Y+1 goto 5
5: do Y:=Y+1 goto 2
Computação de P2 para entrada 2:
Rótulo X Y
1 2 0
2 3 0
3 3 0
4 2 0
5 2 1
2 2 2
3 2 2
4 1 2
5 1 3
2 1 4
3 1 4
4 0 4
5 0 5
2 0 6
0 0 6
A computação de P1 possui 12 passos, enquanto a computação de P2 consiste de 15 passos.
Portanto, P1 possui a menor computação.
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 X := X + 1 como a operação que atribui zero aos registradores X e Y . Nesse caso
teríamos 〈P1,Norma20〉(2) = 6 e 〈P2,Norma20〉(2) = 0
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→ 2x + 2)
2. [1pt]Considere as seguintes afirmações:
I Podemos sempre encontrar um programa iterativo I fortemente equivalente a um programa
recursivo arbitrário R.
FALSO. O contrário é verdade: sempre podemos obter um programa recursivo fortemente
equivalente a um dado programa iterativo.
II Se duas máquinas M1 e M2 não possuem os mesmos conjuntos de entrada e saída, é impossível
que M1 simule M2 ou que M2 simule M1.
FALSO. É impossível que M1 simule fortemente M2 e vice-versa. Porém, é possível a simu-
lação entre elas, pois esta aceita a utilização de funções de codificação e decodificação para os
conjuntos de entrada e saída.
III Não é possível implementar funções como f(x, y) = x∗y em Norma2 (máquina Norma somente
com registradores X e Y ) dada a ausência de registradores auxiliares para implementar a
subrotina de multiplicação.
FALSO. Norma2 simula Norma, utilizando arranjos codificados como números naturais para
representar um número arbitrário de registradores de Norma. Através de codificações apro-
priadas de entrada e saída, é possível implementar funções com mais de um argumento, como
multiplicação.
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 um_reg, onde I é:
1 : do subtrai goto 2
2 : if zero then goto 0 else goto 3
3 : do subtrai goto 4
4 : do adiciona goto 2
a) Considere a enumeração de operações (adiciona = 1, subtrai = 2) e a enumeração de testes
(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,um_reg〉.
〈P,um_reg〉(x) =
{
0 se x ≤ 1
indefinido se x > 1
4. [2pt]Apresente um programa para a máquina Norma que implemente a rotina
A := menor(B,C)
isto é, faça o registrador A receber o menor valor dentre os valores armazenados nos registradores 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áquina Zuleica. Assim como Norma, Zuleica é uma máquina
contendo um número arbitrário de registradores na qual a entrada é feita pelo registrador X e a saída,
pelo registrador Y . Contudo, os registradores de Zuleica armazenam números inteiros, além de
disponibilizar diferentes operações e testes, conforme descrito abaixo:
Reg = {X,Y,A,B,C, . . . }
Zuleica = ((Reg → Z),Z,Z, 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 inteiros) o valor 3 ao número armazenado no registrador R ∈ Reg,
sem alterar os valores armazenados nos demais registradores.
– ΠF (menos2R) subtrai (em inteiros) o valor 2 do número armazenado no registrador R ∈
Reg, sem alterar os valores armazenados nos demais registradores.
• dom(ΠT ) = {negR}R∈Reg onde negR retorna true se o valor armazenado em R for menor que
0, e false caso contrário.
A máquina Zuleica 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 Zuleica simula a Máquina Norma. Para cada programa PN em Norma, é possível construir
um programa equivalente PZ em Zuleica, trocando as operações e testes de PN pelas seguintes
subrotinas em Zuleica:
menos2(R)
Partida
Parada
mais3(R)
R:=R+1
menos2(R)
Partida
Parada
mais3(R)
R:=R-1
menos2(R)
neg(R)
menos2(R)
mais3(R)V
F
menos2(R)
Partida
VERDADEIRO
mais3(R)
R=0?
menos2(R)
neg(R) menos2(R)mais3(R)V
F
FALSOmenos2(R)mais3(R)
4