Pegue aqui os casos de teste para tsp.

Objetivos

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, 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

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