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]