MAC0414  Autômatos, Computabilidade e Complexidade

Até 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>/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.

OBSERVAÇÃO:  Disciplina optativa eletiva no currículo do BCC.