Conteúdo desta página:

• Novidades (consulte este link freqüentemente)
• Dias, Horários e Local das Aulas
• Dia, Horário e Local de Atendimento
• Objetivos da Disciplina
• Ementa
• Bibliografia
• Material didático adicional
  
• Avaliação
• Datas importantes
• Notas

• (16/9) Veja a seção de avaliação e datas.
  

•  Terças e Sextas às 8h na sala 96, IC-1.

• O atendimento aos alunos será feito por e-mail, ou agendamento prévio.

O objetivo desta disciplina  é o estudo de algoritmos avançados para problemas clássicos em Computação. Daremos enfoque especial ao algoritmo polinomial de primalidade AKS, problemas em casamento de cadeias e para fluxos em redes. 

• Algoritmos algébricos: exponenciação e MDC; teste probabilístico de primalidade e aplicações em criptografia.
• Transformada rápida  de Fourier.
• Casamento de cadeias. 
• Estruturas de dados avançadas: conjuntos disjuntos e árvores auto-ajustáveis.
• Análise amortizada. 
• Fluxos em  redes.  
• Algoritmos aproximados  e exatos  para problemas NP-completos. 

Abaixo encontra-se a bibliografa básica para a disciplina. 

1. T.H. Cormen, C.E. Leiserson e R.L.Rivest. Introduction to Algorithms. McGraw-Hill, 1990.
2. U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley. 1989.
3. Brassard and Bratley.  Algorithmics.  Prentice-Hall,   1996. 
4. Ahuja,  Magnanti  and Orlin. Network Flows.  Prentice-Hall, 1993.
5. D. Hochbaum. Approximation algorithms for NP-hard problems. PWS, 1996.
   

• Teoria dos números. Neste diretório você encontra papers, apresentações e Web sites relacionados com o algoritmo AKS.

• String Matching. Neste diretório você encontra material relativo a busca de cadeias.

• A avaliação será baseada em três resumos e apresentações de artigos designados pelo professor. Os dois primeiros já estão definidos:

1. Primality testing in polynomial time, de Michiel Smid.
2. A unified view of string matching, de Ricardo Baeza.

• Entrega do primeiro resumo: 14 de outubro. Apresentações deste artigo nos dias 14 e 17 de outubro.
• Entrega do segundo resumo: 4 de novembro. Apresentações deste artigo nos dias 4 e 11 de novembro.
• Entrega do terceiro resumo: 25 de novembro. Apresentações deste artigo nos dias 25 e 28 de novembro.