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
• Programa
• Bibliografia
• Avaliação
• Datas importantes
• Notas Finais (com exame)
• Listas de Exercícios
• Trabalho

Notícias da última hora:

1. [15/03/2005] Disponibilizada a primeira lista de exercícios.
2. [31/03/2005] Disponibilizadas a segunda e terceira lista de exercícios.
3. [20/04/2005] Disponibilizada a quarta lista de exercícios.
4. [02/05/2005] Divulgada as notas da primeira prova.
5. [12/05/2005] Divulgado o enunciado do trabalho.
6. [24/05/2005] Disponibilizada a quinta lista de exercícios.
7. [04/06/2005] Disponibilizadas a sexta e a sétima lista de exercícios.
8. [16/06/2005] Fim da matéria. Não haverá mais aulas.
9. [22/06/2005] Último horário de atendimento: quinta-feira, dia 23/06/05, das 17:30h às 18:30h.
10. [22/06/2005] Informações sobre a última prova (P2):
    Os alunos estão autorizados a consultar na prova uma folha tamanho CARTA e ESCRITA DE PRÓPRIO PUNHO (frente e verso) contendo APENAS:
    • Enunciados de teoremas (corolários, lemas, proposições, etc) referentes à parte de Teoria de Números.
    • Fórmulas referentes à parte de Teoria de Números contidas nas transparências usadas em aula.
    • Os algorimos de Euclides, Euclides Estendido, Resolvedor de equações modulares lineares e Exponenciação modular.
    Note que, entre outras coisas, NÃO podem ser incluídos nesta folha:
    • Propriedades e Definições.
    • Outros algoritmos que não sejam aqueles especificados acima.
    • Demonstraçães de teoremas (corolários, lemas, proposiçães, etc).
    • Enunciados e soluçães de exercícios.
    • Nada referente à parte de algoritmos aproximados e heurísticas.
    • Diagramas e exemplos.
    As folhas descritas acima serão recolhidas junto com as provas. Elas devem conter, no alto da folha, nome, RA e turma do aluno. Folhas que não estejam de acordo com as regras especificadas acima serão retiradas do aluno durante a prova e consideradas como COLA (ver puniçães cabíveis no final desta página).
11. [30/06/2005] Avisos IMPORTANTES sobre o trabalho:
    1. Um erro foi encontrado nas respostas dos exemplos para o problema 2. Os arquivos já foram atualizados (veja os exemplos).
    2. Os modelos elaborados para cada problema devem imprimir todas as variáveis relavantes em relação a solução ótima calculada. Além disso todos os modelos devem necessariamente incluir a seguinte linha que imprime o valor da função objetivo:
       

       writeln("FO = ", strfmt(getobjval,1,2))

       A linha acima deve ser utilizada sem nenhuma modificação.
    3. Antes de submeter seu trabalho, teste-o com atenção!
    4. Serão desconsiderados (receberão nota zero) os trabalhos/modelos que se encaixem em qualquer um dos casos listados abaixo:
       • Modelos que apresentarem qualquer problema de execução (independente do trabalho escrito).
       • Modelos que fornecerem valor incorreto para a função objetivo nos exemplos divulgados para testes (01.dat e 02.dat em todas as questões).
       • Modelos que não atendam as especificação de entrada (modelo deve solicitar que o nome do arquivo de teste seja fornecido pelo usuário), saída (veja detalhes acima) e nome do arquivo mosel (raXXXXXX-1.mos, raXXXXXX-2.mos, raXXXXXX-3-a.mos, raXXXXXX-3-b.mos, raXXXXXX-4.mos).
       • Modelos desacompanhados do documento que os descreve. Este documento deve explicar todas as variáveis, restrições e a função objetivo usada no modelo (formato do documento: pdf, ps ou html).
       • Trabalhos recebidos após a meia-noite do dia 01/07/2005.
       • Trabalhos muito semelhantes a de outras duplas (neste caso será atrubuída nota zero no semestre para todos os envolvidos).
    5. Só serão aceitos trabalhos incompletos se todos os modelos entregues estiverem completos e acompanhados do documento que os descreve.
12. [03/07/2005] Divulgadas as notas finais.
13. [03/07/2005] Horário de atendimento especial: segunda-feira, 04/07/2005, das 17:15h às 18:15h.
14. [05/07/2005] Último horário de atendimento antes do exame: terça-feira, 05/07/2005, das 17:30h às 18:30h.
15. [09/07/2005] Instruções para os alunos que farão o exame:
    • Local, Data e Horário: Sala 85 do IC-2, dia 12/07/2005, às 19h.
    • Formato da folha de consulta para ser usada durante a prova: em papel tipo carta, com nome e RA no topo, escrita de próprio punho, podendo conter na frente e no verso quaisquer anotações exceto demonstrações e exercícios resolvidos.
    • Duração da prova: 110 minutos.
16. [13/07/2005] Divulgadas as notas finais após o exame.
17. [13/07/2005] Último horário atendimento do curso: quinta-feira, 14/07/2005, das 17:30h às 18:30h.

Docente:

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

Dias, Horários e Local das Aulas:

Terças às 19h e quintas às 21h na sala 85 do IC-2.

Dia, Horário e Local de Atendimento:

Terças-feiras, das 18h às 19h, na sala 23 do IC-1.
Não haverá atendimento em semana de prova.

Objetivos da Disciplina:

