Teoria da Computação

Prévia do material em texto

60Teoria da Computação
Graduação - Bacharelado
Engenharia de Computação
PLANO DE ENSINO
CURSO:
MODALIDADE:
DISCIPLINA: CH:
EMENTA:
· Diferenciar e classificar autômatos, máquinas abstratas, gramáticas gerativas.
· Aplicar conceitos fundamentais do processo computacional e suas limitações.
· Diferenciar as Linguagens Formais e elementos de Teoria da Computação.
 
Autômatos Finitos. Linguagens Livres de Contexto. Máquinas de Turing. Tese de Church. Complexidade 
computacional. 
HABILIDADES
PRÉ- REQUISITOS (SUGERIDOS)
· Cálculo A (GRD-NGR-0003)
 
CORREQUISITOS (SUGERIDOS)
Não se aplica.
 
CONTEÚDOS FORMATIVOS
· Autômatos Finitos.
o Alfabetos. 
o Linguagens. 
o Expressões regulares. 
o Autômatos finitos deterministas e não-deterministas. 
o Equivalência entre autômatos.
o Linguagens regulares e suas propriedades.
o Existência de linguagens não-regulares: teorema do bombeamento.
· Linguagens Livres de Contexto
o Conceito de gramática. 
o Gramáticas livres de contexto. 
o Gramáticas regulares. 
o Autômatos de pilha. 
o Linguagens livres de contexto e suas propriedades. 
o Determinismo. 
o Introdução a análise léxica e sintática.
· Máquinas de Turing.
o Computação com Máquinas de Turing. 
o Combinação de Máquinas de Turing. 
o Extensões das Máquinas de Turing. 
o Máquinas de Turing não-deterministas.
· Tese de Church
o A tese de Church. 
o Máquinas de Turing e gramáticas. 
o Funções primitivas recursivas. Godelização. 
o Funções mu-recursivas. Turing computabilidade. Máquinas de Turing universais. Não-
Página 1 de 2
60Teoria da Computação
Graduação - Bacharelado
Engenharia de Computação
PLANO DE ENSINO
CURSO:
MODALIDADE:
DISCIPLINA: CH:
ATIVIDADES PRÁTICAS
Não se aplica.
REFERÊNCIAS BÁSICAS:
LEWIS,HarryR;FURMANKIEWICZ,Edson (Trad.). Elementos de teoria da computação. 2.ed. Porto Alegre: 
Bookman, 2000. 344 p. ISBN 8573075341
GERSTING, Judith L.; Fundamentos Matemáticos para Ciência da Computação, LTC, 2004. 
SIPSER, Michael. Introdução à Teoria da Computação. Thomson Pioneira, 2007, 502 p. ISBN: 9788522104994. 
 
REFERÊNCIAS COMPLEMENTARES:
DIVERIO, T.A.; MENEZES, P.F.B Teoria da Computação - Máquinas Universais e Computabilidade. Boockman, 
2011.
DIVERIO, T.A.; MENEZES, P.F.B. Teoria da Computação, Sagra-Luzzato, 1999. 
LEWIS, H.R.; PAPADIMITRIOU, C.H. Elements of the Theory of Computation. Prentice-Hall, 1981. 
MENEZES, P.F.B. Linguagens Formais e Autômatos, 3.ed., Sagra-Luzzato, 1999. 
HOPCROFT, J.E.; MOTWANI, R.; ULLMAN, J.D. Introdução a Teoria de Autômatos, Linguagens e Computação. 
Campus, 2002, 584 p., ISBN: 8535210725. 
 
 
computabilidade. 
o O problema de parada em Máquinas de Turing. 
o Enumerabilidade. 
o Aceitabilidade. 
o Decidibilidade. 
o Problemas insolúveis. Exemplos.
· Complexidade computacional. 
o Máquinas de Turing limitadas em tempo e espaço. 
o Grau de crescimento de funções. 
o Simulações limitadas em tempo. As classes P e NP. NP- completude. 
o Alguns problemas NP -completos. 
o Hierarquia de complexidade
 
Página 2 de 2
		2021-08-09T20:55:52-0300
	MICHELA DE ANDRADE FERNANDES:74182790510
		2021-08-09T20:56:13-0300
	MICHELA DE ANDRADE FERNANDES:74182790510