Teoria da Computaçao

TEORIA DA COMPUTAÇÃO
Prova 1 - Prof. Marcus Ramos - 29/04/2011
1ª questão - Como são estruturados:
a) Programas monolíticos?
Identificadores de operações e testes (incluindo a operação vazia), execução seqüencial, desvio condicional e desvio incondicional.
b) Programas iterativos?
Identificadores de operações e testes (incluindo a operação vazia), execução seqüencial, execução condicional estruturada e execução iterativa.
c) Programas recursivos?
Identificadores de operações e testes (incluindo a operação vazia), execução condicional estruturada, definição e chamada de funções.
2ª questão
a) Quais são os requisitos que devem ser satisfeitos por um modelo matemático para ele ser denominado "máquina"?
Deve possuir memória para armazenamento de valores, capacidade de recepção e envio de dados para o meio externo, e atribuir significado para os identificados de operação e de teste usados nos programas através de funções apropriadas.
b) Conceitue "programa para uma máquina".
Quando todos os identificadores de operação e de teste usados no programa estiverem definidos na máquina.
3ª questão - Explique de que maneira os conceitos de computação e função computada são usados para definir (i) equivalência forte de programas, (ii) equivalências de programas numa máquina e (iii) equivalência de máquinas.
Dois programas são ditos fortemente equivalentes se eles possuem a mesma função computada em qualquer máquina. Dois programas são ditos equivalentes numa máquina se eles possuem a mesma função computada nessa máquina. Duas máquinas são equivalentes se, para todo programa de uma máquina, existir um programa da outra máquina que possui a mesma função computada. Uma função computada é um mapeamento entre o conjunto de valores da entrada e o conjunto de valores de saída, realizado através de uma seqüência finita de computações.
4ª questão
a) DefinaMáquina Universal.
Máquina capaz de executar, direta ou indiretamente (através de um programa) qualquer