Instituto de Computação - UNICAMP

Novidades: Consulte esta seção freqüentemente.

1. Média Final.
   Food for thought:
   
   Dos 18 alunos inscritos até o final do semestre, 7 abandonaram a disciplina (deixaram de fazer a segunda prova e 3 dos 4 trabalhos práticos).
   Dos 11 restantes, 9 aprovaram-se e a média das médias finais destes alunos foi 7.8.
   [15/07/2019]
2. Disponibilizadas as médias do semestre e relação de alunos em exame.
   [01/07/2019]
3. Veja o relatório completo da correção do TP4 preparado pelo PED.
   Observação: você tem até terça-feira, 2/7, para solicitar revisão da sua nota, o que pode ser agendado por email com o PED.
   [01/07/2019]
4. Disponibilizadas as notas da P2.
   Observação: a revisão da prova só poderá ser feita nesta quinta-feira, 27/6, na sala 322 do IC3 às 16 horas.
   [27/06/2019]
5. Veja o relatório completo da correção do TP3 preparado pelo PED.
   Nota: de acordo com as regras da disciplina, você tem até quarta-feira, 26/6, para solicitar revisão da sua nota, o que pode ser agendado por email com o PED.
   [19/06/2019]
6. Slides referentes à última aula sobre algoritmos aproximados: α-aproximações usando programação linear e esquemas de aproximação
   Nota: alguns destes slides foram gentilmente cedidos pelo Prof. Flávio Miyazawa. Abaixo uma referência para o estudo deste último tópico.

   Tópico:	Referências (para ver a numeração siga o link acima)	Páginas
   Esquemas de Aproximação (Completamente) Polinomiais [PTAS e FPTAS]	[3]	429-427

   
   [18/06/2019]

7. Guia de estudos para o material sobre algoritmos aproximados visto em aula até esta data:
   

   Tópico:	Referências (para ver a numeração siga o link acima)	Páginas
   Algoritmos Aproximados (aproximação absoluta, relativa, questão P×NP)	[4]	559--577
   α-aproximações para o TSP métrico	[3]	411-418

   
   [13/06/2019]

8. Slides referentes às duas primeiras aulas sobre algoritmos aproximados: aproximações absolutas e α-aproximações
   Nota: alguns destes slides foram gentilmente cedidos pelo Prof. Flávio Miyazawa.
   [13/06/2019]
9. Disponibilizadas listas sobre algoritmos aproximados:
   1. Algoritmos Aproximados (preparada pelo docente)
   2. Algoritmos Aproximados (gentilmente disponibilizada pelo Prof. Eduardo Xavier)
   [11/06/2019]
10. Avisos importantes:
    • Todas as aulas restantes do semestre (dias 6, 11, 13, 18 e 30 de junho) serão dadas na sala 322 do IC3.
    • Nas aulas teóricas dos dias 6, 11, 13 e 18 de junho, a simples presença em aula acarretará em um acréscimo de 0.25 pontos na nota da P2. Além disso, ao final destas 4 aulas, será feito um pequeno teste (não mais de duas perguntas) de 10 minutos de duração que, se respondidos corretamente darão, cada um, um adicional de 0.25 pontos na nota da P2 também. Ou seja, nestas 4 últimas aulas você estará concorrendo à 2 pontos de acréscimo na nota da P2.
    • Para uma leitura adicional sobre relaxação lagrangiana, sugere-se a leitura do capítulo 10 da seguinte obra: L. Wolsey. Integer Programming. Wiley-Interscience. 1998. . Este livro está disponível em algumas bibliotecas da UNICAMP (sem reserva, acho).
      Sugestão de exercícios de relaxação lagrangiana: resolva os seguintes exercicios do Capítulo 10 do livro citado acima: 1, 2, 3, 4, 5, 6, 7 e 8.
    [05/06/2019]
