Introdução à Teoria da Computação

Wilson Rubens Galindo

Motivação

O que é um algoritmo? Definiremos formalmenteO que é computabilidade?Qualquer problema pode ser resolvido por um computador?Resolução de ProblemasDefinição de uma Linguagem de ProgramaçãoO que é tempo computacional?Será que o computador executa qualquer operação em tempo hábil?

Conteúdo

Revisão de provas (matemática discreta)Autômatos finitos determinísticos (AFD)Autômatos finitos não-determinísticos (AFND)Expressões/ linguagens regularesPropriedades das linguagens regularesGramática/linguagem livre de contextoAutômatos a Pilha

Conteúdo

Propriedades de linguagens livres de contextoMáquinas de TuringIntrodução à IndecibilidadeProblemas IntratáveisOutras classes de problemas

Bibliografia

Introdução à Teoria de Autômatos, Linguagens e Computação. John E. Hopcroft, Jeffrey D. Ulman e RajeevMotwani. Trad. da segunda edição, Editora Campus. (Livro Texto)

JFLAP (Software de ajuda)

Acióly, Benedito M.; Bedregal, BenjamínR. C.; Lyra, Aarão. Introdução à Teoria das Linguagens Formais, dos Autômatos e da Computabilidade. Edições UnP, 2002.

Bibliografia

LEWIS, H. R.; PAPADIMITRIOU, C. H. Elementos de Teoria da Computação 2a. Edição. Bookman. 2000. 361p.

Menezes, P.F.B. LINGUAGENS FORMAIS E AUTÔMATOS. Série Livros Didáticos. Instituto de informática da UFRGS. ( 3 Edição). ISBN 85-241-0554-2

Bibliografia

MANNA, Zohar. Mathematical Theory of Computation. New York: McGraw-Hill, 1974.

SERNADAS, C. Introdução à Teoria da Computação. Lisboa: Editorial Presença, 1993.

CD de Teoria da Computação

Organização das aulas

50% Teóricas

50% Práticas/ Exercícios

Exercícios do livro texto* -> Com respostas (cuidado)

! -> mais complexas

!!-> Precisa de conhecimento extra

Avaliações

1ª VA – 17/07/2007

2ª VA – 20/07/2007

3ª VA – 23/07/2007

Final – 24/07/2007

Informações Importantes

Site da disciplinawww.wilsongalindo.rg3.net

E-mailgalindo2105@gmail.com

Plano de aula (datas)No site a partir de 04/07/07

Aula de hoje

Instalação do JFLAP