MC558 - Projeto e Análise de Algoritmos II

A partir de 2016

Pré-­requisitos:

MA327 MC458/ MA327 MC448

Ementa:

Algoritmos em grafos. Redução entre problemas. Complexidade computacional. Classes de problemas. Problemas NP-completos.

 

Programa:

1. Grafos
- Definição e representação de grafos e de digrafos
- Isomorfismos
- Vizinhanças, cortes e graus
- Caminhos e ciclos
- Subgrafos
- Grafos conexos e componentes conexas
- Conjuntos independentes, cliques e coberturas
- Colorações de vértices
- Emparelhamentos
- Colorações de arestas
 
2. Algoritmos em Grafos
- Representação por lista de adjacência e matriz de adjacência
- busca em profundidade
- busca em largura
- ordenação topológica
- componentes fortemente conexos
- árvore geradora mínima: algoritmos gulosos de Prim e Kruskal (uso do "union-find" e análise
amortizada)
- caminhos mínimos com uma única fonte: algoritmos de Dijkstra, Bellman-Ford e DAG
- caminhos mínimos entre todos os pares de vértices: algoritmos da multiplicação de matrizes e Floyd-
Warshall
 
3. Reduções entre problemas
- Para obtenção de cotas superiores
- Para obtenção de cotas inferiores
- Reduções entre problemas envolvendo grafos
 
5. Programação Linear
- Formulação de problemas como PLs.
 

 

Bibliografia:

1 - T. Cormen, C. Leiserson, R. Rivest, C. Stein. Algoritmos - Teoria e Prática (3a. edição), Editora Campus (2012).

2 - U. Manber. Introduction to Algorithms, Addison-Wesley (1989).

3 - M. Sipser. Introduction to the Theory of Computation (3a. edição), Thomson South-Western (2012).

4 - M. Bazaraa, J. Jarvis, H. Sherali. Linear Programming and Network Flows (4a. edição), Wiley (2009).

5 - L. A. Wolsey. Integer Programming, Wiley (1998).