|
UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO
|
| UNIDADE: INSTITUTO DE MATEMÁTICA E ESTATÍSTICA | ||
| DEPARTAMENTO: DEPTO. DE INFORMATICA E CIENCIAS DA COMPUTACAO | ||
| DISCIPLINA: Otimização em Grafos | ||
| CARGA HORÁRIA: 45 | CRÉDITOS: 3 | CÓDIGO: IME04-11312 |
| MODALIDADE DE ENSINO: Presencial | TIPO DE APROVAÇÃO: Nota e Frequência | |
| STATUS | CURSO(S) / HABILITAÇÃO(ÕES) / ÊNFASE(S) |
| Obrigatória | IME - Ciência da Computação (versão 1) |
| TIPO DE AULA | CRÉDITO | CH SEMANAL | CH TOTAL |
| Teórica | 3 | 3 | 45 |
| TOTAL | 3 | 3 | 45 |
OBJETIVO(S):
Apresentar ao aluno os problemas clássicos de otimização em grafos, suas principais aplicações e seus algoritmos de solução com o estudo de suas complexidades. Ao final do curso o aluno deverá estar apto a reconhecer as aplicações que podem ser resolvidas com a teoria estudada.
EMENTA:
Conceitos básicos sobre grafos. Representação computacional de grafos. Buscas em grafos, determinação de componentes fortemente conexas, ordenação topológica. Árvore geradora mínima: algoritmos de Prim e de Kruskal. Caminhos mínimos: fonte única, algoritmo de Dijkstra, algoritmo de Jonhson, caminhos mínimos entre todos os pares de nós, algoritmo de Floyd. Fluxo máximo: teorema do fluxo máximo e corte mínimo e suas implicações combinatórias, algoritmo de Ford-Fulkerson, algoritmo do tipo preflow-push.
| PRÉ-REQUISITO 1: IME04-11311 Algoritmos em Grafos |
| DISCIPLINA(S) CORRESPONDENTE(S): IME04-10829 Algoritmos em Grafos |
BIBLIOGRAFIA: -J. Bondy e U. Murty, "Graph Theory With Applications". Internet, 2004.
-D.West, "Introduction to Graph Theory", 2nd edition, Prentice Hall, 2001.
-R. Sedgwick, "Algorithms in C, Part 5 - Graph algorithms," 3rd edition, Addison Wesley, 2002.
-T.H. Cormen et al, "Introduction to Algorithms", MIT Press e McGraw-Hill, 1990.
-J.L. Szwarcfiter, "Algoritmos em Grafos", Editora Campus, 1987.