Jupiterweb

Informa??es da Disciplina

Preparar para impressão

Júpiter - Sistema de Graduação

Instituto de Matemática e Estatística

Ciência da Computação

Disciplina: MAC0414 - Autômatos, Computabilidade e Complexidade

Automata, Computability and Complexity

Créditos Aula:	4
Créditos Trabalho:	0
Carga Horária Total:	60 h
Tipo:	Semestral
Ativação:	01/01/2015	Desativação:

Objetivos

Estudo de vários formalismos para computação e algoritmos e as limitações de certas formas de computação.

Docente(s) Responsável(eis)

47490 - Arnaldo Mandel

Programa Resumido

Palavras, linguagens, operações sobre linguagens. Linguagens regulares. Autômatos finitos determinísticos e não determinísticos. Teorema de Kleene. Autômatos reduzidos. Modelos de computação; máquinas de Turing. Tese de Church. Redutibilidade e problemas indecidíveis. Complexidade, problemas decidíveis em tempo polinomial. Não-determinismo versus determinismo. Redutibilidade e problemas NP-completos. Teorema de Cook-Levin.

Programa

Avaliação

Método

Critério

Média ponderada de provas e exercícios.

Norma de Recuperação

Bibliografia

A.V. Aho, R. Sethi, J.D. Ullman, Compilers, Principles, Techniques and Tools>/i>, Addison-Wesley, 1986.
J.E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Weley, 2000.
H.R. Lewis, C.H. Papadimitriou, Elementos de Teoria da Computação, 2nd ed., Bookman, 2000.
P.B. Menezes, Linguagens Formais e Autômatos, 3a ed., Sagra Luzzatto, Porto Alegre, 2000.
M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2012.

Clique para consultar os requisitos para MAC0414

Clique para consultar o oferecimento para MAC0414