logo_uerj.gif (2426 bytes)

UERJ/IME 04-11312
Otimização em Grafos
Prof. Paulo Eustáquio

Ementa

Programa

Livro Texto | Bibliografia Adicional

Avaliação | Links

Período Atual (2018-2)


Ementa:

Representação computacional de grafos. Buscas em grafos simples: busca em largura, profundidade e irrestrita. Determinação de elementos estruturais: pontes, pontos de articulação, blocos. Buscas em digrafos: buscas, determinação de componentes fortemente conexas, ordenação topológica, alcançabilidade e fechamento transitivo. Árvore geradora mínima: algoritmos de Prim e Kruskal. Caminhos mínimos: algoritmo de Dijkstra, caminhos mínimos entre todos os pares de nós, algoritmo de Floyd, algoritmo de Bellman-Ford. Fluxo máximo: algoritmo de Ford-Fulkerson,Eemparelhamento máximo em grafos bipartidos, Algoritmos de fluxo de custo mínimo. Tópicos Complementares.

Demonstrações (trabalhos de alunos):

 

Programa:

Livro Texto:

Bibliografia Adicional:

Avaliação:

A avaliação constará de 2 provas (P1 e P2), pequenos trabalhos em casa (TC), em sala (TS), no Laboratório (LAB), extra (TE).

Nota  =  0.35(P1+P2) + 0.3TC + LAB + TS + TE

Trabalhos de casa são obrigatórios e individuais (em dupla quando forem programas) e só podem ser entregues até 1 mês após a data básica de entrega. Os trabalhos em sala, extra e no Laboratório somente aumentam a nota.

Última atualização: 10/09/2018


home
Home

topo
Topo