MAC0430 Algoritmos e Complexidade de Computação
OBJETIVOS: Ensinar noções de complexidade, redução (polinomial) entre problemas, indecidibilidade e problemas completos em NP e PESPAÇO.
PROGRAMA: Noções de análise de algoritmos; pior caso; notação assintótica. Análise de alguns algoritmos de ordenação e busca vistos em disciplinas anteriores. Medidas de complexidade; modelos subjacentes de computador. Tese de Church. Redutibilidade e problemas indecidíveis. Não-determinismo versus determinismo. Fórmulas do cálculo proposicional. Redutibilidade e problemas NP-completos. Hierarquia polinomial de complexidade. Redutibilidade e problemas PESPAÇO-completos.
PRÉ-REQUISITO NÃO-OFICIAL: MAC0338.
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:
- C.H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
- 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.
- C.L. Lucchesi et alii, Aspectos Teóricos de Computação (parte B), IMPA, 1979.
- R. Terada, Desenvolvimento de Algoritmos e Estruturas de Dados, McGraw-Hill, 1991.
OBSERVAÇÃO: Disciplina optativa eletiva no currículo do BCC.
[Veja dados da disciplina no JúpiterWeb]