Semana
|
Conteúdo
|
Slides
|
Udacity
|
12-14/09
|
Introdução. Conceitos matemáticos preliminares.
|
ftc01
|
 |
19-21/09
|
Autômato finito determinista (DFA), Linguagem Regular (LR).
|
ftc02
|
Unit 1 - 26/09
|
26-28/09
|
Autômato finito não determinista (NFA), Equiv. NFA = DFA.
Propriedades de LRs. Expressões Regulares
|
ftc03
ftc04
|
|
03-05/10
|
Minimização de DFA. Gramática regular (GR).
Equivalência. GR = DFA.
|
ftc04A
ftc05
|
Unit 2 - 10/10
|
10/10
|
Exercícios.
|
|
|
24-26/10
|
Problemas decidíveis sobre Linguagens Regulares.
Lema do Bombeamento para Linguagens Regulares.
|
ftc06
ftc07
|
|
31/10
|
Exercícios.
|
ex01
|
ex01-solução
|
07-09/11
|
PROVA 1 - 07/11/2016
|
ex02
|
Unit 3 - 14/11
|
16-18/01/2017
|
Linguagem (CFL) e gramática livre de contexto (CFG).
Um pouco sobre análise sintática (parsers)
|
ftc08
ftc09
|
|
23-25/01
|
Formas normais de CFGs. Algoritmo CKY
Autômatos de Pilha (PDA). Equivalência NPDA = CFGs.
|
ftc10
ftc11
|
|
30-01/02
|
Linguagens Não Livres de Contexto e Livres de Contexto Deterministas.
Propriedades de CFLs. Exercícios.
|
ftc12
ftc13
|
Unit 4 - 0512
|
06-08/02
|
Lema do Bombeamento para CFLs.
|
ftc14
|
Unit 5 - 27/06
|
13-15/02
|
Exercícios
|
ex02
|
ex02-solução
|
20-22/02
|
PROVA 2 - 22/02/2017
|
|
Unit 5,6,7 - 16/01
|
06-08/03
|
Máquinas de Turing. video: Turing Machines
Computando funções com MTs.
|
ftc15
ftc16
|
|
13-15/03
|
Tese de Church-Turing. Variantes de Máquinas de Turing.
MT Universal. Enumerabilidade. video interessante: How To Count Past Infinity
|
ftc17
ftc18
|
Exam - 30/01
|
20-22/03
|
Linguagens Recursivas, Recursivamente Enumeráveis e Não Recursivamente Enumeráveis. Hierarquia de Chomsky. Decidibilidade. Indecidibilidade.
|
ftc19
ftc20
|
|
27/03
|
Problema da Parada. video: Halting Problem
Redução de problemas. Teorema de Rice
|
ftc21
|
|
29/03
|
PROVA 3 - 29/03/2017
|
|
|
05/03
|
EXAME ESPECIAL - 05/03/2017
|
|
|
