Projeto e Otimização de Algoritmos

oliveira(AT)inf.pucrs.br

Objetivos

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

1. Conhecer e analisar as principais técnicas de projeto de algoritmo.

2. Formalizar, com precisão matemática, um problema computacional.

3. Determinar qual é a técnica de projeto mais apropriada para a resolução de um determinado problema.

4. Generalizar as técnicas para resolução de algum problema inédito.

5. Analisar precisamente o algoritmo desenvolvido a fim de provar a sua corretude e de estabelecer limites para o tempo de execução e para o consumo de memória.

Ementa

Estudo das principais técnicas para o projeto e análise de algoritmos: programação dinâmica, algoritmos gulosos, divisão e conquista, backtracking, branch and bound e algoritmos genéticos. Estudos de caso no desenvolvimento de algoritmos. Introdução ao Teorema Mestre.

Programa

1. Introdução ao Projeto e Análise de Algoritmos

   1. Algoritmos Gulosos

      1. Princípios e propriedades
      2. Exemplos
         • Troco em notas/moedas
         • Escalonamento de tarefas
         • Codificação de Huffman
      3. Uso heurístico

   2. Divisão e Conquista

      1. Princípios e propriedades
      2. Exemplos
         • Pesquisa binária
         • Mergesort
         • Quicksort
         • Alg. de Karatsuba

   3. Programação Dinâmica

      1. Princípios e Propriedades
      2. Modelagem com recursão
      3. Exemplos
      4. Técnica de Memoização
      5. Retirada da recursão
      6. Exemplos

   4. Backtracking

      1. Princípios e Propriedades
      2. Modelagem
      3. Exemplos

   5. Branch and bound

      1. Princípios e Propriedades
      2. Modelagem
      3. Exemplos

   6. Algoritmos genéticos

      1. Princípios e Propriedades
      2. Modelagem
      3. Exemplos

2. Teorema Mestre

   1. Definição
   2. Interpretação dos três casos
   3. Exemplos

Avaliação

G1 = ( P1 + P2 + MT ) / 3

Materiais

1. Metodologias de desenvolvimento de algoritmos

   1. Veja na Wikipedia: divide and conquer, greedy, branch and bound, dynamic programming.

   2. O livro de algoritmos do Jeff Erickson, excelente!!

   3. E a coleção de problemas do Ian Parberry, que é muito boa também!!

   4. Material bem legal na Universidade Federal de Campina Grande, do Prof. Jorge Abrantes de Figueiredo.

   5. Veja tambem o livro do Skiena, na biblioteca ou na Web.

   6. Um ótimo livro online em espanhol: Guerequeta y Vallecillo (trata de todas as abordagens, mas às vezes a matemática é meio exigente).

   7. Um exemplo australiano sobre backtracking em Berkeley.

   8. Uma lista de exercícios sobre backtraking está aqui.

2. 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. Recorrências estão aqui e uma lista de exercícios está aqui.

   5. What papers should everyone read?

   6. Siga no Twitter: CompSciFact

   7. Um Wikibook inteiro sobre algoritmos.

   8. Um livro ótimo está aqui.

   9. Este livro é muito bom! Leia com calma e cuidado!!

   10. Um repositório de links existe na Iowa State.

   11. Problemas P e NP na Univ. da California (Irvine).

   12. A reportagem de capa da Communications of the ACM de setembro de 2009, que trata dos últimos resultados sobre P e NP.

Bibliografia:

Livros texto

1. KLEINBERG, J.; TARDOS, E. Algorithm design. Addison-Wesley, 2005.

2. CORMEN, T. H. Algoritmos: teoria e prática. 3ª ed., Rio de Janeiro: Elsevier-Campus, 2012.

3. BALAMURUGAN, S. Nature-inspired Algorithms Applications. 2021. Artificial Intelligence and Soft Computing for Industrial Transformation. Web.

Livros complementares

1. HOROWITZ, E.; SAHNI, S.; RAJASEKARAN, S. Computer algorithms. Silicon Press, 2008.

2. LEVITIN, A.; LEVITIN, M. Algorithmic puzzles. Oxford University Press, 2011.

3. McCORMICK, J. Nine algorithms that changed the future: The ingenious ideas that drive today´s computers. Princeton University Press, 2013.

4. MORET, B.; SHAPIRO, H.: Algorithms from P to NP: Design and Efficiency. 1ª ed. Addison-Wesley, 1991.

5. DASGUPTA, S.; PAPADIMITRIOU, C.; VAZIRANI, U. Algorithms. McGraw-Hill, 2006.

6. GUSFIELD, D.: Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, 1997.