Teoria da Computação (COS700) - 2019/1


Programa de Engenharia de Sistemas e Computação


Esta é a página do curso de Teoria daComputação (COS700).

Nesta página vocês terão todas as informações a respeito do curso, por isso sempre estejam de olho nela.



Professores:

Fábio Botler
Celina Miraglia Herrera de Figueiredo

Monitores:

Marlos - marlosfmartins@gmail.com
Isaque - isaque@cos.ufrj.br
Victor - vcmessner@gmail.com

Google Classroom: 83vf9p2


Ementa:

Linguagens Regulares e Autômatos Finitos Determinísticos; Expressões Regulares; Relação entre AFD's e Expressões Regulares; Autômatos Finitos Não-Determinísticos; Operações com Autômatos Finitos e Linguagens Regulares; Lema do Bombeamento para Linguagens Regulares; Gramáticas Regulares; Linguagens Livres de Contexto e Gramáticas Livres de Contexto; Árvores de Análise Sintática; Lema do Bombeamento para Linguagens Livres de Contexto; Autômatos de Pilha; Relação entre Gramáticas Livres de Contexto e Autômatos de Pilha; Máquina de Turing; Introdução à Teoria da Complexidade.


Horário e local das aulas:

Início: 12/03/2019
3a. e 5a., 13-15h, sala H324-A


Listas

Lista 1: Entregar até 26/03/2019
Lista 2: Entregar até 25/04/2019
Lista 3: Entregar até 15/05/2019
Lista 4: Entregar até 11/06/2019


Programação esperada:

Março
12Introdução, Complexidade, Computabilidade, Automatos
14 Exemplos, Operações regulares, fecho por união
19 não determinismo, conversão determinismo, fecho por concatenação, estrela
21 Construção de subconjuntos, fecho por concatenação estrela
26 Expressões regulares, Expressão regular implica Automato
28 Bombeamento
Abril
2 Algoritmo de Brzozowski (substituição), Lema de Arden, Fechamento
4 Gramatica Regular, equivalencia com Automato, Gramatica Livre de Contexto, Fechamento LLC
9 aula cancelada devido à chuva
11 Arvores de Analise Sintática, fechamento (matéria da P1 até aqui) ***
16 Bombeamento LLC
Feriadão
25 P1
30 Automato de Pilha
Maio
2 Vista P1 & Seminário de Natasha Morrison
7 Equivalencia AP LLC
9 Máquina de Turing
14 decisor, aceitador, recursivo, recursivamente enumeravel, Hierarquia de Chomsky
16 multiplas fitas, não determinismo, fechamento
21 Tese de Curch-Turing, Máquina de Turing universal
23 indecidibilidade, diagonalização, problema da Parada
28 Palestra do Prof. Luis Menasché Schechter sobre Alan Turing; e P, NP
30 Aula de Monitoria
Junho
4 e 6 Não haverá aula.
11Revisão
13P2
18Vista P2

Bibliografia

COUTINHO, S. C.; SCHECHTER, Luis Menasché. Autômatos, Linguagens Formais e Computabilidade..

SIPSER, M. Introdução à Teoria da Computação, 2ª edição. Cengage Learning, ISBN, p. 978-85, 2007.