|
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 |
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.
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.
| PRÉ-REQUISITO 1 |
|---|
| IME04-11311 Algoritmos em Grafos |
| DISCIPLINA CORRESPONDENTE | |
| 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.