MENU: [ Avisos | Informações Gerais | Regras | Bibliografia | Plano de Atividades ]
Última atualização em 21/05/2018 (plano de atividades).
Leia toda esta página no início do semestre: ela contém informações essenciais, como as regras para solicitação de segunda chamada e para o cálculo da nota na disciplina.
Esta página está em contínua construção. Por favor, entre em contato comigo caso você precise de alguma informação adicional, ou caso acredite ter encontrado um erro aqui. Obrigado!
Nesta disciplina nós aprendemos as técnicas clássicas para a manipulação algorítmica de grafos.
Informações importantes sobre a disciplina – como justificativa, objetivos, ementa e bibliografia – podem ser encontrados na regulamentação oficial.
O nosso livro de referência é o "Cormen", que contém tudo o que veremos e muito mais. Ele e outros livros pelos quais o assunto da disciplina pode ser estudado estão listados tanto na bibliografia desta página quanto na regulamentação da disciplina.
Todas as atividades da disciplina já têm data estimada no plano de atividades. Se você percebeu um choque de datas importantes com outra disciplina, ou se você já sabe que não poderá fazer uma das nossas provas na data prevista, por favor me comunique o quanto antes!
Esteja atento, desde o início do semestre, às regras para solicitação de segunda chamada e para o cálculo da nota da disciplina.
A minha sugestão para a obtenção de um bom desempenho na disciplina é (1) acompanhar as aulas com atenção, tirando dúvidas o quanto antes, e (2) fazer os exercícios com regularidade. Caso você possua uma dúvida no horário da aula, o ideal é tirá-la na própria ocasião, para que os demais alunos também se beneficiem das explicações. Esteja, porém, à vontade para me contactar fora das aulas.
Segunda chamada: consulte as regras para a solicitação de prova de segunda chamada.
6 pontos: 2 Avaliações Teóricas, cada uma valendo 3 pontos.
4 pontos: trabalhos de implementação (via Spoj, explicados pelo SIGAA).
Trabalho 1 (entrega até 15/maio): Componentes Conexas.
Trabalho 2 (entrega até 30/maio): --- DIVULGAÇÃO PENDENTE ---
Trabalho 3 (entrega até 10/junho): --- DIVULGAÇÃO PENDENTE ---
Trabalho 4 (entrega até 22/junho): --- DIVULGAÇÃO PENDENTE ---
O critério de aprovação será o padrão da universidade:
| Nota | ≥ 7 | 7 > média ≥ 4 | < 4 |
|---|---|---|---|
| Situação | Aprovado | AF | Reprovado |
O livro de referência da disciplina é o "Cormen": ele contém tudo o que estudaremos e muito mais (não haverá, porém, compromisso em seguir linearmente livro algum).
Original: Introduction to Algorithms (third edition). Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. MIT Press. 2009. ISBN: 9780262033848 (capa dura) e 9780262533058 (capa fina).
Tradução: Algoritmos – Teoria e Prática. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Editora Campus. 2012. ISBN: 978-85-352-3699-6.
Estes outros livros também cobrem todo o conteúdo ou boa parte dele:
Algoritmos. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. McGraw-Hill. 2009. ISBN: 978-85-7726-032-4.
Algorithms. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. McGraw-Hill. 2006. ISBN: 978-0-07-352340-8.
Projeto de Algoritmos – com implementações em Pascal e C - 3ª edição. Nivio Ziviani. Cengage Learning. 2011. ISBN: 9788522110506.
Veja o capítulo 7.
Algorithms, 4th Edition . Robert Sedgewick, Kevin Wayne. Addison-Wesley. 2011. ISBN: 978-0-321-57351-3.
Veja o capítulo 4.
Algorithm Design and Applications. Michael T. Goodrich, Roberto Tamassia. Wiley. 2015. ISBN: 978-1-118-33591-8.
Veja a Parte 4. Além disso, da versão de 2002 desse livro, há um capítulo sobre grafos publicamente acessível.
Esta disciplina possui 35 encontros planejados, dos quais 33 são Aulas e 2 são Avaliações Parciais (as alterações de 32 para 33, 34 e 35 encontros foram aprovadas em sala pelos alunos). Adicionalmente, poderá ser realizada também uma Avaliação Final. Na tabela a seguir estão as datas e descrições de cada encontro.
O conteúdo que veremos pode ser dividido em 5 partes:
Introdução (4 aulas): introdução à disciplina, a grafos e seus algoritmos, e às representações de grafos em algoritmos.
Percursos e Aplicações (9 aulas): motivados por 3 problemas (computar distâncias, ciclos e ordenações topológicas), estudaremos diferentes maneiras de percorrer um grafo, e em particular os percursos em Largura e em Profundidade.
Árvores Geradoras Mínimas (8 aulas): estudaremos o problema, os algoritmos de Kruskal e Prim, a teoria subjacente e estruturas de dados para Conjuntos Disjuntos.
Caminhos Mínimos (5 aulas): estudaremos 3 versões do problema de caminhos mínimos (em grafos com pesos não-negativos, em grafos com pesos negativos e em DAGs) e soluções respectivas, incluindo os algoritmos de Dijkstra e Bellman-Ford.
Fluxo em Grafos (7 aulas): estudaremos o problema de fluxo máximo, dois algoritmos polinomiais para ele (Edmonds-Karp e Push-Relabel) e a teoria subjacente, incluindo a relação com cortes em grafos.
| Aula | Data | Descrição |
|---|---|---|
| 01 | 23/02 (Sex) | Introdução à Disciplina |
| 02 | 28/02 (Qua) | Introdução a Grafos e seus Algoritmos |
| 03 | 02/03 (Sex) | Representações de Grafos: Problema, Ideias e Apreciação |
| 04 | 07/03 (Qua) | Representações de Grafos: Alternativas, Comparação e Programação |
| 05 | 09/03 (Sex) | Distâncias em Grafos Não-Ponderados: Problema, Ideias e Apreciação |
| 06 | 14/03 (Qua) | Distâncias em Grafos Não-Ponderados: 2 Algoritmos e Discussão da Corretude |
| 07 | 16/03 (Sex) | Distâncias em Grafos Não-Ponderados: Discussão da Corretude |
| 08 | 21/03 (Qua) | Distâncias em Grafos Não-Ponderados: Invariantes de Laço |
| 09 | 23/03 (Sex) | Detecção de Ciclos em Grafos Não-Direcionados |
| 10 | 28/03 (Qua) | Detecção de Circuitos em Digrafos: Algoritmo e Discussão |
| 30/03 (Sex) | Feriado Nacional – Paixão de Cristo | |
| 11 | 04/04 (Qua) | Detecção de Circuitos em Digrafos: Corretude |
| 12 | 06/04 (Sex) | Corretude da Detecção de Circuitos; O Problema da Ordenação Topológica |
| 13 | 11/04 (Qua) | Ordenação Topológica: um Algoritmo e Corretude |
| 14 | 13/04 (Sex) | Árvores Geradoras Mínimas: Problema, Ideias e Apreciação |
| 15 | 18/04 (Qua) | Árvores Geradoras Mínimas: Corretude de uma Estratégia |
| 16 | 20/04 (Sex) | Árvores Geradoras Mínimas: Complexidade da Estratégia Inicial |
| 17 | 25/04 (Qua) | Árvores Geradoras Mínimas: Estratégia Alternativa (Kruskal) e Implementação |
| 18 | 27/04 (Sex) | Árvores Geradoras Mínimas: Implementação de Conjuntos Disjuntos e Kruskal |
| 19 | 30/04 (Seg) | Árvores Geradoras Mínimas: Complexidade e Corretude de Kruskal |
| 20 | 02/05 (Qua) | Árvores Geradoras Mínimas: Estratégia Alternativa (Prim) e Implementação |
| 21 | 04/05 (Sex) | Árvores Geradoras Mínimas: Implementação e Complexidade de Prim |
| 22 | 09/05 (Qua) | Caminhos Mínimos em Grafos Ponderados: Discussão, Algoritmo e Complexidade |
| 23 | 11/05 (Sex) | Caminhos Mínimos em Grafos Ponderados: Corretude do Algoritmo de Dijkstra |
| * | 16/05 (Qua) | Avaliação Parcial 1 |
| 24 | 18/05 (Sex) | Caminhos Mínimos com Pesos Negativos: Discussão (Orientação das Arestas, etc.) |
| 25 | 21/05 (Seg) | Caminhos Mínimos com Pesos Negativos: Discussão de Estratégias de Solução |
| 26 | 23/05 (Qua) | Caminhos Mínimos em DAGs |
| 27 | 25/05 (Sex) | Fluxo em Grafos (1/7) |
| 28 | 30/05 (Qua) | Fluxo em Grafos (2/7) |
| 29 | 01/06 (Sex) | Fluxo em Grafos (3/7) |
| 30 | 06/06 (Qua) | Fluxo em Grafos (4/7) |
| 31 | 08/06 (Sex) | Fluxo em Grafos (5/7) |
| 32 | 13/06 (Qua) | Fluxo em Grafos (6/7) |
| 33 | 15/06 (Sex) | Fluxo em Grafos (7/7) |
| * | 20/06 (Qua) | Avaliação Parcial 2 |
| 22/06 (Sex) | ||
| * | 27/06 (Qua) | Avaliação Final |
Para fins de registro, também é possível acessar a versão anterior do plano acima.