View
14
Download
0
Category
Preview:
Citation preview
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
Recommended