Aula |
Data |
Assunto |
Horas Acum. |
1 |
20-abr |
Motivação: Problemas de Decisão
O Entscheidungsproblem
Alfabetos e Linguagens
Autômatos Finitos
|
02 |
|
22-abr |
FERIADO - Tiradentes
|
|
2 |
27-abr |
Autômatos Finitos Determinísticos
Linguagem de um Autômato
|
04 |
3 |
29-abr |
Operações regulares
|
06 |
4 |
04-mai |
Autômatos Finitos Não-Determinísticos:
Motivaçço; Exemplos; Árvores de Computaçço
|
08 |
5 |
06-mai |
Mini-Prova 12-13hs
De Autômatos Finitos Não-Determinísticos para Autômatos Finitos Determinísticos
Fecho sob operações regulares
|
10 |
7 |
11-mai |
Expressões Regulares
De Expressões Regulares para Autômatos Finitos
|
14 |
8 |
13-mai |
Autômatos Finitos versus Expressões Regulares
Linguagens Não-Regulares
Lema do Bombeamento
|
16 |
9 |
18-mai |
Lema do Bombeamento (cont.)
|
18 |
10 |
20-mai |
Mini-Prova 12-13hs
Revisão
|
20 |
11 |
25-mai |
Primeira Prova |
22 |
12 |
27-mai |
Gramáticas Livres-do-Contexto
Árvores sintáticas
|
24 |
13 |
01-jun |
Forma Normal de Chomsky
|
26 |
14 |
03-jun |
Mini-Prova 13-14hs
Ambigüidade em gramáticas
Autômatos com Pilha
|
28 |
|
08-jun |
Semana Pedagógica
|
|
|
10-jun |
Semana Pedagógica
|
|
15 |
15-jun |
Autômatos com Pilha (cont.)
|
30 |
16 |
17-jun |
Exercícios
|
32 |
17 |
22-jun |
Máquinas de Turing
|
34 |
18 |
29-jun |
Segunda Prova |
36 |
19 |
01-jul |
Máquinas de Turing (cont.)
Linguagens Turing-reconhecíveis
|
38 |
20 |
06-jul |
Variantes da Máquinas de Turing
|
40 |
21 |
08-jul |
Máquinas de Turing Não-Determinísticas
Enumeradores
|
42 |
22 |
13-jul |
Mini-Prova 13-14hs
Decidibilidade
Problemas concernentes a Linguagens Regulares
|
44 |
23 |
15-jul |
Problemas concernentes a Linguagens Livres-do-Contexto
O Problema da Parada
|
46 |
24 |
20-jul |
Exercícios
|
48 |
25 |
22-jul |
Mini-Prova 12-13hs
|
50 |
26 |
27-jul |
Indecidibilidade do Problema da Parada
Uma linguagem Turing-irreconhecível
Redutibilidade
|
52 |
27 |
29-jul |
Reduções via histórias de computação
O Problema da Correspondência de Post
Redutibilidade por mapeamento
|
54 |
28 |
03-ago |
Mini-Prova 12-13hs
Complexidade de Tempo
Medindo complexidade
|
56 |
29 |
05-ago |
Classes de complexidade de tempo
A Classe P
|
58 |
30 |
10-ago |
A Classe NP
A Questão P versus NP
|
60 |
31 |
12-ago |
NP-Completude
O Problema SAT
|
62 |
32 |
17-ago |
Teorema de Cook-Levin
|
64 |
33 |
19-ago |
Terceira Prova
|
66 |
34 |
24-ago |
Segunda Chamada |
68 |
35 |
26-ago |
Prova Final |
70 |