MC558 - Projeto e Análise de Algoritmos II

Créditos: 4
Horas semanais de atividades teóricas: 3
Horas semanais de atividades práticas: 1
Oferecimento: Ambos os períodos letivos
 
Pré-Requisitos
MA327
MC458 ou 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
T. Cormen, C. Leiserson, R. Rivest, C. Stein. Algoritmos - Teoria e Prática (3a. edição), Editora Campus (2012).
U. Manber. Introduction to Algorithms, Addison-Wesley (1989).
M. Sipser. Introduction to the Theory of Computation (3a. edição), Thomson South-Western (2012).
M. Bazaraa, J. Jarvis, H. Sherali. Linear Programming and Network Flows (4a. edição), Wiley (2009).
L. A. Wolsey. Integer Programming, Wiley (1998).