MCTA027-13 - Teoria dos Grafos - Bacharelado em Ciência da Computação (3º quad./2016)

Horários e Local

2^a-feira, das 8h às 10h na Sala 302-2 (Aula teórica).
5^a-feira, das 10h às 12h no Lab. 407-2 (Aula prática).

Critério de avaliação

prova escrita valendo 40% da nota da disciplina;
projeto valendo 60% da nota da disciplina;
~~conceito F na prova ou no projeto implica automaticamente F na disciplina;~~
haverá entrega de exercícios que servirão de bônus.

Classificação de conceitos

A: ≥ 9,0

B: ≥ 8,0

C: ≥ 7,0

D: ≥ 5,5

F: < 5,5

O: ≤ 75% de presença em aula.

Recomendações

Matemática Discreta, Processamento da Informação, Algoritmos e Estruturas de Dados I.

Ementa

Conceitos básicos de grafos dirigidos e não dirigidos. Passeios, caminhos, circuitos. Grafos bipartidos e multi-partidos. Subgrafos. Isomorfismo. Conexidade. Florestas e árvores. Exemplos de problemas de interesse: coloração de vértices; clique máximo; caixeiro viajante; problemas de fluxo. Estruturas de dados para a representação de grafos. Percursos em grafos: em largura, em profundidade. Ordenação topológica. Árvores geradoras mínimas. Algoritmo de Kruskal. Caminhos mínimos em grafos: algoritmo de Dijkstra, algoritmo de Floyd-Warshall. Emparelhamentos: Teorema de Hall.

Bibliografia

1. CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L. e STEIN, C. Algoritmos: teoria e prática. 2a edição, Rio de Janeiro, RJ: Campus, 2002.

2. SEDGEWICK, R. Algorithms in C: part 5: graph algorithms. 3a edição. Reading, USA: Addison-Wesley, 2002.

3. CHARTRAND, G.; LESNIAK, L.; ZHANG, P. Graphs & digraphs. 5a edição. Boca Raton, London, New York: CRC Press, 2010.

Bibliografia Complementar

1. BOLLOBÁS, B. Modern graph theory. New York, Berlin, Paris: Springer, 1998.

2. BOAVENTURA, P. O. Grafos: Teoria, Modelos, Algoritmos. Edgard Blücher, 4a edição, 2006.

3. GROSS, J. L.; YELLEN, J. Graph theory and its applications. 2a edição. Boca Raton: Chapman & Hall/CRC, 2005.

4. ANDERSON, I. A first course in discrete mathematics. London, UK: Springer, 2001.

5. BONDY, J.A. e MURTY, U.S.R., Graph Teory, Graduate Texts in Mathematics, Springer, vol. 244, 2008. (versão de 1976 disponível online)

Bibliografia Adicional

1. WEST, D. B. Introduction to Graph Theory. Prentice-Hall, 2a edição.

2. ZIVIANI, N. Projeto de Algoritmos com Implementações em Java e C++. Thomson, 2007.

3. SZWARCFITER, J. L.; MARKENZON, L. Estruturas de dados e seus algoritmos. 3a edição. Rio de Janeiro, RJ: LTC, 2010.

4. MANBER, U. Introduction to algorithms: a creative approach. Reading, USA: Addison-Wesley, 1989.

Datas Importantes

21/11: Prova.

24/11 e 28/11: Apresentação de projetos.

01/12: Avaliação substitutiva (normatizada pela Resolução Consepe 181).

05/12: Avaliação de recuperação (normatizada pela Resolução Consepe 182).

08/12: Vista de prova e pedido de revisão (mediante agendamento por email).

Observações importantes

Prova Substitutiva (SUB): somente para quem faltou uma prova por motivo justificado (conforme Resolução Consepe 181).
É necessário a apresentação de algum documento que comprove o motivo. Motivos aceitos: a) doença ou acidente incapacitante (apresentar atestado médico); b) falecimento de familiar (apresentar atestado de óbito); c) viagem de trabalho ou necessidade de permanecer no emprego por motivo urgente (apresentar declaração do chefe ou superior equivalente); d) acidente de trânsito (apenas se você for o condutor do veículo, devendo apresentar Boletim de Registro de Acidente de Trânsito); e) greve nos transportes, alagamento, acidente de grandes proporções ou eventos similares que impeçam a circulação de pessoas por período prolongado (apresentar notícia veiculada em algum jornal/site de conhecimento geral e comprovante de que você mora ou trabalha na região onde o evento ocorreu).
Prova de recuperação (REC): abrange todo o conteúdo do quadrimestre e é destinada a alunos que tenham obtido conceito D ou F (conforme Resolução Consepe 182). Essa avaliação abrangerá todo o conteúdo da disciplina e a nota dessa prova substituirá a nota final na disciplina, restrito a que o conceito máximo obtido seja um conceito acima (de F para D ou de D para C).
Faltas: haverá controle de presença.
Sobre "abono de faltas": na UFABC, os docentes são orientados a não infringir as regras estabelecidas por lei brasileira ou regimento interno (resoluções, etc). O único caso previsto em lei sobre abono de faltas é para militares em exercício. Fora isso, não existe uma regra para "abono de faltas". Nesses termos, documentos que comprovem a necessidade de ausência em aula servem apenas para requisitar prova substitutiva, não para diminuir o número de faltas computada durante a disciplina.

