Teoria da computação aula_3

Prévia do material em texto

Teoria da Computação
Prof. Ms. Diego Daniel 
Duarte
Faculdades Anhanguera
Limeira - SP
Cronograma
Tópicos
 Programas
 Máquinas
 Computações
Programas
 Definição
– Conjunto estruturado de instruções que capacitam uma 
máquina a aplicar sucessivamente certas operações 
básicas e testes sobre os dados iniciais fornecidos com o 
objetivo de transformar esses dados numa forma desejável
 Tipos de Programas
– Monolítico
– Iterativo
– Recursivo
Programas
 Programas Monolíticos
– Estruturado somente com desvios condicionais e 
incondicionais
– Não emprega mecanismos auxiliares
– Lógica do programa contida em um único bloco 
(monólito)
Programas Monolíticos
 Fluxograma  Instruções Rotuladas
1. Faça F
2. Se T1 então vá para 1, 
senão vá para 3
3. Faça G
4. Se T2 então vá para 5, 
senão vá para 1
Início
F
T1
G
T2
Fim
V
V
f
f
Programa Monolítico
 Par P(I, r)
– I: conjunto finito de instruções rotuladas
– r: rótulo inicial, que distingue a instrução inicial 
em I
 Não existem duas instruções diferentes com 
o mesmo rótulo
 Um rótulo não associado a nenhuma 
instrução, é um rótulo final
Máquinas
 As máquinas interpretam os programas suprindo todos os 
recursos necessários para realizar a computação que eles 
representam
 Cada identificador de operação ou teste interpretado pela 
máquina deve ser associado a uma transformação na estrutura 
da memória e a uma função verdade respectivamente
 Nem todo identificador de operação ou teste é definido em 
uma máquina
 Para cada identificador de operação ou teste definido em uma 
máquina, existe somente uma função associada.
 Máquinas devem descrever o armazenamento ou recuperação 
das informações na estrutura da memória
Máquinas
 Uma máquina é uma Héptupla (V,X,Y,πx,πy,ΠF,ΠV), na 
qual:
– V: conjunto de valores de memória
– X: Conjunto de valores de entrada
– Y: Conjunto de valores de saída
� πx: Função de entrada, tal que πx: X  V
� πy: Função de saída, tal que πy: V  Y
� ΠF: Conjunto de interpretação de Operações. 
Para cada F, existe uma única πF: V  V
� ΠV: Conjunto de Interpretação de Testes. 
Para cada T, existe uma πT: V  {verdadeiro, falso}
Máquinas
 Exemplo: Máquina de Dois Registradores
– Seja uma máquina com dois registradores, a e b, 
que assumem valores m N (números naturais), 
com duas operações e um teste:
Subtrair 1 de a, se a > 0
Adicionar 1 em b
Teste se a é 0 (zero)
– Adicionalmente, os valores de entrada são 
armazenados em a (zerando b) e a saída retorna 
o valor de b
Máquinas
 Implementação
– V = N²  conjunto de valores da memória
– X = N  conjunto de valores de entrada
– Y = N  conjunto de valores de saída
� πx: X  V, ou seja, πx: N  N²
πx(n) = (n, 0)
� πY: V  Y, ou seja πY: N²  N
πY(n, m) = m
Máquinas
 Implementação
� ΠF contém Fn: V  V, ou seja, Fn: N²  N²
 Subtrair 1 de a, se a > 0
– F1(n, m) = (n-1, m), se n > 0
– F1(n, m) = (n, m), se n = 0
 Adicionar 1 em b
– F2(n, m) = (n, m+1)
� ΠT contém Tn: V  { verdadeiro, falso }, ou seja Tn: N²  
{ verdadeiro, falso }
 Teste se a é zero
– T1(n, m) = verdadeiro, se n = 0
– T1(n, m) = falso, se n ≠ 0
Máquinas
 Programas para máquinas
– Diz-se que P é um programa para uma máquina 
M se cada operação e teste em P corresponde a 
uma interpretação em M
Exercício
 Faça um programa 
para a máquina de dois 
registradores 
apresentados no 
exemplo anterior para 
calcular o dobro de um 
número informado
Solução
1. Armazene a entrada
2. Subtraia a
3. Adicione b
4. Adicione b
5. Se a igual a 0, vá para 
6, senão vá para 2
Computação
 Histórico das instruções executadas e 
correspondentes estados da memória
 Representado pro uma cadeia de pares (sk, vk), no 
qual:
– Sk representam os rótulos das instruções
– Vk representam os dados na memória
– Cada par reflete um estado da máquina para o programa
– A cadeia reflete a sequencia de estados possíveis a partir 
do estado inicial
Computação
 Seja F um identificador de operação, T um 
identificador de teste e r´ e r´´ rótulos de L, uma 
cadeia se computação é dada por:
– Operações:
 Se sk é o rótulo de uma operação da forma Sk: faça F vá para 
r’ então (sk+1, vk+1) = (r’, πF(vk)) é o par subsequente de (sk, vk) na 
cadeia.
– Testes
 Se sk é o rótulo de um teste da forma Sk: Se T então vá para 
r’, senão vá para r’’, então (sk+1, vk+1) é o par subsequente de 
(sk, vk) na cadeia, sendo que vk+1 = vk e:
– Sk+1 = r’, se πT(vk) = verdadeiro
– Sk+1 = r’’, se πT(vk) = falso
Exercício
 Dê a cadeia de 
computação para o 
programa do exercício 
anterior considerando a 
entrada 3
Solução
(1, (ε, ε)) Armazene a entrada
(2, (3, 0)) Subtraia a
(3, (2, 0)) Adicione b
(4, (2, 1)) Adicione b
(5, (2, 2)) Se a é zero
(2, (2, 2)) Subtraia a
(3, (1, 2)) Adicione b
(4, (1, 3)) Adicione b
(5, (1, 4)) Se a é zero
(2, (1, 4)) Subtraia a
(3, (0, 4)) Adicione b
(4, (0, 5)) Adicione b
(5, (0, 6)) Se a é zero
(6, (0, 6))
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19