Ementa

 

Aula
Assunto
Responsável
Dia
1

Apresentação do Curso

  • Motivação
  • Contextualização da disciplina
  • Apresentação dos objetivos
  • Bibliografia
  • Critérios de Avaliação
Porfírio
13/01/2000
2

Visão Histórica

  • Problemas de Hilbert
  • Teorema de Gödel
  • Máquina de Turing
  • Tese de Church
Porfírio
13/01/2000
3

Revisão/Introdução de Conceitos Preliminares 1

  • Teoria dos Conjuntos
  • Funções
  • Relações
  • Conjuntos Contáveis e Incontáveis
Porfírio
14/01/2000
4

Revisão/Introdução de Conceitos Preliminares 2

  • Definições Recursivas
  • Grafos
  • Indução Matemática
Porfírio
14/01/2000
5

Alfabetos e Linguagens

  • Conceito de Linguagens ·
  • Procedimentos e Algoritmos · Cadeias ·
  • Especificação finita de Linguagens
  • A Hierarquia de Chomsky
Porfírio
17/01/2000
6

Conjutos Regulares e expressões
Porfírio
17/01/2000
7

Autômatos Finitos 1

  • Autômatos finitos deterministicos ·
  • Diagramas de estado
  • Autômatos incompletos
  • Autômatos com transições em vazio
  • Eliminação das transições vazio
Porfírio
18/01/2000
8

Autômatos 2

  • Autômatos não determinísticos ·
  • Remoção do não determinismo
  • Equivalência entre autômatos deterministicos e não deterministicos
Porfírio
18/01/2000
9

Autômatos e e Linguagem Regulares

  • Equivalência entre autômatos e gramáticas regulares
  • Linguagens não regulares
  • Pumping lemma para gramáticas regulares
Fábio e Ricardo - Equipe1
19/01/2000
10

Autômato Finito Mínimo

  • Equivalência de estados ,
  • autômato deterministico mínimo
Tathiane e VictóriaEquipe2
19/01/2000
11

Algoritmos sobre autômatos

  • Aplicações de Autômatos
  • Diagrama de Estados
Emanuel e Jeandro -Equipe3
20/01/2000
12

Exercícios/Revisão
Porfírio
20/01/2000
13

Gramáticas Livres de Contexto

  • Gramáticas Livres de Contexto e Linguagens -
  • Árvores de Derivação -
  • Derivação a esquerda e a direita
  • Ambíguidade
Porfírio
21/01/2000
14

Autômatos de Pilha

  • Definição de Autômatos de pilha
  • Autômatos de pilha (PDA's), acceptance modes
  • Autômatos de Pilha determinísticos
  • Autômatos de Pilha e Linguagens livres de contexto
Mardônio e Katy - Equipe4
21/01/2000
15

Determinismo e Análise Sintática

  • A universalidade das derivações mais a esquerda (leftmost derivations)
  • gramáticas lineares a direita
Equipe5
24/01/2000
16

Simplificação de gramáticas livres de contexto

  • Eliminação das transições vazias
  • Regra da cadeia
Ruthênio e Marcelo
24/01/2000
17

Algoritmos para gramáticas livres de contexto

  • Forma Normal de Chomsky
  • Forma Normal de Greibach
  • Programação Dinâmica
Neila e Liédja
25/01/2000
18

Propriedades da linguagens livres de contexto

  • Llinguagens que não são livres de contexto
  • Pumpping lemma
Aline e Gustavo - Equipe8
25/01/2000
19

Máquinas de Turing

  • Definição e Notação
Nakakura - Equipe9
26/01/2000
20

Computando com máquinas de Turing

Luiz e Lívia - Equipe10
26/01/2000
21

Exercícios/ Laboratório
Porfírio
27/01/2000
22

Extensões da Máquina de Turing

  • Máquinas de Turing de Acesso Aleatório
Equipe11
27/01/2000
23

Máquinas de Turing não deterministicas
Equipe12
28/01/2000
24

Funções primitivamente recursivas
Equipe13
28/01/2000
25

Máquinas de Turing Universais
Equipe14
31/01/2000
26

Problemas Indecidíveis
Equipe15
31/01/2000
27

Tese de Church
Porfírio
01/02/2000
28

Avaliação
Porfírio
01/02/2000
29

Revisão Final
Porfirio
02/02/2000
30

NEF
Porfírio
02/02/2000

 

1