Ministério da Educação
Brasil um país de todos
Personal tools
You are here: Home Members Rodrigo Soares Introdução à Teoria da Computação Introdução à Teoria da Computação 2015.2
Navigation
Log in


Forgot your password?
 
Document Actions

Introdução à Teoria da Computação 2015.2

by Rodrigo Soares last modified 2016-03-18 19:22

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



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




Listas de exercício





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.


Powered by Plone CMS, the Open Source Content Management System

This site conforms to the following standards: