Introdução à Teoria da Computação
(Período Especial 2)
Professor Murilo V. G. da Silva
Sala Virtual: [Link para sala do Google Meet]
Vídeos gravados: [Link para playlist]
Data da primeira prova: 11/12 (15h30) -- PROVA 1: [Link] (2h30m para resolução -- enviar para m.v.g.@gmail.com)
Data da segunda prova: 26/02 (15h30 -- PROVA 2: [Link] (2h30m para resolução -- enviar para m.v.g.@gmail.com)
Data da terceira prova: 19/03 (15h30) -- PROVA 3: [Link] (2h30m para resolução -- enviar para m.v.g.@gmail.com)
Data da prova final: 26/03
06/11 (15h30): Aula síncrona na sala virtual
06/11 (19h30): Ler [SIL17: Até seção 3.1.2] [SIP06: Até seção 1.1] [HMU01: Até seção 2.2.3]
06/11 (19h30): Assistir vídeos disponíveis na playlist
13/11 (15h30): Aula síncrona na sala virtual
13/11 (19h30): Ler [SIL17: Até seção 3.2.3] [SIP06: Até seção 1.2] [HMU01: Até seção 2.3.4.]
13/11 (19h30): Assistir vídeos disponíveis na playlist
20/11 (15h30): Aula síncrona na sala virtual
20/11 (19h30): Ler [SIL17: Até seção 3.6.1] [SIP06: Até seção 1.3] [HMU01:Até seção 3.1 ]
20/11 (19h30): Assistir vídeos disponíveis na playlist
27/11 (15h30): Aula síncrona na sala virtual
27/11 (19h30): Ler [SIL17: Até seção 4.1] [SIP06: Até seção 1.4] [HMU01: Até seção 4.1]
27/11 (19h30): Assistir vídeos disponíveis na playlist
04/12 (15h30): Aula síncrona na sala virtual (revisão -- encontro de 2 horas)
11/12 (15h30): PROVA 1: [Link] (2h30m para resolução -- instruções na folha de prova)
22/01 (08h00): Ler [SIL17: seções 4.2 e 4.3] [SIP06: 2.1, 2.2] [HMU01: 5.1, 5.2, 6.1, 6.2]
22/01 (08h00): Assistir vídeos disponíveis na playlist
29/01 (15h30): Aula síncrona na sala virtual -- encontro de 2 horas (motivo: reposição)
01/02 (19h30): Ler [SIL17: Cap. 5 e Cap. 6] [SIP06: Cap. 3] [HMU01: Cap. 8]
01/02 (19h30): Assitir vídeos disponíveis na playlist
05/02 (15h30): Aula síncrona na sala virtual
08/02 (19h30): Ler [SIL17: Cap. 7] [SIP06: Cap. 4] [HMU01: Cap. 9]
08/02 (19h30): Assistir vídeos disponíveis na playlist
12/02 (15h30): Aula síncrona na sala virtual
19/02 (15h30): Aula síncrona OPCIONAL sala virtual
26/02 (15h30): PROVA 2: [Link] (2h30m para resolução -- instruções na folha de prova)
01/03 (19h30): Ler [SIL17: Cap. 9 e 10] [SIP06: 7.1-3] [HMU01: 10.1]
04/03 (19h30): Assistir vídeos disponíveis na playlist
05/03 (15h30): Aula síncrona na sala virtual
08/03 (19h30): Ler [SIL17: Cap. 11] [SIP06: 7.4] [HMU01: 10.2-4]
08/03 (19h30): Assistir vídeos disponíveis na playlist
12/03 (15h30): Aula síncrona na sala virtual (revisão)
19/03 (15h30): PROVA 3:
Sistema de Avaliação (antes da prova final): Média = (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 (apenas capítulos 3,4,5,7 e 9) , 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.)
![[ada.png]](notes/extras/ada.png){kind=link}