11. Informações sobre o TP4:
    • Todas as implementações devem ser feitas em liguagem C ou C++
    • Baixe aqui uma cópia do artigo cuja referência encontra-se abaixo. Ele será essencial para uma boa implementação da relaxação lagrangiana.
      Sugere-se fortemente que você leia este artigo até a seção 6.5.2 inclusive.
      
      J. E. Beasley. Lagrangian relaxation.
      In C. R. Reeves, editor, Modern Heuristic Techniques for Combinatorial Problems,
      capítulo 6, páginas 243--303. John Wiley & Sons, Inc.,
      New York, NY, USA, 1993.
      
      Para abrir o arquivo, você vai ter que usar a senha enviada por email. Cuidado: este artigo é protegido por direitos autorais. Assim, sua cópia deve ser exclusivamente para seu uso pessoal!
    [03/06/2019]
12. Slides referentes à terceira aula sobre relaxação lagrangiana podem ser baixados aqui
    [03/06/2019]
13. Disponibilizados o enunciado e as instâncias de teste do TP4.
    Os grupos para realização do TP4 são os mesmos do TP3.
    [30/05/2019]
14. Slides referentes à segunda aula sobre relaxação lagrangiana podem ser baixados aqui
    [30/05/2019]
15. Slides referentes à primeira aula sobre relaxação lagrangiana podem ser baixados aqui.
    [29/05/2019]
16. Novos slides referentes às aulas sobre heurísticas: busca tabu e grasp
    Nota: estes slides foram gentilmente cedidos pelo Prof. Flávio Miyazawa.
    [24/05/2019]
17. Disponibilizado o conjunto completo das instâncias de teste do TP3.
    [18/05/2019]
18. Disponibilizadas as notas do TP2. Veja o relatório completo da correção dos trabalhos preparado pelo PED.
    Veja também o gráfico de distribuição das notas do trabalho.
    Nota: de acordo com as regras da disciplina, você tem até terça-feira, 21/5, para solicitar revisão da sua nota, o que pode ser agendado por email com o PED.
    [18/05/2019]
