Código: Tópicos Especiais em Computação XII
Professor: Leandro Zatesko
Nome: TAP - Técnicas Avançadas de Programação

EMENTA

Programação competitiva. Estruturas de dados avançadas: make–union–find, árvores de segmento, árvores de Fenwick, heaps e árvores de sufixo. Algoritmos gulosos. Algoritmos de divisão e conquista. Programação dinâmica. Modelagem de problemas com grafos. Problemas combinatoriais. Problemas de Teoria dos Números. String matching. Geometria computacional.

OBJETIVOS

Estudar técnicas avançadas de programação para a resolução de problemas complexos, praticando a implementação das técnicas em diversos exercícios e comparando analiticamente o resultado com os algoritmos de força bruta. Entender o conceito de espaço de busca em problemas de otimização. Aprimorar a criatividade e as habilidades necessárias para competições de programação. Estudar algumas técnicas para a obtenção em tempo viável de soluções aproximadas para problemas NP-completos ou NP-difíceis.

BIBLIOGRAFIA BÁSICA

HALIM, S.; HALIM, F. Competitive Programming 3: The New Lower Bound of Programming Contests, Lulu, 2013.
SKIENA, S. S.; REVILLA, M. Programming Challenges, 1ª edição. Springer, 2003.
DASGUPTA, S.; PAPADIMITRIOU, C. H.; VAZIRANI, U. Algoritmos, McGraw Hill, 2008.
KLEINBERG, J.; TARDOS, E. Algorithm Design, 1ª edição. Addison Wesley, 2005.
SKIENA, S. S. The Algorithm Design Manual, 2ª edição. Springer, 2010.

BIBLIOGRAFIA COMPLEMENTAR

BELLMAN, R.; DREYFUS, S. Dynamic Programming, 1ª edição. Princeton University Press, 2010.
CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Algoritmos: Teoria e Prática, Rio de Janeiro: Campus, 2002.
KNUTH, D. E. The Art Of Computer Programming, vol. 1–4, Addison-Wesley, 2011.
MANBER, U. Introduction To Algorithms: A Creative Approach, 1ª edição. Addison-Wesley, 1989.