Teoria da Computação - Mestrado em Ciência da Computação (3º quadrimestre/2014)
Horários: 2a-feira, das 14h-16h e 3a-feira, das 14h às 16h
Local: sala 502B, bloco B
Critério de avaliação
- 1 prova escrita P1 valendo 30% da nota da disciplina;
- 1 prova escrita P2 valendo 30% da nota da disciplina;
- 1 projeto valendo 40% da nota da disciplina (conceito F no projeto implica automaticamente em F na disciplina);
- exercícios poderão ser um bônus.
Classificação de conceitos
A ≥ 9,0; B ≥ 7,5; C ≥ 6,0; D ≥ 5,0.
Programa resumido
Linguagens Regulares; Autômato finito; Não-determinismo; Aplicações de autômato finito; Expressões regulares; Aplicações de expressões regulares; Linguagens que não são regulares; Linguagens livres de contexto; Gramáticas livres de contexto; Aplicações de gramáticas livres de contexto; Autômato de pilha; Linguagens que não são livres de contexto; Máquinas de Turing; Decidibilidade; Linguagens decidíveis; O problema da parada; Linguagens indecidíveis.
Bibliografia
1. M. Sipser. Introdução à Teoria da Computação. Cengage Leaning, 2007.
2. J.E. Hopcroft, R. Motwani, J.D. Ullman. Introdução à teoria de autômatos, linguagens e computação. 2a edição, Campus, 2003.
3. H.R. Lewis, C.H. Papadimitriou. Elementos de teoria da computação. 2a edição, Bookman, 2000.
4. C.H. Papadimitriou. Computational Complexity. Addison Wesley, 1995.
Datas Importantes
11/11: prova P1
09/12: prova P2
15/12: Substitutiva
16/12: Vista de prova e pedido de revisão de prova
Planejamento e Materiais (podem sofrer alterações sem aviso prévio)
TIDIA: TeoriaComp-Leticia
| Data | Assunto |
| 29/09: | Programa da disciplina, critério de avaliação e classificação de conceitos. Conceitos básicos de linguagens formais: alfabeto, gramática, linguagens; Introdução a linguagens regulares: máquina de estado finito (autômato finito determinístico (AFD)) |
| 30/09: | Linguagens regulares: como projetar autômatos finitos determinísticos (operações regulares de união, concatenação e estrela) Exercícios 1.1 a 1.6 do livro do Sipser |
| 06/10: | Linguagens regulares: autômatos finitos não-determinísticos (AFN) Operações regulares sobre AFN's Exercícios 1.7 a 1.17 do livro do Sipser |
| 07/10: | Linguagens regulares: equivalência entre AFD's e AFN's Expressões regulares, gramática regular Exercícios 1.18 a 1.19 do livro do Sipser Equivalência entre expressões regulares, gramáticas regulares e autômatos finitos |
| 13/10: | Equivalência entre expressões regulares, gramáticas regulares e autômatos finitos |
| 14/10: | Aula de Exercícios |
| 20/10: | Aula de Exercícios Linguagens regulares: pumping lemma Descrição do Projeto (Entrega até 15/dez pelo TIDIA) Exemplos de arquivos de entrada para o projeto - Parte 1: formato do arquivo, nfa1, nfa2, nfa3, nfa4, nfa5 Exemplos de arquivos de entrada para o projeto - Parte 2: formato do arquivo, g1, g2, g3, g4, g5, g6 Notícia sobre Computação Quântica |
| 21/10: | Entrega da lista de exercícios (Exercícios 1.1 a 1.21 do livro do Sipser) Linguagens regulares: pumping lemma Lista de Exercícios para Linguagens Regulares Linguagens livres de contexto: gramáticas livres de contexto |
| 27/10: | FERIADO |
| 28/10: | FERIADO |
| 03/11: | Linguagens livres de contexto: gramáticas livres de contexto Forma normal de Chomsky Autômatos a pilha Lista de Exercícios para Linguagens Livres de Contexto Exercícios do livro do Sipser: 2.1-2.7 e 2.10-2.15 |
| 04/11: | Linguagens livres de contexto Aula de Exercícios |
| 10/11: | Não haverá aula |
| 11/11: | Prova P1 (As questões da P1 serão tiradas das listas de exercícios. Autorizado uso da "cola oficial" que deve ser entregue junto com a prova) Notas |
| 17/11: | Equivalência de autômatos a pilha e gramáticas livres de contexto (GLC=>AP e AP=>GLC) |
| 18/11: | Pumping lemma das linguagens livres de contexto |
| 24/11: | Máquinas de Turing Lista de Exercícios para Máquinas de Turing |
| 25/11: | Máquinas de Turing |
| 01/12: | Decidibilidade (problemas indecidíveis, o problema da parada) Lista de Exercícios para Decidibilidade |
| 02/12: | Decidibilidade |
| 08/12: | Teoria da Complexidade Lista de Exercícios para Teoria da Complexidade |
| 09/12: | Prova P2 (As questões da P2 serão tiradas das listas de exercícios. Autorizado uso da "cola oficial" que deve ser entregue junto com a prova) Notas Notas Finais |
| 15/12: | |
| 22/12: | Lançamento de Notas |