19. Slides referentes às aulas sobre heurísticas: conceitos básicos (heurísticas construtivas e de busca local e simulated annealing
    Nota: parte significativa destes slides foram gentilmente cedidos pelo Prof. Flávio Miyazawa.
    [18/05/2019]
20. Disponibilizado o enunciado do TP3 que deverá ser entregue até o dia 30/05/2019. Por enquanto, estão liberados os arquivos de entrada correspondentes a duas instâncias:
    • 3o7jAL18.dzn: instância do exemplo do enunciado
    • 4o24jAL18.dzn: instância real disponibilizada pela indústria e parte do benchmark de teste
    Até o dia 21/05, próxima terça, as demais instâncias do benchmark poderão ser baixadas nesta página.
    

    Grupos para o TP3:

    • ATENÇÃO! Aconteceram pequenas alterações na formação dos grupos em relação ao TP2. Confira!
    • Se o seu RA não consta de nenhum grupo, entre em contato urgente com o docente da disciplina.
       

    grupo	RA dos integrantes
    01	156059 156074
    02	187890 188115
    03	171119 176665
    04	167236 176848
    05	170013 184403
    06	138309 150630
    07	90996 148246
    08	171509 135680
    09	118607 157065

    
    [14/05/2019]
21. Material usado nas aulas sobre programação por restrições:
    • slides (cuidado: parte deste material é coberto por direitos autorais; usar senha distribuída pelo docente)
    • códigos do Minizinc e arquivos de entrada
    Algumas páginas interessantes (além daquelas já indicadas nos slides):
    • Tutorial do MiniZinc (versão 2.2.3)
    • Códigos do tutorial do Minizinc
    • Curso do Coursera sobre modelagem básica com Minizinc
    [14/05/2019]
22. Baixe aqui o código do Minizinc para o jobshop scheduling problem visto na aula de ontem.
    [07/05/2019]
23. Disponibilizadas as notas da P1.
    Veja gráfico de distribuição das notas da prova.
    Nota: de acordo com as regras da disciplina, você tem até sexta-feira, 3/5, para solicitar revisão da sua nota, o que pode ser agendado por email. Você poderá ver pessoalmente sua prova amanhã, após a aula.
    [01/05/2019]
24. Disponibilizadas as notas do 1º trabalho prático. Veja o relatório completo da correção dos trabalhos preparado pelo PED.
    Veja gráfico de distribuição das notas do trabalho.
    [30/04/2019]
25. URGENTE!!!
    Hoje não haverá aula em virtude da suspensão das atividades acadêmicas no campus em decorrência de uma pane elétrica no Restaurante Universitário (RU). Veja o anúncio oficial na página da UNICAMP.
    [30/04/2019]
26. Divulgado o enunciado do 2 º trabalho prático. Fique atento à data de entrega (07/05) e à nova formação dos grupos (houve mudanças!!!).
    [23/04/2019]
27. Leia a folha de instruções da P1
    [15/04/2019]
28. Disponibilizados os exemplos de modelos em Julia usados em sala de aula.
    Nota: para rodar estes modelos, não esqueça de selecionar corretamente no código o resolvedor (CPLEX ou Gurobi) que você quer usar.
    [12/04/2019]
29. Sobre a entrega do TP1, a seguinte mensagem foi enviada a todos os alunos:

       Alguns alunos me procuraram para saber se podiam entregar o TP1 com
       atraso.
    
       Darei uma tolerância até sábado. Porém, a cada dia de atraso haverá
       um decréscimo  na nota, o qual  será decido a posteriori,  tendo em
       vista que  a solicitação só foi  feita na data de  hoje!  Portanto,
       após as  24:00 horas deste  sábado, dia 13/4, nenhum  trabalho será
       mais recebido.
    
       Observação: via de  regra, o quanto antes o  trabalho for entregue,
       mesmo que contendo alguns erros, melhor!

    [11/04/2019]
    
    
30. Baixe a planilha do gnumeric corrigida para o problema do flowshop.
    Desafio (ainda valendo 2×10^-37 na média): descreva uma estratégia para encontrar o erro na planilha do flowshop usada em aula.
    Dica: lembre que nós conhecíamos uma solução viável com valor melhor que aquela retornada pelo solver da planilha. Como isso pode nos ajudar a encontrar o erro? :)

    As planilhas para sua análise podem ser baixadas clicando nos links apropriados ao lado:   planilha corrigida   planilha com erro (usada em aula)

    Note que o arquivo com a descrição do modelo sofreu pequenas correções de digitação. Você pode baixá-lo novamente aqui
    [05/04/2019]

31. A tabela abaixo serve de guia de estudos para o tópico Programação Linear Inteira.
    

    Tópico:	Referências (para ver a numeração siga o link acima)	Páginas
    PLI	[7]+[8]	capítulos (incluindo exercícios) sobre modelagem usando PLI
    	[9]	38--39

    
    [04/04/2019]

32. Disponibilizada a lista de exercícios de formulações usando PLI e matrizes TU
    [04/04/2019]
33. Exemplos de planilhas eletrônicas na resolução de problemas NP-difíceis (aulas 9 e 10):
    • cobertura de vértices mínima de um grafo
    • clique máxima de um grafo
    • flowshop em duas máquinas (descrição do modelo implementado na planilha)
    [03/04/2019]
34. Divulgada a lista dos grupos para o TP1. São 11 duplas e uma tripla (grupo 8). Os grupos de 1 a 7 foram formados conforme solicitação dos seus integrantes. Os demais tiveram os nomes de seus integrantes escolhidos aleatoriamente pelo docente.
    Não serão permitidas alterações na composição dos grupos!
    [31/03/2019]
35. Disponibilizado o enunciado do TP1 que deverá ser entregue até o dia 11/04/2019. Outros arquivos necessários para a preparação do trabalho são:
    • Descrição do algoritmo a ser implementado;
    • Conjunto das instâncias de teste;
    • Rotina de medição de tempo em C++/C.
    Os nomes dos integrantes das duplas que farão o trabalho devem ser informados via email enviado ao docente até esta 5ª-feira 28/03. Alunos que não tenham se manifestado até esta data serão alocados aleatoriamente pelo docente a duplas formadas pelo docente e tomarão conhecimento dos seus parceiros até o dia 02/04.
    [26/03/2019]
