Introdução à Teoria da Computação (CI1059)
Professor: Nicollas Mocelin Sdroievski
Para entrar em contato comigo, envie um e-mail para nmsdroievski[arroba]ufpr.br
Horário das aulas:
- Terça-feira 15h30-17h30
- Quinta-feira 15h30-17h30
Horário de antendimento quintas-feiras 14:30 - 15:30 ou a combinar (com agendamento)
Local das aulas:
- PC-07
Datas importantes
4/8: Não haverá aula
6/8: Não haverá aula
11/8: Início das aulas
8/9: Não haverá aula (Padroeira de Curitiba)
15/9: Não haverá aula (semana acadêmica)
17/9: Não haverá aula (semana acadêmica)
22/9: Prova 1
29/10: Prova 2
1/12: Prova 3
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
Primeira lista de exercícios: (aqui)
Slides da disciplina: (aqui)
Página do professor Murilo: (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