MC558 - Projeto e Análise de Algoritmos II

Créditos: 4
Horas semanais de atividades teóricas: 4
Oferecimento: Ambos os períodos letivos
 
Pré-Requisitos
MC458
Ementa

Grafos: conceitos e algoritmos. Reduções entre problemas. Programação Linear. Classes de Problemas.

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

4. Programação Linear

- Formulação de problemas como PLs.

5. Classes de Problemas

A hierarquia de Complexidade. As classes P, NP, NP-completo e NP-difícil

​​​​​​​Noção de completude e o Teorema de Cook

​​​​​​​Problemas e reduções fundamentais em NP-completude

​​​​​​​​​​​​​​Outras classes de problemas: co-NP, PSPACE, problemas indecidíveis (Problema da Parada)

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).