Algoritmos em Grafos - TCC-00.284

Segundo Período de 2017 - Turma A-1

Prof. Fábio Protti - fabio@ic.uff.br

 

Horário e Local

Segundas e quartas, das 9:00 às 11:00

Sala 204

 

Programa da disciplina

Introdução a grafos. Definições básicas. Conceitos importantes de Teoria de Grafos. Grafos como estruturas de dados.

Grafos Eulerianos. Algoritmo para Trilhas Eulerianas.

Busca em profundidade em grafos. Algoritmo para determinar articulações e blocos de um grafo.

Conceito de digrafo (grafo direcionado). Busca em profundidade em digrafos. Algoritmo para determinar componentes fortemente conexas de um digrafo.

Busca em largura em grafos. Algoritmo de Dijkstra para caminhos mínimos em digrafos.

Algoritmo de Floyd-Warshall para caminhos mínimos entre todos os pares de vértices de um digrafo. Programação Dinâmica para caminhos mínimos.

Algoritmos de Kruskal e Prim para determinação de árvores geradoras mínimas.

Algoritmos de ordenação topológica de um dígrafo acíclico.

Fluxos em redes.

Emparelhamentos. Algoritmo dos caminhos aumentantes. Método Húngaro para emparelhamentos em grafos bipartidos.

O Problema do Caixeiro Viajante (PCV). Algoritmo exato para o PCV. Algoritmos aproximativos para o PCV.

 

Estrutura do Curso

Aulas Teóricas.

Lista de exercícios sugeridos (não são para entregar, mas recomendo a resolução).

Exercícios de implementação (não são para entregar).

 

Calendário de Provas 

Primeira Prova: dia 9 de outubro  de 2017

Segunda Prova: dia 29 de novembro de 2017

Segunda Chamada: dia 6 de dezembro de 2017 (só para quem perdeu P1 ou P2 - abrange todo o conteúdo da disciplina!)

VS: dia 13 de dezembro de 2017

 

Trabalho 

Entrega: até dia 3 de dezembro

Enviar por e-mail:

·         membros da equipe

·         código fonte do programa

·         código executável do programa (ou explicação de como executar)

Enunciados dos trabalhos

 

 Avaliação

Seja M = max{  (2*P1+2*P2+T)/5  ,  (P1+P2)/2  }

Se M >= 6,0, o aluno está aprovado.

Se M < 4,0, o aluno está reprovado.

Se 4 <= M < 6,0, o aluno deve fazer a VS.

A nota da VS deverá ser maior ou igual a 6,0.

 

Exercícios de implementação (não são para entregar)

Use o site http://uva.onlinejudge.org

A linguagem de implementação pode ser Pascal, C, C++ ou Java.

 

784 - Maze Exploration

10305 - Ordering Tasks

10099 - The Tourist Guide

762 - We Ship Cheap

10054 - The Necklace

10004 - Bicoloring

10067 - Playing with Wheels

523 - Minimum Transport Cost

532 - Dungeon Master

10034 - Freckles

 

Bibliografia

1)    Jayme L. Szwarcfiter. Grafos e Algoritmos Computacionais. Campus, Rio de Janeiro, 1986.

2)  Alan Gibbons. Algorithmic Graph Theory. . Cambridge University Press, 1985.

3)  T. H. Cormen e outros. Algoritmos (tradução da 2a. Edição Americana). Campus, RJ, 2002.

 

Downloads

Lista de Exercícios Sugeridos

Aula Inicial sobre Aplicações em Grafos

Slides da Disciplina 

Conceitos Introdutórios sobre Grafos