INE 6010 - Teoria da Computacao (PPGCC)

• O exame de proficiência desta disciplina será realizado em 11/03/2010 das 14:00 às 16:00 horas no auditório do INE.
• O livro texto encontra-se disponível no CTC e na biblioteca universitária, que também dispõe de algumas das obras da bibliografia complementar. Sugiro fortemente consultarem, além do livro texto, sobre teoria da computação, ao menos Cormen e Dasgupta, sobre projeto e análise de algoritmos, da bibliografia complementar abaixo.

Programa

1. Conjuntos, Relações e Linguagens
2. Autômatos Finitos
3. Linguagens Livres de Contexto
4. Máquinas de Turing
5. Indecidibilidade
6. Complexidade Computacional
7. Completude NP
8. Tópicos em Projeto e Análise de Algoritmos

Livro texto

• Lewis, Harry R.; Papadimitriou, Christos H. Elementos de teoria da computação. 2a edição, Bookman, Porto Alegre, 2000. 344p. ISBN 85-7307-534-1.

Bibliografia Complementar

• Aho, A. V., Hopcroft, J. E., Ullman, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1975.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms.. Second Edition, MIT Press, 2001. 1184p.
• Dasgupta, S., Papadimitriou, C., Vazirani, U. Algorithms. McGraw-Hill, 2007. draft
• Garey, M. R.; Johnson, D. S. Computers and Intractibility: a Guide to the Theory of NP-Completeness. W.H.Freeman and Co., San Francisco, 1979. 340p.
• Gersting, Judith L. Fundamentos matemáticos para a ciência da computação. 5a edição, LTC, 2004. 538p.
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. Introduction to Automata Theory, Languages, and Computation. 2nd Edition, Addison Wesley, 2000. 521p.
• Levitin, A. V. Introduction to the Design and Analysis of Algorithms. 2nd Edition, Addison-Wesley, 2006, ISBN-13: 9780321358288, 592p.
• Manber, U. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
• Sipser, Michael Introduction to the Theory of Computation. PWS Publishing Company, 2005, ISBN 0-534-95097-3, 400p.

Links

• NP-Completude
  • P versus NP
  • Official problem description

Apuração do rendimento dos alunos

• Nota final   =   0,4 * Prova1   +   0,6 * Prova2
• Conceitos
• A: 9,0 <= Nota final <= 10
• B: 7,5 <= Nota final < 9,0
• C: 6,0 <= Nota final < 7,5
• E: 0,0 <= Nota final < 6,0
• Alunos com nota maior ou igual a 5 no exame de proficiência podem optar por ter conceito D (Dispensado)

Notas e conceitos

• Exame de proficiência
• Conceitos (D = dispensado)

Atendimento

• Segundas-feiras, das 17:00 às 19:00 horas, na sala INE-409.