[20/11/2013] Divulgado o esboço do exame. Favor consultar a planilha de notas 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.
Terças-feiras, das 17h às 18h, na sala 23 do IC-1.
Importante:
O atendimento deve ser confirmado, com no mínimo 24h e no máximo 48h de antecedência, por email. Você deve enviar uma mensagem com o subject/assunto “[MC448] Horário de Atendimento” confirmando sua intenção de usar o horário de atendimento no horário acima (único disponível). Você receberá um email confirmando o atendimento.
Só serão atendidos alunos que confirmarem o atendimento, de acordo com a regra acima.
Se você confirmou o interesse pelo horário de atendimento, você deve comparecer a sala indicada até no máximo às 17:30h. Após este horário, se não houver alunos, o atendimento será encerrado.
Se não houver nenhum atendimento confirmado, o horário estará cancelado.
Não haverá horário de atendimento na semana das provas ou do exame.
Não haverá atendimento de dúvidas por email.
Programa
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
Reduções entre problemas:
Para obtenção de cotas superiores
Para obtenção de cotas inferiores
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 quatro provas denotadas respectivamente por P1, P2, P3 e P4. Cada prova terá duração de 1:30h e será composta de duas questões.
Os seguintes tópicos serão avaliado em cada uma das provas.
Prova 1:
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
Prova 2:
Reduções entre problemas:
Para obtenção de cotas superiores
Para obtenção de cotas inferiores
Prova 3:
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
Prova 4:
Tratamento de Problemas NP-difíceis:
Programação Linear Inteira
Algoritmos exatos
Algoritmos aproximados
Algoritmos heurísticos
A nota final antes do exame (N) será calculada usando a seguinte fórmula:
N = (P1 + P2 + P3 + P4)/4
Se 2.5 ≤ N < 5, o aluno terá direito a fazer o exame.
A nota final da disciplina (F) após o exame (E) será calculada pela fórmula:
F = min{5, (N + E)/2}, se 2.5 ≤ N < 5 e o aluno fez o exame
F = N, caso contrário
Observações:
Não haverá provas ou exame substitutivos.
As provas e o exame serão realizados sem consulta a qualquer material.
Qualquer tentativa de fraude nas provas ou no exame resultará em média do semestre F = 0.0 (zero) para todos os envolvidos, sem prejuízo de outras sanções.
De acordo com a fórmula acima, caso um aluno seja aprovado após realizar o exame, sua nota final será F = 5.0 (cinco).
O exame terá duração de 2 horas e será composto por 4 questões, sendo que cada questão cobrirá um tópico de uma das provas.
Todas as provas e o exame serão realizados na sala 322 do IC-3.
Após corrigidas, as provas estarão disponíveis para consulta apenas nos dias e horários divulgados junto com as notas das provas.