Planejamento e Materiais

Calendário Acadêmico 2016

TIDIA: TeoriaGrafos-2016-diurno

Data	Assunto	Materiais
19/09: 2^a-feira	Breve introdução à Complexidade Assintótica de Algoritmos. Definições em grafos e exemplos de problema de interesse em grafos.	Introdução à complexidade Introdução em grafos
22/09: 5^a-feira	Aula prática. Representação computacional: matriz de adjacências e lista de adjacências (CORMEN p.419; ZIVIANI p.273).	Introdução à C/C++ Ponteiros Tutorial C++ Roteiro da Aula
26/09: 2^a-feira	Busca em largura (CORMEN p.422; MANBER p.198; ZIVIANI p. 288).	BFS
29/09: 5^a-feira	Aula prática. Propriedades da busca em largura. Especificação do projeto da disciplina	Roteiro da Aula
03/10: 2^a-feira	Busca em profundidade (CORMEN p.429; MANBER p.190; ZIVIANI p.283) Ordenação Topológica (CORMEN p.436; MANBER p.199; ZIVIANI p.292) Teste para Verificar se um grafo é acíclico	DFS
06/10: 5^a-feira	Aula prática. Busca em profundidade e ordenação topológica.	Roteiro da Aula
10/10: 2^a-feira	Algoritmo de Dijsktra (BONDY & MURTY p.15; CORMEN p.459; MANBER p.201; WEST p.97; ZIVIANI p.305). Entrega da equipe e da escolha do tema do projeto (atividade no TIDIA)	Fila de prioridades Dijkstra
13/10: 5^a-feira	Aula prática. Projeto: leitura dos grafos e cálculo de propriedades Projetos, Equipes e Datas de Apresentação	Roteiro da Aula
17/10: 2^a-feira	Algoritmo de Bellman-Ford (caminho mínimo para grafos com pesos negativos) Algoritmo de Floyd-Warshall (caminho mínimo entre todos os pares de vértices)	Bellman-Ford Floyd-Warshall
20/10: 5^a-feira	Aula prática. Projeto: implementação do método exato.	Roteiro da Aula
24/10: 2^a-feira	~~Árvores geradoras mínimas: algoritmo de Prim e algoritmo de Kruskal (CORMEN p.445; MANBER p.208; WEST p.95; ZIVIANI p.297).~~ Paralisação
27/10: 5^a-feira	Aula prática. Projeto: implementação do método exato (continuação da aula prática anterior).
31/10: 2^a-feira	Árvores geradoras mínimas: algoritmo de Prim e algoritmo de Kruskal (CORMEN p.445; MANBER p.208; WEST p.95; ZIVIANI p.297).	AGM Kruskal
03/11: 5^a-feira	Aula prática. Projeto: implementação do método heurístico 1.
07/11: 2^a-feira	Fluxo máximo em redes (CORMEN p. 509; BONDY & MURTY p. 70) Emparelhamentos em grafos: Teorema de Hall (CORMEN p. 525; BONDY & MURTY p.80-85; MANBER p.234; WEST sec.3.2).	Fluxo Máximo
10/11: 5^a-feira	Aula prática. Projeto: implementação do método heurístico 1. Fluxo máximo em redes (CORMEN p. 509; BONDY & MURTY p. 70)	Fluxo Máximo
14/11: 2^a-feira	FERIADO
17/11: 5^a-feira	~~Aula prática. Projeto:~~ ~~comparação dos métodos.~~ Emparelhamentos em grafos: Teorema de Hall (CORMEN p. 525; BONDY & MURTY p.80-85; MANBER p.234; WEST sec.3.2).	Slides
21/11: 2^a-feira	Prova Notas Notas Finais	Lista de Exercícios 1 Lista de Exercícios 2 Lista de Exercícios 3 Lista de Exercícios 4 Lista de Exercícios 5 Lista de Exercícios 6
24/11: 5^a-feira	Apresentação de projetos AS APRESENTAÇÕES SERÃO NA SALA S305-3 (não no lab)
28/11: 2^a-feira	Apresentação de projetos MUDANÇA DA SALA DE AULA PARA S307-1 (porque o projetor quebrou na sala 302-2)
01/12: 5^a-feira	Avaliação Substitutiva
05/12: 2^a-feira	Avaliação de Recuperação Notas Finais com REC
08/12: 5^a-feira	Vista de Prova e Pedido de Revisão (mediante agendamento por email) Sala 517-2
16/12: 6^a-feira	Lançamento de Notas

Letícia Rodrigues Bueno