Teoria da Computação - Exercícios

Prévia do material em texto

UNIVERSIDADE FEDERAL DE PELOTAS 
 Teoria da Computação 
Lista de Exercícios 1 
Profa Simone André da Costa 
 
 
1. Defina um programa monolítico na forma de instruções rotuladas com pelo menos 5 instruções. 
Converta este programa para fluxograma. 
 
2. Defina um programa monolítico na forma de fluxograma. Converta este programa para 
instruções rotuladas. 
 
3. Converta o programa monolítico abaixo na forma de instruções rotuldas. 
 
 
 
 
 
 
 
 
 
 
 
4. Os programas definidos abaixo definem programa monolítico (considere 1 como rótulo 
inicial)? Em caso afirmativo converta para fluxograma, senão justifique. 
a) 1: Se T então vá para 50 senão vá para 3 
2: Faça F vá para 1 
3: Faça G vá para 4 
4: Se T2 então vá para 2 senão vá para 10 
 
d) 1: Se T então faça F senão vá para 3 
 2: Faça F vá para 1 
 
b) 1: Faça F vá para 1 
 
e) 1: Se T então vá para 50 senão vá para 30 
c) 1: Faça F vá para 2 
2: Se T2 então vá para 1 senão vá para 3 
3: Faça G vá para 4 
4: Faça F vá para 3 
f) 1: Faça F;G vá para 2 
 2: Se T2 então vá para 1 senão vá para 3 
 
5. Defina um programa iterativo utilizando pelo menos dois mecanismos sequenciais diferentes e 
justifique que este programa está bem definido. 
 
6. Os programas definidos abaixo definem programas iterativos? Em caso afirmativo mostre que 
ele está bem definido, senão justifique. 
a) Enquanto T faça (F;G;(Se T então F senão G);Até T faça(F)) 
b) Até T faça (F;G;(Se T2 então G2)) 
c) (Se T2 então Até T1 faça (G; (Se T então F senão H)) senão I) 
d) F;G 
e) I 
 
7. Defina um programa recursivo utilizando pelo menos três identificadores de sub-rotina 
diferentes e justifique que este programa está bem definido. 
 
8. Os programas definidos abaixo definem programas recursivos? Em caso afirmativo mostre 
que ele está bem definido, senão justifique. 
a) (Se T então R1;R2 senão G;I), onde 
R1 def G;H;(Se T então R1 senão R2) 
R2 def G;(Se T2 então R2 senão I) 
b) R1;R2 onde 
R1 def Enquanto T faça (G;R1) 
R2 def I 
c) G;H 
partida 
parada 
T1 
T2 F 
G2 H V 
V 
F 
F