MAC0414 Autômatos, Computabilidade e Complexidade
Por | EmAté 2014 se chamou MAC0414 Linguagens Formais e Autômatos.
Este disciplina é formada por uma coletânea de tópicos que eram apresentados nas extintas
MAC0414 Linguagens Formais e Autômatos,
MAC0423 Introdução à Teoria da Computabilidade, e
MAC0430 Algoritmos e Complexidade de Computação.
OBJETIVOS: Estudo de vários formalistmnos para computação e algoritmos e as limitações de certas formas de computação.
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.
RESPONSÁVEL: Arnaldo Mandel
PRÉ-REQUISITOS: MAC0338.
CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS: 4 horas, 4 créditos-aula.
CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM: Média ponderada de provas e exercícios.
BIBLIOGRAFIA BÁSICA:
- A.V. Aho, R. Sethi, J.D. Ullman, Compilers, Principles, Techniques and Tools, 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.
OBSERVAÇÃO: Disciplina optativa eletiva no currículo do BCC.
[Veja dados da disciplina no JúpiterWeb]