Introdução à Teoria da Computação (CI-1059 -- TURMA A)

Professor: Murilo V. G. da Silva

Horário das aulas:
- Terça-feira 13h30-15h30
- Quinta-feira 13h30-15h30
Horário de antendimento (com agendamento):
- Terça-feira 15h30-14h30
Local das aulas:
- PC-16

Data da P1: 16/10/2025 (Notas P1)
Data da P2: 18/11/2025
Data da P2: 04/12/2025
Data do Exame Final: 18/18/2025

Conteúdos cobertos na disciplina:

- Motivação Linguagens Formais e AFDs
- AFNs e epsilon-AFNs
- ERs e Lema do Bombeamento
- APs e Gramáticas
- Máquinas de Turing
- A Tese de Church-Turing e Computabilidade
- Complexidade de Kolmogorov
- Introdução à Teoria de Complexidade Computacional
- Reduções e NP-completude de problemas

Sistema de Avaliação:
Provas (P1 + P2 + P3) / 3

Slides selecionados: (aqui)
Material de apoio e cursos semelhantes de outras universidades: (aqui)

Bibliografia principal

[SIL25] -- SILVA, M.V.G. Autômatos, Computabilidade e Complexidade Computacional , 2025.

[HMU01] -- HOPCROFT, J. E.; MOTWANI R.; ULLMAN, J. D. Introduction to Automata Theory, Languages, and Computation (2nd Edition) , Addison Wesley, 2001.

[SIP06] -- SIPSER, M. Introduction to the Theory of Computation , Thomson Course Technology, 2006.

[DPV06] -- DASGUPTA, S.; PAPADIMITRIOU C. H.; VAZIRANI, U. Algorithms (capítulo 8) , McGraw-Hill 2006

[PAP94] -- PAPADIMITRIOU, C. H. Computational Complexity (capítulo 9) , Addison Wesley Longman 1994

[ABA06] -- ARORA, S.; BARAK B. Computational Complexity - A Modern Approach (capítulos 1 e 2) , McGraw-Hill 2006

[MME11] -- MOORE, C.; MERTENS, S. The Nature of Computation (capítulo 7) , Oxford 2011

[AAR13] -- AARONSON, S. Quantum Computing Since Democritus , Cambridge 2013

Bibliografia auxiliar

GAREY, M. R.; JOHNSON, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman 1979

SUDKAMP, T. A. Languages and Machines: An Introduction to the Theory of Computer Science (3rd Edition), Addison Wesley, 2005.

LEWIS, H. R.; PAPADIMITRIOU C. H. Elements of the Theory of Computation (2nd Edition), Prentice Hall 1997

Material extra ("fun stuff"):

Máquina de Turing de Lego: [lego.flv] (Assunto envolvido: Máquina de Turing)

Máquina Analítica de Charles Babbage: [babbage.flv] (Assunto envolvido: universalidade da computação, século 19)

Programa para a Máquina Analítica escrito por Ada Lovelace: [ada.png] (Assunto envolvido: algoritmo para computador)

Como computar com DNA: [dna.flv] (Assunto envolvido: universalidade da computação, TCT e o mundo físico)

Entrevista com Scott Aaronson (MIT): [aaronson.mp4] (Assunto envolvido: Conjectura P != P-SPACE, tempo, espaç e o mundo físico)

Mecanismo de Antikythera: [antikythera.flv] (Assunto envolvido: Mecanismo MUITO antigo (não turing completo) para cálculos astronômicos, século 1 a.C.)

Computar com o jogo da vida: [life1.mp4] [life2.mp4] [life3.mp4] (Assunto envolvido: universalidade da computação, jogo da vida)