IF689 - Informática Teórica

Informações gerais

Professor: Fred Freitas
E-mail: fred@cin.ufpe.br

Aluno de Doutorado: Diogo Espinhara E-mail: deo@cin.ufpe.br

Monitor: Jailson Gomes (jjgsj@cin.ufpe.br)
Google Classroom da disciplina

Avaliações

·         Mini prova a cada capítulo estudado (20% da nota total)

·         Prova a cada dois capítulos estudados (80% da nota total)

Slides das aulas

·         Capítulo 1

1.    Apresentação

2.    Autômatos Finitos

3.    Operações Regulares

4.    Autômatos Finitos Não-Determinísticos

5.    Equivalência entre AFDs e AFNs

6.    Fecho para Linguagens Regulares

7.    Expressões Regulares

8.    Expressões Regulares e AFNG

9.    Lema do Bombeamento

·         Capítulo 2

1.    Hierarquia de Chomsky

2.    Gramáticas Livres de Contexto

3.    Ambiguidade e Forma Normal de Chomsky

4.    Autômatos com Pilha

5.    Equivalência entre APs e GLCs

·         Capítulo 3

1.    Máquinas de Turing

2.    Variantes da Máquina de Turing

·         Capítulo 4

1.    Decidibilidade

·         Capítulo 5

1.    Redutibilidade

2.   

Redutibilidade por histórias de computação

3.   

Redutibilidade por mapeamento

·         Capítulo 7

1.    Complexidade de tempo

2.    A classe P

3.   

A classe NP; NP-completude, redutibilidade em tempo polnomial

·         Capítulo 8

1.    A classe PSPACE

2.    PSPACE-completude

Bibliografia

Bibliografia Básica

Introdução à Teoria da Computação, Michael Sipser, Thomson Pioneira, ISBN 8522104999, 2007.

Bibliografia Suplementar

Introdução à Teoria dos Autômatos, Linguagens e Computação, John E. Hopcroft, Rajeev Motwani e Jeffrey D. Ullman, Editora Campus, Outubro 2002, ISBN 85-352-1072-5. Elements of the Theory of Computation (Second Edition), Harry R. Lewis and Christos Papadimitriou, Prentice-Hall, 1998, ISBN: 0-13-262478-8.

Automata and Computability, Dexter Kozen, Springer, 1997, ISBN: 0-387-94907-0.

Computational Complexity, Christos Papadimitriou, Addison Wesley, 1994, ISBN: 0-201-53082-1.