[25/06/2012] Divulgado o esboço do exame com a distribuição das questões e os pesos de cada questão. Favor consultar a planilha de notas, aba “exame”, para verificar qual a nota que será atribuída para cada questão, caso o aluno indique no exame que a questão não deva ser corrigida, usando neste caso notas previamente obtidas durante o semestre, conforme especificado no rodapé de cada questão.
[19/06/2012] O último horário de atendimento do semestre será no dia 25 de junho de 2012 (segunda-feira), das 17:30h às 19h, na sala 23 do IC.
Segundas-feiras às 19h e quartas-feiras às 21h, no CB-08.
Dias, Horários e Local de Atendimento
Segundas-feiras, das 18:00h às 18:45h, na sala 23 do IC-1.
Não haverá atendimento em dia de prova.
O horário de atendimento será encerrado caso não haja procura até às 18:30h.
Objetivos da Disciplina:
O objetivo desta disciplina é complementar a formação dos alunos na área de algoritmos introduzindo os conceitos de classes de complexidade de problemas. Com isso será possível entender porque é difícil encontrar bons algoritmos para resolução de certos problemas. Em particular, serão estudadas as classes dos problemas NP-completos e NP-difíceis que são freqüentemente encontrados em situações práticas. Será dada ênfase às técnicas que permitem mostrar que um determinado problema pertence uma destas classes e às alternativas que permitem resolvê-lo de forma exata ou aproximada.
Espera-se que, ao final do semestre, os alunos entendam o conceito de NP-completude e conheçam, não só as técnicas que permitam a identificação de um problema como estando nesta classe, mas também as formas alternativas para tratá-lo e as limitações de cada uma delas.
Ementa:
Redução entre problemas. Complexidade computacional. Classes de problemas. Problemas NP-completos. Tratamento de Problemas NP-difíceis.
Programa
Reduções entre problemas:
Para obtenção de cotas superiores
Para obtenção de cotas inferiores
Programação Linear:
Formulação de problemas como Programação Linear
Apresentação resumida do algoritmo SIMPLEX e de sua complexidade
Dualidade em programação linear
Classes de Problemas:
A hierarquia de Complexidade: as classes P, NP, NP-completo e NP-difícil
A noção de completude e o Teorema de Cook
Problemas e reduções fundamentais em NP-completude
Outras classes: co-NP, PSPACE e problemas indecidíveis
Tratamento de Problemas NP-difíceis:
Programação Linear Inteira
Algoritmos exatos
Algoritmos aproximados
Algoritmos heurísticos
Referências Bibliográficas
A seguir encontra-se a bibliografia de base desta disciplina com alguns comentários visando auxiliá-lo na escola dos livros a serem pesquisadas durante os seus estudos. Note que, além destes livros, existem nas bibliotecas da UNICAMP outras boas referências sobre os assuntos que serão vistos em sala de aula.
T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein. Introduction to Algorithms (Third Edition). The MIT Press, 2009. Comentário: Livro básico de análise de algoritmos.
T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein. Algoritmos - Teoria e Prática. Editora Campus, 2002. Comentário: Versão em português, da segunda versão da referência anterior.
U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989. Comentário: O capítulo 10 trata exclusivamente sobre reduções entre problemas e é uma ótima referência para o curso. O mesmo pode ser dito a respeito do capítulo 11 sobre NP-completude.
C. H. Papadimitriou e K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc., 1982. Comentário: Uma boa fonte de referência na parte de NP-completude, principalmente para explicar as técnicas de branch-and-bound e apresentar os conceitos básicos de algoritmos aproximados.
E. Horowitz e S. Sahni. Fundamentals of Computer Algorithms. Computer Science Press, 1978. Comentário: Outra boa fonte de referência para NP-completude, algoritmos aproximados, algoritmos de branch-and-bound e backtracking.
M. Garey e D. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, 1979. Comentário: Referência clássica sobre a Teoria da Complexidade.
P. J. de Rezende e J. Stolfi. Fundamentos de geometria computacional. Universidade Federal de Pernambuco, Departamento de Informatica, 1994. IX Escola de Computação, Recife, 24 a 31 de julho de 1994. Comentário: Uma boa leitura sobre reduções entre problemas (parte inicial do curso).
M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997. Comentário: Este livro é muito bem escrito e aborda de forma bem mais aprofundada vários tópicos que são vistos na disciplina.
H.R. Lewis e C.H. Papadimitriou. Elementos de Teoria da Computação. Bookman. 2a edição, 2000. Comentário: No mesmo nível do livro acima, porém em português.
M.C. Goldbarg e H.P.L. Luna. Otimização Combinatória e Programação Linear: modelos e algoritmos. Editora Campus, 2000. Comentário: Uma boa fonte de consulta em português sobre formulação de problemas usando PLI.
N. Ziviani. Projeto de Algoritmos com implementações em Pascal e C (3a edição). Thomson, 2010. Comentário: Um livro recente em português sobre algoritmos. O Capítulo 9 é uma boa referência complementar.
Branch & Bound + Programação Linear Inteira (Lista 4) (PDF).
Heurísticas + Algoritmos de Aproximação (Lista 5) (PDF).
Avaliação
A avaliação será baseada nas notas de três provas e de um trabalho denotados, respectivamente, por P1, P2, P3 e T. O trabalho será composto de tarefas de implementação e experimentação computacional além da preparação de um documento sumário descrevendo o que foi realizado.
A média final do semestre (MF) será calculada da seguinte forma:
Seja M = (3*P1 + 3*P2 + 2*P3 + 2*T)/10
Se (M ≥ 5.0) ou (M < 2.5) então MF = M
caso contrário:
Se o aluno não compareceu ao exame então MF = M
caso contrário, MF = (M+E)/2
Observações:
Não haverá provas substitutivas.
Todas as provas realizadas durante o semestre e o exame final serão realizados sem consulta.
Qualquer tentativa de fraude nas provas, no exame ou no trabalho implicará em média final do semestre MF = 0 (ZERO) para todos os envolvidos, sem prejuízo de outras sanções.