Disciplina: DCC172 - PROGRAMAÇÃO COMPETITIVA
Horas Aula: 4
Departamento: DEPTO DE CIENCIA DA COMPUTACAO /ICE
Plano de Ensino
Voltar
Ementa
Estudo de técnicas de projeto de algoritmos e programação visando problemas típicos de competições de programação: Programação Dinâmica, Algoritmos em Grafos, Backtracking e Heurísticas, Algoritmos Geométricos, Tópicos variáveis e atuais em competições de programação.
Conteúdo
Técnica de Programação Dinâmica: Problemas da mochila, problema da árvore de busca ótima; Maior Sub-sequëncia Comum; Distância de Edição; Comparação de Strings (algoritmo KMP);
Algoritmos em Grafos: Caminhos Mínimos (algoritmos de Dijkstra e Floyd-Warshall); Árvore Geradora Mínima (algoritmo de Prim); Fluxo em Grafos (algoritmo de Edmonds-Karp e variações); Percursos em Grafos;
Técnica de Backtracking e Heurísticas;
Algoritmos Geométricos: Primitivas Básicas, Ordenação Angular, Problema do Par mais Próximo, Envoltória Convexa;
Tópicos variáveis e atuais em competições de programação;
Bibliografia
- MARTINS, W. Jogos de Lógica. Ed Vieira. 2011.
- SKIENA S., REVILLA M., Programming Challenges: The Programming Contest Training Manual. Springer, 2003.
- SCHILDT, H. C - Completo e Total. 3rd Ed. Editora Makron Books, 1997.
Bibliografia(continuação)
Não informado
Bibliografia complementar
- CORMEN, T., LEISERSON, C., REVERST, R., STEIN, C. Algoritmos - teoria e prática. Campus, 2002.
- DEITEL, H., DEITEL, P. C++ How to program. Prentice Hall, 8ed. 2012.
- GROSS, J. L., YELLEN, J. Graph Theory and Its Applications, Second Edition, 2010
- PREISS, B. Estrutura de Dados e Algoritmos. Elsevier. 2001.
- ZIVIANI, N. Projeto de Algoritmos - com implementacoes em Pascal e C. Cengage Learning, 3rd Ed, 2011.