Um primeiro 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.

Um segundo objetivo é apresentar alguns algoritmos relacionados a problemas numéricos para os quais existem importantes aplicações na área de Computação e Engenharia. Este é o caso, por exemplo, dos algoritmos relacionados à Teoria dos Números que formam a base dos sistemas criptográficos atuais, como por exemplo o RSA.

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. Além disso, os alunos deverão ter adquirido o conhecimento teórico básico para entender o funcionamento de alguns algoritmos numéricos de grande importância prática.

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

Reduções entre problemas. Algoritmos não determinísticos. Classes de problemas: P, NP, NP-difícil e NP-completo. Teorema de Cook. Provas de NP-completude. Outras classes: co-NP, P-espaço e NP-espaço. Teorema de Savitch. Indecidibilidade: Problema da Parada. Tratamentos de problemas NP-completos/difíceis: algoritmos de backtracking e branch-and-bound. Modelagem e resolução de problemas NP-difíceis usando Programação Linear Inteira. Métodos heurísticos para problemas NP-difíceis. < Algoritmos aproximados: definições e exemplos. Existência de Algoritmos aproximados e a questão P=NP. Teoria dos Números e Introdução à Criptografia: o algoritmo de Euclides para o máximo divisor comum (MDC), o algoritmo estendido de Euclides para o MDC, aritmética modular, resolução de uma equação linear modular, Teorema Chinês do resto, exponenciação e exponenciação modular, sistemas criptográficos de chave pública e o método RSA, teste de primalidade de Miller-Rabin.

Bibliografia e material didático:

O material didático abaixo foi preparado pelo professor Cid Carvalho de Souza especialmente para esta disciplina. Deste material constam: cópias das transparências referentes à NP-completude, um guia de estudos sobre NP-completude para auxiliá-lo a encontrar na bibliografia listada a seguir uma discussão mais aprofundada sobre cada tópico discutido em sala de aula e uma cópia do conjunto de transparências referente à Teoria de Números.

1. Transparências das aulas de NP-completude
   Postscript, 1 por página (1.0M)
   Postscript, 2 por página (1.1M)
   PDF, 1 por página (618K)
2. Guia de estudo de NP-completude (em postscript, 69K)
3. Transparências das aulas de Teoria dos Números
   Postscript, 1 por página (606K)
   Postscript, 2 por página (531K)
   PDF, 1 por página (296K)
   

A seguir encontra-se a bibliografia de base desta disciplina com alguns comentários adicionados pelos docentes visando auxiliá-lo na escolha das obras a serem pesquisadas durante os seus estudos. Note que, além destes 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 e R.L.Rivest. Introduction to Algorithms. McGraw-Hill, 1990.
   Comentário: Livro básico do curso principalmente da parte de algoritmos numéricos (capítulo 31 da segunda edição ou 33 da primeira edição). Existe uma versão da segunda edição deste livro em português na biblioteca do IMECC.
2. 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.
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 (parte inicial do curso).
7. 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.
8. 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 mas tem esta versão em português.
9. 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.
10. N. Ziviani. Projeto de Algoritmos com implementaçõs em Pascal e C. 2a edição. Thomson. 2003.
    Comentário: Um livro recente em português sobre algoritmos. O último capítulo é uma referência para a primeira parte da disciplina.

Avaliação:

A avaliação será baseada nas notas de duas provas e de um trabalho denotadas respectivamente por P1, P2 e T. O trabalho será composto de tarefas de implementação e experimentação computacional de pequeno porte além da preparação de um documento sumário descrevendo o que foi realizado. O trabalho deverá ser efetuado por grupos de no maximo dois alunos. A média do semestre M será calculada da seguinte forma:

1. Calcule: A=(2*P1+2*P2+T)/5
2. Calcule: g=mínimo{P1,P2,T}
3. Se (A >= 5.0) e (g >= 3.0)
   então   M=A
   se não M=mínimo{A,4.9}

Sendo E a nota do exame, o cálculo da média final da disciplina (MF) será feito da seguinte forma:

1. Se (M >= 5.0) e (o aluno não compareceu ao exame) então MF=M.
2. Se não   MF=(M+E)/2
   Observação: neste caso, para efeitos de cálculo, se o aluno não comparecer ao exame o valor de E será igual a zero !

Se (MF >= 5.0) então o aluno APROVOU-SE. Caso contrário, ele REPROVOU-SE.

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 ou no trabalho implicará em média do semestre (M) ZERO para todos os envolvidos, sem prejuízo de outras sanções.
4. Qualquer tentativa de fraude no exame implicará em média final (MF) ZERO para todos os envolvidos, sem prejuízo de outras sanções.
5. Não será cobrada presença em sala de aula. Todos os alunos receberão 100% de presença, independente da nota final obtida (não será atribuido o conceito "Reprovado por Falta" em nenhum caso).

Datas Importantes:

• Calendário oficial da DAC: Visite esta página para saber quais as datas de alteração de matrícula, de trancamento de disciplinas e dos períodos sem atividade.
• 01/03/2005: início das aulas.
• 28/04/2005: primeira prova (P1).
• 05/05/2005: disponibilização do enunciado do trabalho (T) pelos professores.
• 30/06/2005: segunda prova (P2).
• 01/07/2005: data limite para entrega do trabalho.
• 12/07/2005: exame (E).
• 14/07/2005: divulgação dos resultados finais da disciplina.