1. O que é Teoria da Computação
2. Metodologia de Ensino
3. Metodologia de Avaliação

MOTIVACIONAL: Os códigos e as linguagens...

Cap. 1 do Livro do Papadimitriou.

Uma breve introdução a Teoria da Computação
 

Revisão conteúdo de Matemática Discreta

Alfabetos e Linguagens

1. (60min) TESTE de Revisão de conceitos Preliminares de Matemática Discreta:
   1. Conjuntos
   2. Relações
   3. Funções
   4. Grafos
2. Conceitos Preliminares

Cap. 1 do Livro do Papadimitriou.

Alfabetos e Linguagens

 TIRA-DÚVIDAS e

PROVA ESCRITA 1: expressões, fundamentos de linguagens

1. Máquinas de Estados Finitos
2. Autômatos Finitos Determinísticos

Cap. 1 do Livro do Papadimitriou.

Cap. 2 do Livro do Paulo Menezes

Animação: http://www.cs.montana.edu/~dynalab/

Exercícios - Autômatos Finitos

Cap. 1 do Livro do Papadimitriou.

Cap. 2 do Livro do Paulo Menezes

Bônus-extra: Entender o Algoritmo de conversão de AFN em AFD e resolver a questão 2.2.6

TIRA-DÚVIDAS e exercícios do Capítulo 2

1. PROVA ESCRITA 2: TESTE Autômatos Finitos Determinísticos

• http://www.li.facens.br/~tiemi/Tc1/afn.pdf

1. Autômatos e Linguagens
2. Minimização de Estados
3. PROVA ESCRITA 3: TESTE Autômatos Finitos Não-Determinísticos

1. Seção 2.3 do Livro texto
2. Seção 2.5 do Livro texto
3. Algoritmo Minimização
4. Outra explicação do algoritmo de minimização

1. Minimização de Estados (continuação)
2. TIRA-DÚVIDAS e exercícios do Capítulo 2

1. Seção 2.3 do Livro texto
2. Seção 2.5 do Livro texto
3. Algoritmo Minimização
4. Outra explicação do algoritmo de minimização
5. 
   
6. TRABALHO: (20.jun por email para jones.albuquerque@gmail.com) Implementar em Python, usando Orientação a Objetos, um minimizador de autômatos que receba como ENTRADA: uma t-upla (definindo um autômato) e tenha como SAÍDA: o autômato mínimo.
   ENTREGA MÁXIMA: 04 de março, entrega de código-fonte e texto em formato de artigo científico: MODELO AQUI.
   • VIDE Exemplos de implementações de Autômatos AQUI.
   • Mais sobre Autômatos em Python
   • CLASSE DFA PRONTA!! Se preferir, é só usá-la!!

1. estudos sobre Minimização de Estados (continuação)
2. Equivalência AFDs e AFNs

• http://www.li.facens.br/~tiemi/Tc1/afn.pdf

• 1. Tira-dúvidas
  2. PROVA ESCRITA 4: Exp. regulares, AFD, AFN e minimização de estados

1. FECHAMENTO 1 VA 

• Linguagens Livres de Contexto

Gramáticas Livres de Contexto 

Árvores de Análise Sintática e Autômatos a Pilha

Gramática Python
Gramática Java

• Autômatos a Pilha e Gramáticas Livres de Contexto
• Exercícios

 tirdúvidas GLC - Gramáticas Livres de Contexto

1. PROVA ESCRITA 1 - 2VA - (Gramáticas Livres de Contexto e Autômatos a Pilha)

Máquinas de Turing

Computação com Máquinas de Turing

• Seção 4.1
• Alan Turing Biography
• Tutorial Máquina de Turing

1. Exercícios Máquinas de Turing LISTA
2. Máquinas de Turing: outros modelos e exercícios

1. PROVA ESCRITA 2 - 2VA - (Máquinas de Turing)

Exercícios Máq. Turing e Indecidibilidade

Indecidibilidade

Problema da Parada

Capítulo 5

Seção 5.1 e 5.3
Simulador Máquina de Turing
Exercícios Máquina de Turing

50-52

1. Indecidibilidade e Complexidade Computacional
2. Tira-Dúvidas e Execícios

54 a 58

1. Complexidade Computacional
2. Exercícios
3. PROVA ESCRITA 3 e 4 - 2VA - teste capítulo 4 a 6 (Complexidade e Computabilidade)