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 e Material Didático
• Avaliação
• Datas importantes
• Notas
• Listas de Exercícios
• Trabalho

Notícias da última hora:

1. [02/07/2006] Divulgadas as notas da segunda prova.
2. [23/06/2006] De acordo com a resolução do Magnífico Reitor, a prova final marcada para o dia 27/06/06, às 19h, foi adiada para o dia 29/06/06, às 21h.
3. [21/06/2006] Haverá um horário atendimento extra na sexta-feira, dia 23/06/2006, das 18:00h às 19:30h, na sala 23 do IC-01.
4. [20/06/2006] Divulgada a quinta e sexta lista de exercícios (veja aqui).
5. [18/06/2006] Divulgadas as notas do trabalho
6. [11/06/2006] Divulgada a quinta lista de exercícios (veja aqui).
7. [11/05/2006] Divulgado o enunciado do trabalho.
8. [07/05/2006] Divulgadas as notas da primeira prova
9. [25/04/2006] Divulgada a quarta lista de exercícios (veja aqui).
10. [06/04/2006] Divulgada a terceira lista de exercícios (veja aqui).
11. [28/03/2006] Divulgada a segunda lista de exercícios (veja aqui).
12. [18/03/2006] Divulgada a primeira lista de exercícios (veja aqui).

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 CB01.

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 transparência por página
   PDF, 1 transparência por página
2. Guia de estudo de NP-completude (Postscript)
3. Transparências das aulas de Teoria dos Números
   Postscript, 1 transparência por página
   Postscript, 2 transparências por página
   PDF, 1 transparência por página
   

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 individualmente.

A média do semestre M será calculada da seguinte forma:

1. Calcule: A = (2*P1+2*P2+T)/5
2. Calcule: P = (P1+P2)/2
3. Se (A ≥ 5.0) e (P ≥ 5.0)
   então M = A
   senão M = mínimo{A,P}

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

1. Se o aluno não compareceu ao exame então MF = M.
2. Caso contrário, MF = (M+E)/2
   

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, 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. 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.
• 07/03/2005: início das aulas.
• 02/05/2006: Primeira prova (P1).
• 09/05/2006: Disponibilização do enunciado do trabalho.
• 13/06/2006: Data limite para entrega do trabalho (T).
• 29/06/2006: Segunda prova (P2).
• 11/07/2006: Exame (E).
• 17/07/2006: Divulgaçãão dos resultados finais da disciplina.