Complexidade Computacional - 2002

• Critério de avaliação

  Haverão três provas e várias listas de exercícios.

  Data das provas

  • Prova 1: 19/4
  • Prova 2: 24/5
  • Prova 3: 28/6

  A média de provas é MP = (P₁ + P₂ + 2P₃)/4.

  Denotando por ML a média aritmética das notas obtidas nas listas de exercícios, um aluno, para ser aprovado, deverá ter média pelo menos 5.0 de prova e de listas. Haverá também uma nota implícita por participação em aula, na lista de discussão, etc.

  A média das provas terá peso 60% na nota final enquanto que a média de listas terá peso de 30%. Os 10% finais dependerão da participação do aluno na disciplina.

• Bibliografia

  O livro texto é o seguinte

  C. Papadimitriou, Computational Complexity, Reading, Mass., Addison-Wesley, 1994. [QA810 P213c]

  Além deste, o aluno interessado pode consultar também os seguintes textos

  1. A.V. Aho, J.E. Hopcroft, and J.D. Ullman, Data structures and algorithms, Reading, Mass., Addison-Wesley, 1983. [QA758 A286d]
  2. J.E. Hopcroft and J.D. Ullman, Formal languages and their relation to automata, Reading, Mass., Addison-Wesley, 1969. [QA806 H791f]
  3. M.R. Garey and D.S. Johnson, Computers and intractability :a guide to the theory of NP-completeness, San Francisco, W.H. Freeman, 1979. [QA810 G229c]