Teoria da Computação

Prof.: Ricardo Gonçalves de Aguiar

Material de Apoio

Teoria da Computação
Prof.: Ricardo Gonçalves de Aguiar

Objetivos

Apresentar os conceitos teóricos sobre os elementos básicos da computação. Apresentar os limites da Computação: conceito de computabilidade e decidibilidade. Bibliografia
BÁSICA:
•
•
•

DIVERIO, T. A.; MENEZES, P. B.. Teoria da Computação: Máquinas
Universais e Computabilidade. Porto Alegre: Sagra Luzzato, 2000.
MENEZES, P. B.: Linguagens Formais e Autômatos. Porto Alegre: SagraLuzzato, 2001.
LINZ, P.: Na Introduction to Formal Languages and Automata, Boston: Jones and Bartlett Publishers, 2006

COMPLEMENTAR:
•
•

SIPSER,M.:
Introduction to the Theory of Computation, Second Edition,
Course Technology; 2005
GREENLAW,R.; HOOVER,H.J.: Fundamentals of the Theory of Computation,
Morgan Kaufmann; 1998

Forma de Avaliação

São três notas: Da avaliação 1 (AV1) a Avaliação 3 (AV3). A avaliação 2 é a avaliação integrada.
A média final é obtida através da média das duas maiores notas.
Para que o aluno seja aprovado, a média deve ser maior ou igual a 6,0

Notas Históricas
Muito antes da invenção do computador (máquina física: hardware), matemáticos procuravam construir um método simples capaz de resolver qualquer problema. Alguns métodos foram desenvolvidos e funcionaram, mas dependendo do problema, o método não era capaz de resolver o problema. A partir daí, os matemáticos passaram a tentar criar métodos que superassem a capacidade do método anterior e aumentassem a sua capacidade de resolução.

~1~

Prof.: Ricardo Gonçalves de Aguiar

Material de Apoio

Até que um “fulaninho” chamado Alan Turing desenvolveu em 1936 um método de resolução de problemas que superou todos os outros métodos existentes, recebendo o nome de Máquina de
Turing. Depois da teoria de Turing foram criados inúmeros outros métodos, mas na melhor das hipóteses, o método apenas se equivalia ao de Turing, não conseguia superar