|
UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO
|
| UNIDADE: INSTITUTO DE MATEMÁTICA E ESTATÍSTICA | ||
| DEPARTAMENTO: DEPTO. DE INFORMATICA E CIENCIAS DA COMPUTACAO | ||
| DISCIPLINA: Algoritmos em Grafos | ||
| CARGA HORÁRIA: 45 | CRÉDITOS: 3 | CÓDIGO: IME04-11311 |
| 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):
Capacitar o aluno a compreender as propriedades matemáticas de grafos, bem como de suas aplicações. Em particular, para a compreensão das aplicações computacionais, o aluno deverá ficar apto a compreender as representações computacionais de grafos e os principais algoritmos utilizados na solução de problemas usando a teoria estudada.
EMENTA:
Conceitos básicos sobre grafos. Representação computacional de grafos. Buscas em grafos simple, busca em largura, profundidade e irrestrita. Determinação de elementos estruturais: pontes, pontos de articulação, blocos. Dígrafos: busca, determinação de componentes fortemente conexas, 2-SAT, ordenação topológica, alcançabilidade e fechamento transitivo. Algoritmos para determinação de ciclos eulerianos e hamiltonianos. Planaridade.
| PRÉ-REQUISITO 1: IME04-10823 Algoritmos e Estruturas de Dados II |
| 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.