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
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.
 
 
 
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

Créditos | Fale conosco
© 1999 - 2019 - Superintendência de Tecnologia da Informação/USP