Ementa/Descrição: |
Conceitos de algoritmos, análise e eficiência de algoritmos, projeto de algoritmos (indução, divisão e conquista, programação dinâmica, método guloso) NP-completude (teoria e técnica de demonstração), classes de complexidade (P, NP, NP-completo, NP-difícil), reduções polinomiais, algoritmos para problemas NP-completos. Conceitos básicos de grafos e algoritmos para resolver problemas modelados em grafos, Conectividade, Distâncias, Estabilidade e Número Cromático, Árvores e Arborecências, Grafos Planares. Caminhos, Ordenação Topológica, Coloração. |