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 2012

Horário e local

3^a 08-10h, 6^a 08-10h, Sala D-005

Monitoria

Fernando Neto (fmpn2@cin.ufe.br)
Flavia Porto Costa (fpc@cin.ufe.br)
Daniel Bezerra (db@cin.ufe.br)
Sergio Renan Ferreira Vieira (srfv@cin.ufe.br)
Página Monitoria

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

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

07-Dez
Palestra "O legado de Alan Turing"
Professor Ruy J. G. B. de Queiroz

11-Dez
Autômatos Finitos
Aula 2
Autômatos Finitos Determinísticos
Linguagem de um Autômato
Linguagens regulares

14-Dez
Operações com linguagens regulares
Fecho sob operações regulares (união)
Aula 3

18-Dez
Autômatos Finitos Não-Determinísticos
Aula 4

Primeira Mini Prova: Sala D005 - 8:00h

21-Dez
Autômatos Finitos Não-Determinísticos
Aula 4

15-Jan
De Autômatos Finitos Não-Determinísticos para Autômatos Finitos Determinísticos
Aula 5 - Parte 1
Fecho sob operações regulares (concatenação, estrela)
Aula 5 - Parte 2

18-Jan
Expressões Regulares
Aula 6 - Parte 1

De Expressões Regulares para Autômatos Finitos
De Autômatos Finitos para Expressões Regulares
Aula 6 - Parte 2

22-Jan
Linguagens Não-Regulares
Lema do Bombeamento
Aula 7

25-Jan
Primeira Prova

29-Jan
Gramáticas Livre de Contexto
Ambigüidade em gramáticas
Aula 8

01-Fev
Autômatos com Pilha
Autômatos com Pilha versus Gramáticas Livres-do-Contexto

05-Fev
Segunda Prova

08-Fev
Máquinas de Turing
Linguagens Turing-reconhecíveis

12-Fev
Carnaval

15-Fev
Variantes da Máquinas de Turing: Várias fitas

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

22-Fev
Decidibilidade
Problemas concernentes a Linguagens Regulares

26-Fev
Problemas concernentes a Linguagens Livres-do-Contexto

01-Mar
O Problema da Parada
Indecidibilidade do Problema da Parada
Uma linguagem Não-Turing-reconhecível