Introdução à Teoria da Computação (CI-1059)
Professor: Murilo V. G. da Silva
Horário das aulas:
- Terça-feira 13h30-15h30
- Quinta-feira 13h30-15h30
Horário de antendimento:
- Terça-feira 15h30-17h30
Local das aulas:
- PA-01
Data da P1: 15/04/2025
Data da P2: 22/05/2025
Data da P2: 26/06/2025
Conteúdos cobertos na disciplina:
- Motivação Linguagens Formais e AFDs [SIL17: até 3.2] [SIP06 até 1.1] [HMU01 1.1-5, 2.1, 2.2.1-6]
- NFAs e epsilon-NFAs [SIL17: 3.2-5] [SIP06: 1.2] [HMU01: 2.3, 2.5.1]
- ERs e Lema do Bombeamento [SIL17: 3.6, 4.1, 4.2.1, 4.2.2] [SIP06: 1.2-4,2.2] [HMU01: 2.5.1-5, 3.1, 3.2, 4.1, 6.1, 6.2]
- APs e Gramáticas [SIL17: 4.2-3] [SIP06: 2.1-2] [HMU: 5.1, 5.2.1-5., 5.4.1, 5.4.3-4, 6.2-3]
- Máquinas de Turing [SIL17: cap. 5] [SIP06: 3.1-2] [HMU: 8.1, 8.2-4]
- A Tese de Church-Turing e Computabilidade [SIL17: 5.3, cap. 6 e 7] [SIP06: 3.2-3, 5.1-2] [HMU: 8.3-4, 8.6, 9.1-2, 9.3.1-2]
- Introdução à Teoria de Complexidade Computacional [SIL17: cap. 9, 10] [SIP06: ] [HMU: ]
- Reduções e NP-completude de problemas [SIL17: 11] [SIP06: cap. 7, 8 e 9 ] [HMU: cap. 10 e 11]
Sistema de Avaliação:
Provas (P1 + P2 + P3) / 3
Material de apoio e cursos semelhantes de outras universidades: (aqui)
Bibliografia principal
-
[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 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.)