36. A tabela abaixo serve de guia de estudos para o material visto em aula até a data de hoje.
    

    Tópico:	Referências (para ver a numeração siga o link acima)	Páginas
    Programação Dinâmica	[1]	Capítulo 15
    Backtracking	[4]	323--369
    	[2]	358--361
    Branch-and-bound	[3]	438--448

    
    [21/03/2019]

37. Houve uma pequena alteração no tutorial preparado pelo PED para a instalação de pacotes essenciais para a realização de alguns trabalhos práticos. Considere baixá-lo novamente caso jã tenha realizado o download antes dessa desta.
    [21/03/2019]
38. Baixe aqui os slides sobre a breve revisão de programação linear e sobre modelagem usando programação linear inteira. (sexta a nona aula).
    [21/03/2019] (atualizado em [03/04/2019])
39. Disponibilizada a lista de exercícios de backtracking e branch-and-bound (algoritmos exatos - enumeração implícita)
    [21/03/2019]
40. Disponibilizada a lista de exercícios de programação dinâmica (algoritmos exatos pseudopolinomiais)
    [21/03/2019]
41. Baixe aqui os slides sobre algoritmos de branch-and-bound (quarta e quinta aula).
    [19/03/2019]
42. Baixe aqui os slides sobre algoritmos de backtracking (terceira e quarta aula).
    [15/03/2019]
43. Baixe aqui a planilha do gnumeric exemplificando o algoritmo de programação dinâmica para o problema da mochila binária com custos inteiros.
    [13/03/2019]
44. Baixe aqui o tutorial preparado pelo PED para a instalação de pacotes essenciais para a realização de alguns trabalhos práticos que serão propostos no semestre. Sugere-se fortemente que as instalações sejam feitas o quanto antes para que não haver problemas com prazo de entrega de trabalhos.. Fique atento para instalar as versões que serão usadas para corrigir os trabalhos.
    [13/03/2019]
45. Baixe aqui os slides sobre programação dinâmica e algoritmos pseudopolinomiais (segunda e terceira aula).
    [12/03/2019]
46. Definido o local e horário de atendimento do PED.
    [07/03/2019]
47. Baixe aqui os slides usados na primeira e segunda aulas.
    [07/03/2019]
48. Baixe aqui o plano de desenvolvimento da disciplina para o semestre.
    [07/03/2019]
49. Início das aulas.
    [28/02/2019]

Docente:

Cid Carvalho de Souza
Sala: 8 (Prédio IC1)
Email para contato: cid[at]ic[dot]unicamp[dot]br

PED: Natanael Ramos (naelr8[at]gmail[dot]com)

Dias e locais das aulas e do atendimento:

• aulas: as aulas serão das 16:00 às 18:00 horas nas 3ªs (sala CB05) e 5ªs (sala PB11).
• atendimentos do docente: às terças depois da aula ou em horário previamente combinado (solicitado por email enviado com pelo menos 72 horas de antecedência).
      O docente não dará atendimento em semana de prova ou exame.
• atendimento do PED: início a partir da terceira semana de aula em horário a ser definido.
  O atendimento será toda 5ª-feira das 18:00 às 18:50 no PB11 (sala de aula).
  O atendimento do PED será suspenso se: (i) nenhum aluno comparecer nos primeiros 15 minutos; ou (b) passados os 15 minutos iniciais, a fila de espera por atendimento tiver se esgotado; ou (c) o horário de término do atendimento tiver sido atingido.

Objetivos da Disciplina:

O objetivo desta disciplina é complementar a formação dos alunos na área de algoritmos, introduzindo técnicas para lidar com problemas NP-difíceis, resolvendo-os de forma exata, heurística ou aproximada. Espera-se que ao final do semestre os alunos tenham adquirido sólidos conhecimentos sobre estas técnicas e sejam capazes de compreender as vantagens e as limitações de uso de cada uma delas.

