Projeto e Otimização de Algoritmos

oliveira(AT)inf.pucrs.br

Consulte o cronograma

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 algoritmos.
  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, as quais são: programação dinâmica, algoritmos gulosos, divisão e conquista. Introdução ao Teorema Mestre e as três regras. Introdução à Programação Linear e estudo do algoritmo Simplex. Introdução à Programação Inteira e estudo do método Branch and Bound. Estudo dos principais métodos heurísticos como GRASP, descida de gradiente e Algoritmos Genéticos.

Programa

  1. Introdução ao Projeto e Análise de Algoritmos
    1. Algoritmos Gulosos
    2. Divisão e Conquista
    3. Programação Dinâmica
    4. Branch and Bound
    5. Algoritmos Genéticos
    6. Heurísticas e Algoritmos de Aproximação
    7. Programação Linear

Avaliação

G1 = (P1+P2+MT)/3

Materiais

  1. Materiais da disciplina:
    1. Recorrências estão aqui e uma lista de exercícios está aqui.
    2. 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. Este livro é muito bom! Leia com calma e cuidado!!
  7. Caso você tenha dificuldade com os trabalhos:
    1. Dicas sobre o uso de pseudo-código estão 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. Material sobre análise de algoritmos em Cprogramming.com.
    2. Explicações legais sobre notação O() na Universidade de Wisconsin (Madison).
    3. Notação O() na Wikipedia.
    4. Problemas P e NP na Univ. da California (Irvine).
    5. 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.

Bibliografia:

Livros texto

Livros complementares