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

Segundo Semestre de 2008

Horário e local

3^a 10-12, 6^a 08-10, Sala D-218

Professores

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

Regras gerais para condução da disciplina

aqui

ATENÇÃO: Newsgroup

Todas as mensagens relativas à disciplina são veiculadas no grupo de notícias depto.cursos.grad.if689.

Monitoria

Antonius Pyetro do Amaral Ferreira (apaf)
Jesus Sanchez-Palencia Fernandez Filho (jspff)
João Victor Guimarães de Lemos (jvgl)
Rodrigo Diego Melo Amorim (rdma)
Tiago de Farias Silva (tfs)

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

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

08-Ago
Autômatos Finitos

12-Ago
Autômatos Finitos Determinísticos
Linguagem de um Autômato
Linguagens regulares

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

19-Ago
(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

22-Ago
(Mini-Prova)
Linguagens Não-Regulares
Lema do Bombeamento

26-Ago
Primeira Prova

29-Ago
Gramáticas Livres-do-Contexto
Forma Normal de Chomsky
Árvores sintáticas

02-Set
Ambigüidade em gramáticas
Autômatos com Pilha

05-Set
Autômatos com Pilha versus Gramáticas Livres-do-Contexto

09-Set
A Segunda Prova vai ser no dia 19 DE SETEMBRO (sexta, ao meio dia)

12-Set
Máquinas de Turing
Linguagens Turing-reconhecíveis

16-Set
Variantes da Máquinas de Turing: Várias fitas

19-Set
Máquinas de Turing Não-Determinísticas

23-Set
(Mini-Prova)
Enumeradores

26-Set
Decidibilidade
Problemas concernentes a Linguagens Regulares

30-Set
Problemas concernentes a Linguagens Livres-do-Contexto