CPS740 Algoritmos e Grafos

  Professores Jayme L. Swzarcfiter e Márcia R. Cerioli
  Programa de Engenharia de Sistemas e Computação - UFRJ
  Mestrado e Doutorado
  2018/2


Ementa:

Representação de grafos. Busca em Profundidade e em Largura. Algoritmo Guloso. Programação Dinâmica. Fluxo Máximo em Redes. Caminhos Mínimos. Emparelhamento Máximo em Grafos.


Programa em 2018/2:

1. Introdução:
1.1. Complexidade de algoritmos
1.2. Representação de grafos

2. Busca em Grafos:
2.1. Busca em profundidade
2.11. Aplicação: bi-conectividade
2.2. Busca em profundidade em digrafos
2.2.1. Aplicação: componentes fortemente conexos
2.3. Busca em Largura
2.3.1. Busca em largura lexicográfica
2.4. Busca irrestrita

3. Outras Técnicas
3.1. Algoritmo guloso: árvore geradora mínima
3.2. Programação dinâmica

4. Fluxo Máximo em Redes
4.1. O Teorema do fluxo máximo - corte mínimo
4.2. Algoritmos para encontrar um fluxo máximo em uma rede

5. Caminho Mínimos
5.1. Equações de Bellman
5.2. Algoritmos de Dijkstra
5.3 Algoritmo de Bellman-Ford

5.4 Algoritmo de Floyd 5.7 Detecção de ciclos negativos 6. Emparelhamentos Máximos em Grafos 6.1 Emparelhamentos perfeitos 6.2 Caminhos alternantes 6.3 Cardinalidade máxima em grafos bipartidos sem pesos 6.4 O método húngaro 6.5 Emparelhamentos e coberturas por vértices


Página atualizada em 6 jun 18 por Márcia R. Cerioli