Introdução à Teoria da Computação
(Período Especial - Ciclo 3)
Professor Murilo V. G. da Silva
Sala Virtual: [Link para sala do Google Meet]
Data da primeira prova: 02/09
Data da segunda prova: 21/09
Data da prova final: 25/09
10/08 (18h30): Aula Remota de 1 hora
10/08 (19h30): Vídeo Liberado em: [link p/ Playlist de vídeos]
10/08 (19h30): Ler [SIL17: cap. 1 e 2] [SIP06: cap. 0] [HMU01: 1.5]
12/08 (19h30): Vídeo Liberado em: [link p/ Playlist de vídeos]
12/08 (19h30): Ler [SIL17: sec. 3.1] [SIP06: 1.1] [HMU01: 2.1-2]
14/08 (16h00): Aula Remota de 2 horas
17/08 (19h30): Vídeo Liberado em: [link p/ Playlist de vídeos]
17/08 (19h30): Ler [SIL17: 3.2.1-3] [HMU01: 2.3.1-4]
19/08 (19h30): Ler [SIL17: 3.3-5] [SIP06: 1.2] [HMU01: 2.3.5, 2.5]
24/08 (07h00): Vídeo Liberado em: [link p/ Playlist de vídeos]
24/08 (18h00): Aula Remota de 2 horas
26/08 (19h30): Ler [SIL17: 3.6] [SIP06: 1.3] [HMU01: 3.1-2]
27/08 (19h30): Vídeo Liberado em: [link p/ Playlist de vídeos]
28/08 (19h30): Ler [SIL17: 4.1] [SIP06: 1.4] [HMU01: 4.1]
31/08 (18h00): Aula Remota de 2 horas
02/09 (16h00): Prova 1
03/09 (19h30): Ler [SIL17: 4.2] [SIP06: 2.2] [HMU01: 6.1-2]
08/09 (19h30): Ler [SIL17: 4.3] [SIP06: 2.1] [HMU01: 5.1-2]
09/09 (19h30): Ler [SIL17: cap. 5] [SIP06: 3.1-2] [HMU01: 8.1-4]
11/09 (16h00): Aula Remota de 1 hora
14/09 (19h30): Vídeo Liberado em: [link p/ Playlist de vídeos]
14/09 (19h30): Ler [SIL17: cap. 6]
16/09 (19h30): Ler [SIL17: cap. 7]
18/09 (16h00): Aula Remota de 1 hora
21/09 (18h00): Prova 2
IMPORTANTE: Não haverá encontro virtual neste dia.
O aluno deve apenas fazer o download da prova (no horário combinado, i.e., 18h00)
e enviar a mesma resolvida para o professor até 20h00.
[link p/ Prova 2] -- enviar para murilo@inf.ufpr.br até 20h00 do dia 21/09/2020
25/09 (16h00): Prova Final
Sistema de Avaliação (antes da prova final): Média = (P1 + P2) / 2
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}