MAC0430  Algoritmos e Complexidade de Computação

OBJETIVOS:  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:  MAC0338e 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]