|
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 |
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.
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.
| PRÉ-REQUISITO 1 |
|---|
| IME04-10823 Algoritmos e Estruturas de Dados II |
| 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.