Projeto e Otimização de Algoritmos
oliveira(AT)inf.pucrs.br
Pegue aqui os casos de teste para tsp.
Objetivos
O cumprimento da disciplina busca dar ao aluno, ao
final do semestre, condições de:
- Conhecer e analisar as principais técnicas de projeto de
algoritmo.
- Formalizar, com precisão matemática, um problema
computacional.
- Determinar qual é a técnica de projeto mais apropriada para a
resolução de um determinado problema.
- Generalizar as técnicas para resolução de algum problema
inédito.
- 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
- Introdução ao Projeto e Análise de Algoritmos
- Algoritmos Gulosos
- Divisão e Conquista
- Programação Dinâmica
- Branch and Bound
- Algoritmos Genéticos
- Heurísticas e Algoritmos de Aproximação
- Programação Linear
Avaliação
G1 = (P1+P2+MT)/3
Materiais
- Materiais da disciplina:
- Recorrências estão aqui e uma lista
de exercícios está aqui.
- Uma lista de exercícios sobre backtraking está aqui.
-
What papers should everyone read?
- Siga no Twitter: CompSciFact
- Um Wikibook inteiro
sobre algoritmos.
- Um livro ótimo está aqui.
- Este livro é
muito bom! Leia com calma e cuidado!!
- Caso você tenha dificuldade com os trabalhos:
- Dicas sobre o uso de pseudo-código estão
aqui e aqui.
- Também temos o livro do Zobel na biblioteca. Use-o!!
- 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.
- Introdução à análise de algoritmos
- Material sobre análise de algoritmos em
Cprogramming.com.
- Explicações legais sobre notação O() na
Universidade de Wisconsin (Madison).
- Notação O() na Wikipedia.
- Problemas P e NP na Univ. da
California (Irvine).
- A reportagem de
capa da Communications of the ACM de setembro de 2009,
que trata dos últimos resultados sobre P e NP.
- Metodologias de desenvolvimento de algoritmos
- Veja na Wikipedia:
divide and conquer, greedy, branch and bound, dynamic
programming.
- Material bem legal na Universidade Federal de Campina Grande,
do Prof. Jorge
Abrantes de Figueiredo.
- Veja tambem o livro do Skiena, na biblioteca ou na Web.
- Um ótimo livro online em espanhol: Guerequeta y
Vallecillo (trata de todas as abordagens, mas às vezes a
matemática é meio exigente).
- Um exemplo australiano sobre backtracking em Berkeley.
- Um pouco de tudo:
- Uma série de aulas do
MIT (em inglês), sobre vários tópicos da disciplina e outros
assuntos.
- Um catálogo de cursos sobre algoritmos na Universidade
de Pittsburgh. Fonte de outros links!
- Design and Analysis na
Universidade de Kent.
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.