Programa:  (em verde encontra-se o material já coberto)

Reduções e Classes de Problemas: revisão do conceito de reduções entre problemas e das definições das classes P, NP, NP-completo e NP-difícil. Algoritmos exatos para problemas NP-difíceis: algoritmos pseudo-polinomiais; algoritmos de backtracking; algoritmos de branch-and-bound; Programação Linear Inteira [PLI] (incluindo matrizes totalmente unimodulares) e Programação por Restrições [PR] como ferramentas para resolução de problemas NP-difíceis; Pacotes computacionais para resolver PLI e PR; Algoritmos heurísticos para problemas NP-difíceis: definições básicas: algoritmos construtivos e algoritmos de busca local; meta-heurísticas (simmulated annealing, busca tabu, algoritmos genéticos, GRASP); Relaxação Lagrangiana; Algoritmos aproximados definições básicas: aproximação absoluta; exemplos de aproximação absoluta; inaproximabilidade em aproximação absoluta; fator de aproximação (aproximação relativa); exemplos de fator de aproximação; inaproximabilidade em fator de aproximação; uso de PL no desenvolvimento de algoritmos aproximados; esquemas de aproximação polinomial (definição e exemplo);

Referências bibliográficas:

A seguir encontra-se a bibliografia de base da disciplina com alguns comentários adicionados pelo docente visando auxiliá-lo na escolha das obras a serem pesquisadas durante os seus estudos. Note que, além desses livros, existem nas bibliotecas da UNICAMP outras excelentes obras 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. 2nd Edition, McGraw-Hill, 2001.
   Comentário: Livro básico das disciplinas de algoritmos do IC.
2. U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley. 1989.
   Comentário: Outro livro básico das disciplinas de algoritmos do IC. O capítulo 10 trata exclusivamente sobre reduções entre problemas e bastante rico em exemplos. O mesmo pode ser dito a respeito do capítulo 11 sobre NP-completude.
3. 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.
4. 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.
5. M. Garey e D. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman. 1979.
   Comentário: Uma espécie de referência ``bíblica'' sobre a Teoria da Complexidade !
6. 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.
7. 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 PL e PLI.
8. M. Bazaraa, J. Jarvis e H. Sherali. Linear Programming and Network Flows. 2ª edição, John Wiley and Sons. 1990.
   Comentário: Uma boa fonte de consulta sobre PL e PLI.
9. L. Wolsey. Integer Programming. Wiley-Interscience. 1998.
   Comentário: Uma boa fonte de consulta sobre PLI.
10. M. H. Carvalho, M. R. Cerioli, R. Dahab, P. Feofiloff, C. G. Fernandes, C. E. Ferreira, K. S. Guimarães, F. K. Miyazawa, J. C. Pina Jr., J. Soares, Y. Wakabayashi,
    Uma Introdução Sucinta a Algoritmos de Aproximação,
    23º Colóquio Brasileiro de Matemática, 2001 (versão PDF, disponibilizada na página do Prof. Flávio Miyazawa).
    Comentário: Uma boa fonte de consulta sobre algoritmos aproximados.
11. M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
    Comentário: Uma excelente obra sobre Teoria da Computação onde tópicos cobertos nesta disciplina são vistos com um maior formalismo.
12. F.K. Miyazawa e C.C. de Souza, Introdução à Otimização Combinatória, Jornadas de Atualização em Informática - Congresso da Sociedade Brasileira de Computação - JAI-SBC, 2015. (versão pdf; ver capítulo 3).
    Comentário: uma obra recente em português que cobre bastante do conteúdo que é visto em MC658.

Material didático: Transparências usadas em aula serão disponibilizadas nesta seção, sempre que possível, antes da data de seu uso efetivo.

Avaliação:

A avaliação será baseada nas notas de duas provas (P1 e P2), nas notas de trabalhos práticos (TPs) que serão passados ao longo do semestre.

