Horário: 3as e 5as, das 10h às 12h.
Início: 1 de agosto de 2017.
Provas:
- P1: 03/10
- P2: 23/11
- PF: 30/11
Monitores:
- Igor Carpanese
- Rodrigo Luna
Repositório do código criado em sala de aula:
https://github.com/vigusmao/AlgGraf_2017_2
Ementa aproximada:
- Representação computacional de grafos;
- Buscas em grafos: geral, largura, profundidade;
- Aplicações de buscas: componentes conexos e biconexos, caminho mínimo em grafos sem pesos; componentes fortemente conexos de um digrafo;
- Backtracking;
- Algoritmos gulosos;
- Árvore geradora mínima;
- Caminho mínimo em grafos com pesos;
- Programação dinâmica e memoização;
- Fluxo máximo / corte mínimo;
Bibliografia sugerida
| Grafos e Algoritmos Computacionais | Introduction to Algorithms | ||
| (Jayme Luiz Szwarcfiter) | (Cormen, Leiserson, Rivest & Stein) | ||
 |  |
Conteúdo das aulas
01/08
Introdução. A busca pela eficiência. O problema da celebridade.
03/08
Representação de grafos (direcionados e não-direcionados, com e sem pesos nas arestas) no computador: listas de vértices e arestas, matriz de adjacências, listas de adjacências (possivelmente com uso de hashing), matriz de incidências.
Complexidades das operações básicas. O problema das estradas entre metrópoles.
08/08
Um primeiro programa com grafos utilizando matriz de adjacências (e listas de adjacências).
Código (em C) feito em sala de aula no GitHub.
10/08
Busca geral. Determinação de componentes conexas.
Busca em largura. Caminho mínimo entre dois vértices (sem pesos nas arestas).
15/08
Classificação das arestas na busca em largura. Busca em largura para grafos direcionados. Pseudo-código usando fila.
Busca em profundidade. Classificaço das arestas na busca em profundidade. Pseudo-código usando recursão.
17/08
Aplicação de busca em profundidade: determinação das articulações de um grafo.
24/08
Exemplo completo do algoritmo de determinação das articulações de um grafo, incluindo a determinação de suas componentes biconexas.
29/08
Usando uma pilha explícita para identificar as componentes biconexas ao longo da busca de forma eficiente.
Implementação de busca em profundidade e do algoritmo que encontra as articulações de um grafo.
Código (em Python) feito em sala de aula no GitHub.
31/08
05/09
12/09
14/09
19/09
Semana da Computação.
21/09
Semana da Computação.
26/09
28/09
Revisão para a P1.
03/10
P1.
05/10
Resolução da P1 em sala de aula.
10/10
17/10
19/10
24/10
SIAC 2017.
26/10
SIAC 2017.
31/10
07/11
Exemplo completo de execução do algoritmo de Floyd. Complexidade.
09/11
Programação dinâmica fora de grafos. Dividir e conquistar + Memoização.
14/11
Fluxo máximo em redes.
