25-Mai
Motivação: Problemas de Decisão
O Entscheidungsproblem
Alfabetos e Linguagens
30-Abr
Autômatos Finitos
02-Mai
Autômatos Finitos Determinísticos
Linguagem de um Autômato
Linguagens regulares
04-Mai
Operações com linguagens regulares
Fecho sob operações regulares (Complementação, união, interseção)
Autômatos Finitos Não-Determinísticos:
Motivação; Exemplos; Árvores de Computação
09-Mai
(Mini-Prova)
De Autômatos Finitos Não-Determinísticos para Autômatos Finitos Determinísticos
Fecho sob operações regulares (Concatenação, estrela)
11-Mai
Expressões Regulares
De Expressões Regulares para Autômatos Finitos
16-Mai
(Mini-Prova)
De Autômatos Finitos para Expressões Regulares
18-Mai
Linguagens Não-Regulares
Lema do Bombeamento
23-Mai
25-Mai
Gramáticas Livres-do-Contexto
Forma Normal de Chomsky
Árvores sintáticas
30-Mai
Ambigüidade em gramáticas
Autômatos com Pilha
01-Jun
Autômatos com Pilha versus Gramáticas Livres-do-Contexto
06-Jun
Segunda Prova
13-Jun
Máquinas de Turing
Linguagens Turing-reconhecíveis
15-Jun
Variantes da Máquinas de Turing: Várias fitas
20-Jun
Máquinas de Turing Não-Determinísticas
22-Jun
(Mini-Prova)
Enumeradores
27-Jun
Decidibilidade
Problemas concernentes a Linguagens Regulares
29-Jun
Problemas concernentes a Linguagens Livres-do-Contexto
04-Jul
(Revisão)
06-Jul
O Problema da Parada
Indecidibilidade do Problema da Parada
Uma linguagem Não-Turing-reconhecível
11-Jul
(Mini-Prova)
Redutibilidade
Reduções via histórias de computação
13-Jul
O Problema da Correspondência de Post
Redutibilidade por mapeamento
18-Jul
Complexidade de Tempo
20-Jul
Medindo complexidade
Classes de complexidade de tempo
25-Jul
(Mini-Prova)
A Classe P
27-Jul
A Classe NP
A Questão P versus NP (em português)
01-Ago
Redutibilidade em Tempo Polinomial
NP-Completude
03-Ago
O Problema SAT
10-Ago
(Mini-Prova)
Complexidade de Espaço
15-Ago
Teorema de Savitch
17-Ago
A Classe PSPACE
22-Ago
Terceira Prova
24-Ago
Segunda Chamada
29-Ago
Prova Final
Última atualização: 06 de Julho de 2007, 10:39am GMT-3
ATENÇÃO: Newsgroup
Todas as mensagens relativas à disciplina são veiculadas
no grupo de notícias depto.cursos.grad.if689.