CCT-UFCA/Ciência da Computação/Algoritmos em Grafos

Programa do Componente Curricular

Código:	CC0017
Componente Curricular:	Algoritmos em Grafos
Semestre de Oferta:	3º Semestre		Tipo:	Disciplina	Caráter:	Obrigatória
Unidade Acadêmica Responsável:	Centro de Ciências e Tecnologia - CCT
Área:	Teoria da Computação
Créditos:	4	Carga horária:	64	Teórica:	64	Prática:	0	Extensão:	-
Pré-requisito:	CC0061 - Algoritmos e Estruturas de Dados
Co-requisito:
Equivalência:	MC0016

Objetivos

Apresentar e detalhar o conceito de grafo para a abstração de problemas matemáticos visando desenvolver algoritmos que atuem nesse contexto para solucionar problemas de forma computacional. Explorando famosos algoritmos e problemas em grafos diversos e suas particularidades, visando sempre criar algoritmos ótimos para dado problema.

Ementa

Conceitos e definições de grafos; Representação de grafos: matriz e listas de adjacências. Algoritmos de percurso em grafos. Árvore geradora mínima. Caminhos mínimos. Fluxo máximo.

Conteúdo

• Conceitos básicos de grafos
• Conceitos básicos iniciais: Subgrafos, Caminhos e Ciclos, Algumas classes de grafos, grafos bipartidos, etc.
• Grafos acíclicos: Árvores e Florestas
• Grafos orientados e Representação de grafos
• Busca em Profundidade - DFS
• Aplicações de busca em profundidade - ordenação topológica
• Aplicações de busca em profundidade - componentes fortemente conexas
• Busca em Largura
• Cálculo das distâncias entre um vértice aos demais em grafos não ponderados
• Aplicação da Busca em Largura
• Determinação das distâncias de um vértice aos demais
• Problema dos Caminhos mínimos
• Algoritmo de Dijkstra
• Algoritmo de Bellman-Ford
• Algoritmo de Floyd-Warshall
• Árvores geradora Mínima: Algoritmo de Kruskal -Técnica de Union-Find
• Árvores geradora Mínima: Algoritmo de Kruskal
• Árvore geradora Mínima: Algoritmo de Prim
• Fluxo em grafos

Metodologia

A disciplina e conduzida por meio de aulas teóricas presenciais, nas quais o "universo" dos grafos será apresentado e detalhado, formando uma base sólida para a abstração de problemas em grafos diversos sob os quais serão desenvolvidos algoritmos para soluciona-los. As aulas são dinâmicas e valorizam a participação ativa dos estudantes, principalmente por meio de atividades e projetos práticos, enfatizando a usabilidade dos grafos no contexto da computação.

A disciplina usualmente (mas não obrigatoriamente) conta com um mentor para auxiliar os alunos em horários alternativos aos das aulas.

Avaliação

Ao decorrer da disciplina, serão aplicadas provas três provas teóricas e será desenvolvido um trabalho prático (geralmente em dupla). A média final consistirá na média aritmética simples das notas das provas e do trabalho prático. O trabalho prático deverá ser adequadamente apresentado pela dupla especificando as contribuições de cada membro, pois a nota do trabalho em si é individual e pode variar entre os membros da dupla.

A metodologia de avaliação acima descrita pode variar de acordo com as especificidades de cada turma bem como com o calendário semestral.

Bibliografia Básica

1. SZWARCFITER, J. L. Teoria Computacional de Grafos. Elsevier, Rio de Janeiro, 2018.
2. GIBBONS, A. Algorithmic Graph Theory. Cambridge University Press, 1985.
3. CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Algoritmos: teoria e prática. 3ª ed. LTC, 2012. 944p. ISBN-10 : 8535236996, ISBN-13 : 978-8535236996.

Bibliografia Complementar

1. BONDY, J. A.; MURTY, U. S. T. Graph Theory. Springer, 2007.
2. EASLEY, D.; KLEINBERG J. Networks, Crowds, and Markes: Reasoning About a Highly Connected World. Cambridge University Press, 2010.
3. KNUTH, D. E. The Stanford GraphBase, Addison-Wesley, 1993.
4. JOYNER, D.; NGUYEN, M. V.; COHEN, N. Algorithmic Graph Theory. Em http://code.google.com/p/graph-theory-algorithms-book/, Google Code, 2010.
5. SEDGEWICK R. Algorithms in C - part 5: Graph Algorithms. 3rd ed. AddisonWesley/Longman, 1998.