Estudo de algoritmos eficientes para resolver problemas fundamentais de grafos.

Aplicação de três técnicas de desenho de algoritmos (estratégias greedy, programação dinâmica e transformação-e-conquista).

Compreensão dos conceitos básicos da Teoria da Complexidade.

Saber

Definir e identificar três técnicas de desenho de algoritmos: estratégias greedy, programação dinâmica e transformação-e-conquista.

Conhecer os algoritmos fundamentais de grafos, os tipos abstratos de dados envolvidos e as estruturas de dados usadas para os implementar com eficiência.

Compreender complexidade amortizada.

Definir algumas classes de complexidade e compreender alguns problemas em aberto.

Saber Fazer

Conceber e analisar um algoritmo aplicando programação dinâmica.

Formalizar um problema concreto em termos de grafos e adaptar um algoritmo clássico para o resolver.

Escolher, comparar, adaptar e utilizar estruturas de dados adequadas ao problema a resolver.

Calcular a complexidade de algoritmos com base na complexidade amortizada das funções auxiliares e calcular a complexidade amortizada dessas funções.

Avaliar soluções e efetuar escolhas fundamentadas.

Provar que um problema é NP-completo.

(1) Programação dinâmica.

(2) Introdução ao estudo de grafos. Definições fundamentais. Tipos abstratos de dados grafo não orientado e grafo orientado. Implementações de grafos.

(3) Algoritmos elementares de grafos. Percursos em profundidade e em largura. Ordenação topológica.

(4) Árvores mínimas de cobertura. Algoritmo de Kruskal. Tipo abstrato de dados partição.

(5) Complexidade amortizada. Método do potencial.

(6) Algoritmo de Prim. Tipo abstrato de dados fila com prioridade adaptável.

(7) Caminhos mais curtos. Algoritmos de Dijkstra, Bellman-Ford e Floyd-Warshall.

(8) Redes de fluxos. Fluxos máximos. Método de Ford-Fulkerson. Algoritmo de Edmonds-Karp. Emparelhamentos máximos em grafos bipartidos. Cortes mínimos.

(9) Introdução à Teoria da Complexidade. As classes P, NP, PSPACE e EXPTIME. Os sufixos difícil e completo. Redução de problemas. Alguns problemas em aberto.

Referências Principais

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd edition). The MIT Press, 2009.

Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2005.

Referências Complementares

Anany Levitin. Introduction to The Design and Analysis of Algorithms (3rd edition). Addison-Wesley, 2011

Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.

Steven S. Skiena. The Algorithm Design Manual (2nd edition). Springer, 2008.

Steven S. Skiena and Miguel A. Revilla. Programming Challenges: The Programming Contest Training Manual. Springer, 2003.

Os alunos devem:

(a) ter destreza em programação orientada por objetos;

(b) estar familiarizados com as estruturas de dados fundamentais (listas ligadas, tabelas de dispersão, árvores binárias de pesquisa, heaps binários);

(c) saber calcular as complexidades temporal e espacial de algoritmos.