Nenhuma destas atividades valendo nota será antecipada por solicitação de um aluno ou terá substitutiva. Sem exceções.

A partir destas avaliações, as notas do semestre e final serão calculadas da seguinte forma:

• Média ponderada dos trabalhos práticos: MT = (W1×T1+W2×T2+...+Wn×Tn)/(W1+W2+...+Wn),
  onde 3 ≤ n ≤ 5 e Wi é o peso do trabalho i podendo ser 1, 2 ou 3 dependendo do grau de dificuldade do trabalho.
• Média geométrica das provas: MP= √ P1× P2 
• Média do semestre: (* antes do exame *)
  se MP≥ 5.0 e MT≥ 5.0 então MS = (7×MP+3×MT)/10
  se não MS = min { 4.9, (7×MP+3×MT)/10 }
  Observações: se MS < 2.5 ou MS ≥ 5.0, o aluno estará impedido de fazer o exame.
  
• Média final: (* após o exame *)
  se o aluno fez o exame então
  • MF = min { 5.0, (MS+E)/2 }
  se não (* aluno não fez exame *)
  • se MS < 2.5 ou MS≥ 5.0 então MF = MS (* aluno impedido de fazer o exame *)
  • se não MF = MS/2 (* aluno deveria ter feito o exame, mas não fez *)
• Resultado final:
  se o aluno não teve a frequência mínima então ele REPROVOU-SE por falta
  se não
  • se MF≥ 5.0 então o aluno APROVOU-SE
  • se não o aluno REPROVOU-SE por nota

Sobre os trabalhos práticos:

Alguns trabalhos práticos terão de ser feitos individualmente enquanto outros deverão ser feitos em grupos de 2 (excepcionalmente 3) alunos. Neles serão propostos problemas NP-difíceis que deverão ser tratados com uso das técnicas vistas na disciplina. A entrega dos trabalhos consistirá de código e de um relatório de análise de resultados em formato a ser divulgado oportunamente. O prazo para execução dos trabalhos poderá variar entre uma e três semanas, dependendo do grau de dificuldade dos mesmos.

Observações:

1. Não haverá provas ou trabalhos substitutivos.
2. Todas as provas realizados durante o semestre, bem como o exame final, serão sem consulta.
3. Qualquer tentativa de fraude nas provas, no exame ou nos trabalhos práticos implicará em média final (MF) igual a ZERO para todos os envolvidos, sem prejuízo de outras sanções.
4. Qualquer pedido de revisão da nota atribuída a uma avaliação realizada durante o semestre deverá ser feito em no máximo 2 dias (úteis) contados a partir da data de divulgação dos resultados daquela avaliação. No caso do exame, este prazo será de 24 horas. Solicitações que não atendam a esta exigência serão automaticamente negadas pelo docente.

Listas de exercícios:

Ao longo do semestre serão propostas listas de exercícios que deverão ser feitas para uma maior fixação dos tópicos apresentados em classe. O conteúdo dos exercícios é considerado parte integrante do material visto e tratado como parte coberta da matéria. A entrega deles não será cobrada. Entretanto, para o bom aprendizado da disciplina é necessário que cada aluno tente fazer os exercícios individualmente e só depois discutí-los em grupo. Dúvidas ou dificuldades devem ser discutidas com o docente ou com o PED.

Datas Importantes:

• Calendário oficial da DAC . Visite esta página para saber quais as datas de alteração de matrícula, desistência de disciplinas e dos períodos sem atividade.
• 28/02 (qui): início das aulas.
• 16/04 (ter): primeira prova (P1).
• 21/05 (ter): reunião de avaliação de cursos. Só não haverá aula se houver coincidência de horário.
• 25/06 (ter): segunda prova (P2).
• 11/07 (qui): exame (E).

Observação: as datas de divulgação do enunciado, disponibilização de dados de entrada e de entrega dos códigos e relatórios referentes aos trabalhos práticos serão divulgadas oportunamente e com a antecedência devida no correr do semestre.