Complexidade e Otimização 

---

Critérios de correção para os trabalhos.

Os trabalhos tem a forma de ARTIGOS (pegue aqui um exemplo). Artigos que incluírem o código do programa no texto como se fosse uma explicação para o algoritmo recebem notas ruins. A lista de exercícios da disciplina está aqui. 

Objetivos

O cumprimento da disciplina busca dar ao aluno, ao final do semestre, condições de:

1. Aprofundar os métodos para análise da eficiência de algoritmos e compreender as formas de análise de algoritmos.
2. Aprofundar as classes de problemas P e NP, suas características e importância.
3. Conhecer as metodologias mais comuns para desenvolvimento de algoritmos eficientes.

Ementa

Estudo de complexidade e análise de algoritmos utilizando notação assintótica (O(), Tetha(), Omega()). Aplicação de recorrências e somatórios na análise de algoritmos. Estudo das classes de problemas (P, EXP, NP, NP-Completo, NP-Hard, P-SPACE) e instâncias de problemas destas categorias. Caracterização de estratégias para a construção de algoritmos e solução de problemas (algoritmos gulosos, programação dinâmica, branch- and- bound, backtracking). Estudo de problemas de otimização e de análise combinatória.

Programa

1. Revisão de análise de algoritmos
   1. Ordem de crescimento
   2. Notação Assintótica
      1. Notação O
      2. Notação Omega
      3. Notação Theta
   3. Tipos de algoritmos: logarítmico, linear, quadrático, exponencial e outros
2. Análise de Complexidade de Algoritmos e de Problemas
   1. Somatórios
   2. Recorrências
   3. Análise de Problemas
   4. Classes de Problemas
      1. P
      2. NP
      3. NP- Completo
      4. NP- Hard
   5. Solução de Problemas "Difíceis"
      1. Força- Bruta
      2. Heurísticas
   6. Exemplos de Problemas
3. Estratégias de Construção de Algoritmos1 Introdução aos Problemas de Otimização
   1. Algoritmos Gulosos
   2. Divisão e Conquista
   3. Programação Dinâmica
      1. Recorrências
      2. Tabulação e Memoização
   4. Branch & Bound
   5. Backtracking

Avaliação

G1 = (P1+P2+NTrab)/3

Materiais

1. Materiais da disciplina: 
   1. Somatórios estão aqui e uma lista de exercícios está aqui.
   2. Notações estão aqui e uma lista de exercícios está aqui.
   3. Recorrências estão aqui e uma lista de exercícios está aqui.
   4. Uma lista de exercícios sobre backtraking está aqui.
    
2. What papers should everyone read? 
3. Siga no Twitter: CompSciFact 
4. Um Wikibook inteiro sobre algoritmos. 
5. Um livro ótimo está aqui. 
6. E outro livro muito legal está aqui. 
7. Caso você tenha dificuldade com os trabalhos:
   1. Dicas sobre o uso de pseudo-código estão aqui, aqui, e aqui.
   2. Também temos o livro do Zobel na biblioteca. Use-o!!
   3. Um repositório de links existe na Iowa State. 
   Recomendamos os itens listados em Writing Texts and Abstracts, especialmente as dicas de Schulzrinne e a apresentação de Peyton-Jones. 
8. Introdução à análise de algoritmos
   1. Somas na Univ. da California (Davis).
   2. Material sobre somas (bem legal), na Universidade do Tennessee (Knoxville).
   3. Material sobre análise de algoritmos em Cprogramming.com.
   4. Explicações legais sobre notação O() na Universidade de Wisconsin (Madison).
   5. Notação O() na Wikipedia.
   6. Problemas P e NP na Univ. da California (Los Angeles).
   7. Mais P e NP na Univ. da California (Irvine).
   8. A reportagem de capa da Communications of the ACM de setembro de 2009, que trata dos últimos resultados sobre P e NP.
    
9. Metodologias de desenvolvimento de algoritmos
   1. Veja na Wikipedia: divide and conquer, greedy, branch and bound, dynamic programming.
   2. Material bem legal na Universidade Federal de Campina Grande, do Prof. Jorge Abrantes de Figueiredo.
   3. Veja tambem o livro do Skiena, na biblioteca ou na Web.
   4. Um ótimo livro online em espanhol: Guerequeta y Vallecillo (trata de todas as abordagens, mas às vezes a matemática é meio exigente).
   5. Um exemplo australiano sobre backtracking em Berkeley.
    
10. Um pouco de tudo:
    1. Uma série de aulas do MIT (em inglês), sobre vários tópicos da disciplina e outros assuntos.
    2. Um catálogo de cursos sobre algoritmos na Universidade de Pittsburgh. Fonte de outros links!
    3. Design and Analysis na Universidade de Kent.
    4. Catálogo de Algoritmos, do Skiena, em Stony Brook. (Temos na biblioteca)
     

Bibliografia:

Livros texto

•  AHO, Alfred V. Foundations of computer science. New York, NY: Computer Science Press, 1998.
•  CORMEN, Thomas H. Introduction to algorithms. 3. ed. Cambridge (MA): The MIT Press, 2009.
•  RAWLINS, Gregory J. E. Compared to what? An introduction to the analysis of algorithms. New York, NY: Computer Science Press, 1992.

Livros complementares

• GERSTING, Judith L. Fundamentos matemáticos para ciência da computação: um tratamento moderno de matemática discreta. 5. ed. Rio de Janeiro: LTC, 2004.
• GIBBONS, Alan. Algorithmic graph theory. Cambridge (UK): Cambridge Univ., 1985.
• LEVITIN, Anany. Introduction to the design and analysis of algorithms. Boston: Addison- Wesley, 2003.
• WALLIS, W. D. A beginner's guide to graph theory. Boston: Birkhäuser, 2000.
• DASGUPTA, S., PAPADIMITRIOU, C.H., VAZIRANI, U.V. Algorithms. http://www.cs.berkeley.edu/~vazirani/algorithms/all.pdf. Acessado em janeiro de 2011.

---

 De volta para minha página. 

[PUCRS]

[Faculdade de Informática]

[Pós-Graduação em Informática]