Carregando...

DISCIPLINA Listagem de Ementa/Programa

AUTÔMATOS E COMPUTABILIDADEDISCIPLINA 116882

VER OFERTA

ÓrgãoCIC Departamento de Ciência da Computação
Código116882
DenominaçãoAutômatos e Computabilidade
NívelGraduação
Início da Vigência em1971/2
Pré-requisitos MAT 113107 Algebra 1 OU
MAT 113115 Teoria dos Números 1
EmentaInício da Vigência em 2003/1

Ementa:
Linguagens regulares, livres de contexto, sensíveis ao contexto,
recursivas, recursivamente enumeráveis e não recursivamente enumeráveis:
reconhecedores e geradores. Computabilidade: máquinas de Turing e
funções recursivas. Decidibilidade, redutibilidade. Complexidade:
NP-completude, espaço-completude.

ProgramaInício da Vigência em 2003/1


1. Autômatos finitos determinísticos e não-determinísticos, expressões regulares, equivalência e minimização de autômatos, lema do bombeamento.

2. Gramáticas regulares, gramáticas livres de contexto, ambiguidade, formas normais, autômatos com pilha, lema do bombeamento, gramáticas sensíveis ao contexto.

3. A máquina de Turing, variantes, a tese de Church-Turing, decidibilidade, linguagens recursivas, recursivamente enumeráveis e não recursivamente enumeráveis, o problema da parada.

4. Redutibilidade, autômatos linearmente limitados, funções recursivas, redutibilidade por mapeamento.

5. Auto-referência, o teorema da recursão, oráculos e Turing-redutibilidade.

6. Complexidade de tempo, as classes P e NP, NP-completude, linguagens NP-difíceis.

7. Complexidade de espaço, as classes PSPACE e NPSPACE, PSPACE-completude.

BibliografiaInício da Vigência em 2003/1

Hopcroft, J. E., Motwani, R. e Ulmann, J., Introduction do automata
theory, languages, and computation, Addison Wesley, 3a ed., 2006.
Harry R. Lewis, Christos H. Papadimitriou, Elementos de Teoria da
Computação, Bookman, 2a ed., 1998.
Michael Sipser, Introduction to the Theory of Computation, Cengage
Learning; 3a. edition, 2012.
Thomas A Sudkamp, Languages and Machines, Wesley, 2a ed., 1997.
R. Gregory Taylor, Models of Computation and Formal Languages, Oxford,
1a ed., 1998.

Bibliografia Complementar:
Paulo Blauth Menezes, Linguagens Formais e Autômatos, Sagra, 3a ed.,
2000.
Tiaraju Asmuz Divério e Paulo Blauth Menezes, Teoria da Computação,
Sagra, 1a ed., 1999.
Ann Yasuhara, Recursive Function Theory & Logic, Academic Press, 1a ed.,
1971.