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 = ( 3 * P1 + 3 * P2 + MT ) / 7

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. Uma playlist sobre Programação Dinâmica no YouTube, bem legal!

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

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

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

   8. Um exemplo australiano sobre backtracking em Berkeley.

   9. Uma lista de exercícios está aqui.

2. Um pouco de tudo:

   1. Alguns vídeos sobre o passeio do cavalo usando o algoritmo de Warnsdorff:

      1. Tabuleiro 12x12
      2. Tabuleiro 18x18
      3. Tabuleiro 22x22
      4. Tabuleiro 35x35
      5. Tabuleiro 48x48

   2. Uma série de aulas do MIT (em inglês), sobre vários tópicos da disciplina e outros assuntos.

   3. Um catálogo de cursos sobre algoritmos na Universidade de Pittsburgh. Fonte de outros links!

   4. Design and Analysis na Universidade de Kent.

   5. Recorrências estão aqui e uma lista de exercícios está aqui.

   6. What papers should everyone read?

   7. Siga no Twitter: CompSciFact

   8. Um Wikibook inteiro sobre algoritmos.

   9. Um livro ótimo está aqui.

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

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

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

   13. 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.