Universidade Federal de Pernambuco (UFPE)
Centro de Informática (CIn)
Graduação em Ciência da Computação e Engenharia da Computação

IF689 - Informática Teórica

Primeiro Semestre de 2011

Horário e local

4^a 15-17h, 6^a 13-15h, Sala D-002

Professores

Anjolina Grisi de Oliveira e Ruy José Guerra Barretto de Queiroz.

Regras gerais para condução da disciplina

aqui

ATENÇÃO: Rede Social

Tudo sobre a disciplina estará sendo veiculado na comunidade Informática Teórica 2011.1 no Orkut.

Produção de verbetes da Wikipedia

Lema do bombeamento para linguagens regulares
Lema do bombeamento para linguagens livres de contexto
Linguagens recursivamente enumeraveis
Gramática ambígua
Forma Normal de Chomsky
PSPACE-complete
PSPACE-completude
Complexidade de tempo
Máquina de estados finitos não determinística
Redução (complexidade)
Conjuntos recursivamente enumeraveis
Teorema de Savitch
Satisfatibilidade
Teorema de Rice
Fórmula booleana totalmente quantificada
Complexidade NL
Problema do isomorfismo de grafos

Monitoria

Tarcísio Coutinho da Silva (tcs5)
(a confirmar)

Bibliografia Básica

Introdução à Teoria da Computação, Michael Sipser, Thomson Pioneira, ISBN 8522104999, 2007. (Tradução brasileira de Introduction to the Theory of Computation, Michael Sipser, Second Edition, PWS Publishing Company, February 2005, ISBN 0-534-95097-3.)

Bibliografia Suplementar

Introdução à Teoria de Autômatos, Linguagens e Computação, John E. Hopcroft, Rajeev Motwani e Jeffrey D. Ullman, Editora Campus, ISBN 85-352-1072-5, Outubro 2002. (Tradução para o português de Introduction to Automata Theory, Languages, and Computation, 2/E, Addison-Wesley, 2001, ISBN: 0-201-44124-1. Página de apoio: http://www-db.stanford.edu/~ullman/ialc.html)

Atenção:

Apontadores Interessantes:
Entscheidungsproblem.
Zum Hilbertschen Aufbau der reelen Zahlen, por W. Ackermann, publicado em Mathematische Annalen 99:118-133, 1928.
Über die Erfüllbarkeit gewisser Zählausdrücke, por W. Ackermann, publicado em Mathematische Annalen 100:638-649, 1928.
On formally undecidable propositions of Principia Mathematica and related systems I, por K. Gödel, 1931.

Programação de Aulas

02-Mar
Motivação: Problemas de Decisão
O Entscheidungsproblem
Exibição do trailer do filme Julia Robinson and Hilbert's Tenth Problem
Alfabetos e Linguagens

11-Mar
Autômatos Finitos

16-Mar
Autômatos Finitos Determinísticos
Linguagem de um Autômato
Linguagens regulares

18-Mar
Operações com linguagens regulares
Fecho sob operações regulares (união)
Autômatos Finitos Não-Determinísticos

23-Mar
(Mini-Prova)
De Autômatos Finitos Não-Determinísticos para Autômatos Finitos Determinísticos
Fecho sob operações regulares (concatenação, estrela)
Expressões Regulares
De Expressões Regulares para Autômatos Finitos
De Autômatos Finitos para Expressões Regulares

25-Mar
(Mini-Prova)
Linguagens Não-Regulares
Lema do Bombeamento

30-Mar
Primeira Prova

01-Abr
Gramáticas Livres-do-Contexto
Forma Normal de Chomsky
Árvores sintáticas

06-Abr
Ambigüidade em gramáticas
Autômatos com Pilha

08-Abr
Autômatos com Pilha versus Gramáticas Livres-do-Contexto

13-Abr
Segunda Prova

15-Abr
Máquinas de Turing
Linguagens Turing-reconhecíveis

20-Abr
Variantes da Máquinas de Turing: Várias fitas

27-Abr
Máquinas de Turing Não-Determinísticas

29-Abr
(Mini-Prova)
Enumeradores

04-Mai
Decidibilidade
Problemas concernentes a Linguagens Regulares

06-Mai
Problemas concernentes a Linguagens Livres-do-Contexto