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
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.
Referências Bibliográficas
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.
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.
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: Uma espécie de referência ``bíblica’' 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 mas tem esta versão 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çõ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.
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.
Versão PDF Observação: fazer apenas os exercícios 3, 5, 6, 7 e 11.
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:
Calcule: A = (2*P1+2*P2+T)/5
Calcule: P = (P1+P2)/2
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:
Se o aluno não compareceu ao exame então MF = M.
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:
Não haverá provas substitutivas.
Todas as provas realizadas durante o semestre e o exame final serão realizados sem consulta.
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.
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).
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.
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.