Forgot your password?
Document Actions
Introdução à Teoria da Computação 2015.2
Página da disciplina de Introdução à Teoria da Computação
Presença e Notas
Notas do Semestre 2015.2 (Atualizados em 10.12.15)
Avisos
- Cadastre-se no https://groups.google.com/d/forum/itc-si1 e participe do Grupo de Introdução a Teoria da Computação (2015.2).
- Aula de reposição neste sábado, 03.10, às 8:00hs na sala 5 do CEGOE
Ementa e plano de ensino
Bibliografia
Elementos de Teoria da Computação. Harry R. Lewis, Christos H. Papdimitriou. 2. ed. 2004. (LIVRO-TEXTO)
Languages and Machines. Thomas Sudkamp, 3a. ed. Addison-Wesley, 2005. (EXERCÍCIOS)
Menezes, Paulo Blauth. Linguagens Formais e Autômatos. Editora Sagra Luzzatto, 2000. (ALGORITMO DE MINIMIZAÇÃO DE ESTADOS)
Introdução aos fundamentos da Computação - Linguagens e Máquinas. Newton José Vieira. Thomsom, 2006.
Diverio, Tiarajú Asmuz e Menezes, Paulo Blauth. Teoria da Computação: Máquinas Universais e Computabilidade. Editora Sagra Luzzatto, 1999.
Introdução à Teoria de Autômatos, Linguagens e Computação. Hopcroft, J. E. e Ullman, J. D. e Motwani, R. Tradução. Editora Campus, 2003. Exercícios * resolvidos
Software
JFLAP JAVA Formal Language and Automata Package - ferramenta visual usada para criar e simular diversos tipos de autômatos, e converter diferentes representações de linguagens.
Slides
- Slides do Dr. Rakesh Verma da University of Houston
- The University of British Columbia
- Slides do Prof. Lucas Rangel da PUC-Rio
Listas de exercício
- Lista de exercícios sobre autômatos finitos
- Lista de exercícios sobre GLCs e APs
- Lista de exercícios sobre Máquinas de Turing e Indecidibilidade
Aulas
|
créditos |
data | assunto |
Leitura complementar |
|---|---|---|---|
| 2 |
Apresentação da disciplina Introdução a Conjuntos, relações e linguagens. |
Cap. 1 do Livro do Papadimitriou.
|
|
| 4 |
Conjuntos. Relações e funções. Tipos especiais de relações binárias. |
Cap. 1 do Livro do Papadimitriou. |
|
| 6 |
Conjuntos finitos e infinitos. Fechamentos e algoritmos. |
Capítulo 1 do Livro-texto | |
| 8 | Alfabetos e linguagens. Representações finitas de linguagens. | Capítulo 1 do Livro-texto Material de sala de aula | |
| 10 | Alfabetos e linguagens. Representações finitas de linguagens. | Capítulo 1 do Livro-texto Material de sala de aula | |
| 12 | Alfabetos e linguagens. Representações finitas de linguagens. | Capítulo 1 do Livro-texto Material de sala de aula | |
| 14 | Revisão | ||
| 16 | 1o Teste da 1a VA | ||
| 18 | Autômatos finitos determinísticos | Material de sala de aula | |
| 20 | Autômatos finitos não-determinísticos. | Material de sala de aula | |
| 22 | Autômatos finitos não-determinísticos. | ||
| 24 | Linguagens regulares e não-regulares. | Material de sala de aula | |
| 26 | Árvores de análise sintática | ||
| 28 | Técnicas de demonstração | ||
| 30 | Revisão | ||
| 32 | 2o Teste da 1a VA | Assunto: Capítulo 2 e Seção 1.5 do livro texto. Exceto Seção 2.5 | |
| 34 | Gramáticas livres de contexto | Lista de exercícios | |
| 36 | Árvores de análise sintática Autômatos de pilha | ||
| 38 | Árvores de análise sintática Autômatos de pilha | ||
| 40 | Autômatos de pilha e gramáticas livres de contexto | ||
| 42 | Autômatos de pilha e gramáticas livres de contexto | ||
| 44 | Determinismo e análise sintática | ||
| 46 | Determinismo e análise sintática | Lista de exercícios | |
| 48 | Determinismo e análise sintática | Material sobre conjuntos first e follow | |
| 50 | 1o Teste da 2a VA | ||
| 52 | Máquinas de Turing | ||
| 54 | Computação com máquinas de Turing. Gramáticas. | ||
| 56 | Indecidibilidade. A tese de Church-Turing. Máquinas de Turing universais. | ||
| 58 | Problema da parada. Revisão. | ||
| 60 | 2a Prova da 2a VA adiada para quarta-feira, 01.07 | ||
| 62 | Prova da 3a VA | ||
| 64 | Prova Final |
-
Avaliações
NOTA 1V.A. = 2 testes valendo 50% da nota cada um.
NOTA 2V.A. = 2 testes valendo 50% da nota cada um.
NOTA 3V.A. = Prova escrita com todo o conteúdo (100%)
NOTA FINAL = Prova escrita com todo o conteúdo (100%)
- informação de terceiros (Infração Disciplinar) - vide Regimento Geral da UFRPE, Cap. III, Seção IV, Art. 138, pg 113 a 118.