Universidade Federal de Pernambuco (UFPE)
Centro de Informática (CIn)
Graduação em Ciência da Computação e Engenharia da Computação
3a 10-12h, 6a 08-10h, Sala D-002
Ruy José Guerra Barretto de Queiroz.
(a ser anunciada).
(a confirmar)
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.)
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)
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.
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
07-Dez
Autômatos Finitos
11-Dez
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)
Autômatos Finitos Não-Determinísticos
18-Dez
(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
21-Dez
(Mini-Prova)
Linguagens Não-Regulares
Lema do Bombeamento
15-Jan
Gramáticas Livres-do-Contexto
Forma Normal de Chomsky
Árvores sintáticas
18-Jan
Ambigüidade em gramáticas
Autômatos com Pilha
22-Jan
Autômatos com Pilha versus Gramáticas Livres-do-Contexto
25-Jan
Lema do Bombeamento para Linguagens Livres-do-Contexto
29-Jan
Primeira Prova
01-Fev
Máquinas de Turing
Linguagens Turing-reconhecíveis
05-Fev
Variantes da Máquinas de Turing: Várias fitas
08-Fev
Máquinas de Turing Não-Determinísticas
15-Fev
(Mini-Prova)
Enumeradores
19-Fev
Decidibilidade
Problemas concernentes a Linguagens Regulares
22-Fev
Problemas concernentes a Linguagens Livres-do-Contexto
26-Fev
O Problema da Parada
01-Mar
Indecidibilidade do Problema da Parada
Uma linguagem Não-Turing-reconhecível
05-Mar
(Mini-Prova)
Redutibilidade
Reduções via histórias de computação
08-Mar
O Problema da Correspondência de Post
Redutibilidade por mapeamento
12-Mar
Complexidade de Tempo
15-Mar
Medindo complexidade
Classes de complexidade de tempo
19-Mar
(Mini-Prova)
A Classe P
22-Mar
A Classe NP
26-Mar
A Questão P versus NP (em português)
02-Abr
Redutibilidade em Tempo Polinomial
NP-Completude
05-Abr
O Problema SAT
12-Abr
(Mini-Prova)
Complexidade de Espaço
16-Abr
Teorema de Savitch
19-Abr
A Classe PSPACE
23-Abr
Segunda Prova
26-Abr
Segunda Chamada
29-Abr
Prova Final
Última atualização: 22 de Novembro de 2012, 08:56am GMT-3