CCT-UFCA/Ciência da Computação/Algoritmos Aproximativos
Programa do Componente Curricular
[editar | editar código]| Código: | |||||||||
| Componente Curricular: | Algoritmos Aproximativos | ||||||||
| Semestre de Oferta: | Tipo: | Disciplina | Caráter: | Optativa | |||||
| Unidade Acadêmica Responsável: | Centro de Ciências e Tecnologia - CCT | ||||||||
| Área: | Teoria da Computação | ||||||||
| Créditos: | 4 | Carga horária: | 64 | Teórica: | 64 | Prática: | 0 | Extensão: | - |
| Pré-requisito: | CC0065 - Construção e Análise de Algoritmos | ||||||||
| Co-requisito: | |||||||||
| Equivalência: | |||||||||
Objetivos
[editar | editar código]Familiarizar os alunos com as técnicas de desenvolvimento e análise de algoritmos de aproximação para problemas combinatórios e com os resultados da teoria de complexidade relacionados a aproximações. São estudados algoritmos de aproximação para vários problemas, dentre os quais destacamos problemas de escalonamento, bin packing, geometria computacional e otimização sobre grafos.
Ementa
[editar | editar código]Recapitulação de resultados básicos sobre grafos, complexidade computacional e probabilidade. Métodos de desenvolvimento de algoritmos de aproximação: métodos métricos, métodos probabilísticos, métodos baseados em programação semidefinida e métodos primaisduais. Algoritmos de aproximação para problemas de escalonamento, bin packing, geometria computacional, e otimização sobre grafos (coberturas, empacotamentos, conectividade e cortes). Complexidade de aproximações: classes de complexidade Max SNP e APX, reduções, alguns resultados negativos de aproximação.
Conteúdo
[editar | editar código]Metodologia
[editar | editar código]Avaliação
[editar | editar código]Bibliografia Básica
[editar | editar código]- VAZIRANI, V. Approximation Algorithms. Springer, 2002. ISBN 978-3540653677.
- HOCHBAUM, D. Approximation Algorithms for NP-hard Problems. PWS Publishing Company, 1997. ISBN 978-0534949686.
- WILLIAMSON, D.; SHMOYS, D. The Design of Approximation Algorithms, Cambridge, 2011. ISBN 978-0521195270.
Bibliografia Complementar
[editar | editar código]- CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Algoritmos: teoria e prática. 3ª ed. LTC, 2012. 944p. ISBN-10 : 8535236996, ISBN-13 : 978-8535236996.
- MAYR E. W.; PRÖMEL, H. J.; STEGER A. Lectures on Proof Verification and Approximation Algorithms, Springer, 1998. ISBN 978-3-540-69701-5
- MOTWANI, R.; RAGHAVAN, P. Randomized Algorithms. Cambridge University Press, 1995. ISBN 978-0521474658.
- DASGUPTA, S.; PAPADIMITRIOU, C.; VAZIRANI, U. Algoritmos, 1oed. McGraw Hill, 2009, 336p. ISBN-10: 8577260321, ISBN-13: 978-8577260324.
- GOLDBARG, E.; GOLDBARG, M.; LUNA, H. Otimização Combinatória e Meta-heurísticas: Algoritmos e Aplicações. GEN LTC, 2015. ISBN-13: 978-8535278125