Prof. Carlos Martinhon -  IC/UFF

Disciplina de Análise e Projeto de Algoritmos
      a) Programa:
  1. Complexidade de Algoritmos: Maquina RAM. Tamanho de um problema. Complexidades local e assintótica. Complexidade de algoritmos recursivos. Critérios de custo uniforme e logaritmico.
  2. Método da Divisão e Conquista: Princípios. Busca binária e complexidade. Máximo e mínimo de uma Lista e complexidade. Ordenação (Quicksort, Mergesort, etc). Limite inferior de um problema. 
  3. Método Guloso: Princípios. Aplicações: armazenamento, árvore geradora mínima, etc.
  4. Programação Dinâmica: Princípios, Princípio de Otimalidade de Bellman. Aplicações: Caminhos Mínimos, Escalonamento,  etc.
  5. Backtracking: Princípios. Aplicações: Problema das n Damas, Problema de Coloração de Vértices, etc.
  6. Classes de Problemas: Problemas de Decisão, Localização e Otimização. Algoritmos não-determinísticos, Classes P e NP dos problemas de decisão. Problemas NP-árduos e NP-completos. Redução e extensão entre problemas.
   
      b) Bibliografia:
  1. T. H. Cormem, C. E. Leiserson, R. L. Rivest, C. Stein [2002],  Introduction to Algorithms (Second Edition), MIT Press and McGraw-Hill.
  2. E. Horowitz, S. Sahni [1978], Fundamentals of Computer Algorithms, Computer Science Press.
  3. M. R. Garey and D. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness", W. H. Freeman, San Francisco, CA, 1979.
  4. C. Martinhon [1996], Apostila de Análise e Projeto de Algoritmos (Versão Preliminar e Incompleta).
     
      c) Outros:
  1. Avaliação: Média Aritmética da 1a e 2a prova. Aprovação acima de 6,0.
  2. Listas de Exercícios (em PDF):  Lista1, Lista2, Lista3, Lista4, Desafios!
  3. Notas (2o Semestre - 2004).
  4. Outros Links

NOTA: O Acrobat Reader pode ser encontrado aqui !!