| Ementa/Descrição: |
Análise dos algoritmos básicos de busca em grafos. Técnicas de projeto de algoritmos: método guloso (sugestões de exemplos: Escalonamento de tarefas, Kruskal, Prim, Dijkstra, Mochila fracionária, Huffman) e programação dinâmica (sugestões de exemplos: Corte de barras, Bellman-Ford, Floyd-Warshall, Alinhamento de sequências, Mochila inteira). Introdução à teoria da complexidade computacional: redução entre problemas e classes P, NP, NP-completo e NP-difícil. Tópicos opcionais: noções de abordagens para tratar problemas NP-completos e NP-difíceis. |
| Referências: |
"CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Algoritmos: teoria e prática. 2. ed. Rio de Janeiro, RJ: Elsevier: Campus, 2002. P. 916.
DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos H.; VAZIRANI, Umesh V. Algorithms. Boston, USA: McGraw-Hill, 2008. P. 320.
SEDGEWICK, Robert. Algorithms in c, Part 5: Graph Algorithms. 3. ed. Reading, USA: Addison-Wesley Professional, 2002. P. 482.
Bibliografia complementar
SEDGEWICK, Robert. Algorithms in C, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching. 3. ed. Reading, USA: Addison-Wesley Publishing, 1998. P. 702. ISBN 9780201756081.
SEDGEWICK, Robert; WAYNE, Kevin. Algorithms. 4. ed. Boston, USA: Addison-Wesley, 2011. P. 955. ISBN 9780321573513.
KLEINBERG, Jon; TARDOS, Éva. Algorithm Design. 1. ed. Boston, USA: Addison-Wesley, 2006. P. 864. ISBN 9780321295354.
MANBER, Udi. Introduction to Algorithms: A Creative Approach. Boston, USA: Addison-Wesley, 1989. P. 478. ISBN 9780201120370."
|
