MAC0430 Algoritmos e Complexidade de Computação
Por | EmOBJETIVOS: Ensinar noções de indecidibilidade, complexidade, redução (polinomial) entre problemas, e problemas completos em NP e PESPAÇO.
PROGRAMA: Modelos de computação; máquinas de Turing. Tese de Church. Redutibilidade e problemas indecidíveis. Complexidade, problemas decidíveis em tempo polinomial. Não-determinismo versus determinismo. Redutibilidade e problemas NP-completos. Hierarquia polinomial de complexidade. Redutibilidade e problemas PESPAÇO-completos.
PRÉ-REQUISITO NÃO-OFICIAL: MAC0338 e MAC0414.
CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS: 4 horas, 4 créditos-aula.
CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM: Média ponderada de provas e exercícios.
BIBLIOGRAFIA BÁSICA:
- H.R. Lewis, C.H. Papadimitriou, Elementos de Teoria da Computação, 2nd ed., Bookman, 2000.
- M. Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997.
- D. Harel, Algorithmics (capítulos 7 e 8), Addison-Wesley, 1987.
- J. van Leeuwen, Handbook of Theoretical Computer Science (volume A, capítulo 2), MIT Press, 1990.
OBSERVAÇÃO: Disciplina optativa eletiva no currículo do BCC. Corresponde aos capítulos 4 a 7 do livro de Lewis e Papadimitriou.
[Veja dados da disciplina no JúpiterWeb]
Oferecimentos recentes da disciplina: 2002/1