Conteúdo desta página:

• Notícias da última hora
• Docente
• Dias, Horários e Local das Aulas
• Dia, Horário e Local de Atendimento
• Objetivos da Disciplina
• Ementa da Disciplina
• Programa da Disciplina
• Bibliografia
• Material Didático
• Avaliação
• Datas importantes
• Notas
• Trabalho
• Listas de Exercícios

Notícias da última hora:

1. [15/07/2012] Divulgadas as notas do exame.
2. [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.
3. [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.
4. [19/06/2012] Divulgadas as notas da Terceira Prova.
5. [18/06/2012] Divulgadas as notas do trabalho prático.
6. [12/06/2012] Horário de atendimento extra: sexta-feira, dia 15 de junho de 2012, das 17:30h às 19h, na sala 23 do IC.
7. [11/06/2012] Divulgada a lista de exercícios de Heurísticas e de Algoritmos de Aproximação .
8. [11/06/2012] Divulgado o material didático de Algoritmos de Aproximação.
9. [05/06/2012] Divulgada a lista de exercícios de Branch & Bound e de Programação Linear Inteira.
10. [05/06/2012] Divulgado o material didático de Heurísticas.
11. [31/05/2012] Enunciado do Problema 3 do Trabalho Prático foi levemente modificado (vide último parágrafo acrescentado à descrição do problema).
12. [30/05/2012] Divulgado o material didático de Branch & Bound.
13. [23/05/2012] Divulgado o material didático de Programação Linear Inteira .
14. [23/05/2012] Divulgado o enunciado do Trabalho Prático.
15. [13/05/2012] A segunda prova estará disponível para consulta no horário de atendimento dos dias 21 e 28 de maio de 2012.
16. [17/05/2012] Divulgadas as notas da Segunda Prova.
17. [02/05/2012] Divulgadas as listas de exercícios de Classes de Problemas.
18. [02/05/2012] Atualizado o material didático de Classes de Problemas.
19. [19/04/2012] Divulgado o material didático de Classes de Problemas.
20. [13/04/2012] A primeira prova estará disponível para consulta no horário de atendimento dos dias 16 e 23 de abril de 2012.
21. [13/04/2012] Divulgadas as notas da Primeira Prova.
22. [28/03/2012] Divulgado o material didático de Reduções entre Problemas.
23. [26/03/2012] Divulgadas as listas de exercícios de Programação Linear e de Reduções entre Problemas.
24. [14/03/2012] Divulgado o material didático de Programação Linear.
25. [06/01/2012] Página da disciplina no ar.

Docente:

Zanoni Dias
Sala: 23 (IC-1)
Email: zanoni@ic.unicamp.br

Dias, Horários e Local das Aulas:

Segundas-feiras às 19h e quartas-feiras às 21h, no CB-08.

Dia, Horário 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

Bibliografia:

A seguir encontra-se a bibliografia de base desta disciplina com alguns comentários visando auxiliá-lo na escolha 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.

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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).
8. 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.
9. 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.
10. 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.
11. 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.

Material didático:

• Programação Linear: aula 1, aula 2, aula 3, aula 4 e aula 5.
• Reduções entre Problemas.
• Classes de Problemas.
• Branch & Bound e Programação Linear Inteira.
• Heurísticas e Algoritmos de Aproximação.

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 = (3P1 + 3P2 + 2P3 + 2T)/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:

1. Não haverá provas substitutivas.
2. Todas as provas realizadas durante o semestre e o exame final serão realizados sem consulta.
3. 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.
4. Não será cobrada presença em sala de aula.

Datas Importantes:

• 29/02/2012 (quarta-feira): Primeira aula.
• 09/04/2012 (segunda-feira): Primeira prova (P1).
• 23/04/2012 (segunda-feira): Data limite para divulgação das notas da primeira prova (P1).
• 02/05/2012 (quarta-feira): Data limite para desistência de matrícula em disciplinas do primeiro semestre de 2012.
• 14/05/2012 (segunda-feira): Segunda prova (P2).
• 23/05/2012 (quarta-feira): Divulgação do enunciado do trabalho prático (T).
• 28/05/2012 (segunda-feira): Data limite para divulgação das notas da segunda prova (P2).
• 17/06/2012 (domingo): Data limite para a entrega do trabalho prático (T).
• 18/06/2012 (segunda-feira): Terceira prova (P3).
• 25/06/2012 (segunda-feira): Data limite para entrega das notas terceira prova (P3) e do trabalho prático (T).
• 11/07/2012 (quarta-feira): Exame (E).
• 17/07/2012 (terça-feira): Data limite para divulgação das notas do exame (E).