| Maio |
|
4
|
Apresentação |
|
4
6
|
Introdução, Complexidade, Computabilidade,
Automatos, Exemplos, Operações regulares, fecho por união |
|
11
13
|
Não determinismo, conversão determinismo,
Construção de subconjuntos, fecho por concatenação, estrela |
|
18
20
|
Expressões regulares, Expressão regular implica Automato,
Bombeamento Linguagem Regular
|
|
25
|
Algoritmo de Brzozowski (substituição), Lema de Arden |
|
27
|
Gramatica Regular, equivalencia com Automato
- quadro
|
|
|
| Junho |
|
1-3
|
P1
|
|
8
|
Linguagens Livre de Contexto
Fechamento LCC
- quadro
|
|
10
|
Árvores de Análise Sintática,
Gramáticas ambíguas
- quadro
|
|
15
|
Bombeamento LLC
- quadro
|
|
17
|
Automato de pilha
- quadro
|
|
22 |
Equivalencia AP LLC
- quadro
|
|
24
|
Máquinas de Turing de maneira semi-formal
- quadro
|
|
29
|
Máquinas de Turing de maneira formal;
decisores; linguagens recursivas
- quadro
|
|
|
| Julho |
|
1
|
aceitadores; linguagens recursivamente enumeráveis;
máquinas com múltiplas fitas e máquinas não determinísticas,
- quadro
|
|
6 |
equivalência entre determinismo e não determinismo em máquinas de Turing;
Máquina de Turing universal
- quadro
|
|
8
|
O Problema da Parada, Indecidibilidade, Redução por mapeamento
- quadro
|
| 13
|
Palestra do Prof. Luis Menasché Schechter
A Vida e as Contribuições Científicas de Alan Turing |
|
15
|
Introdução à Teoria da Complexidade
- quadro
|
|
19-26
|
P2
|