Horário: 3as e 5as, das 10h às 12h.
Início: 7 de março de 2017.
Provas:
- P1: 11/05
- P2: 22/06
- PF: 29/06
Monitores:
- Igor Carpanese
- Rodrigo Luna
Repositório do código criado em sala de aula:
https://github.com/vigusmao/AlgGraf2017_1
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;
- Programação dinâmica e memoização;
- Caminho mínimo em grafos com pesos;
- 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
07/03
Introdução. A busca pela eficiência. O problema da celebridade.
09/03
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.
14/03
Busca em grafos. Busca geral. Busca em largura. Classificação das arestas ao longo da busca.
16/03
Busca em largura (finalização). Algoritmo básico (pseudocódigo). Complexidade. Visita a arestas.
Busca em profundidade (ideia geral). Implementação recursiva.
21/03
Busca em profundidade (finalização). Algoritmo básico (pseudocódigo). Classificação das arestas ao longo da busca.
Aplicação de busca em profundidade: encontrando as articulações de um grafo.
23/03
Implementação (Python) do algoritmo geral de busca em profundidade, e do algoritmo que determina as articulações de um grafo dado.
Código feito em sala de aula no GitHub.
28/03
Busca em profundidade em grafos direcionados. Outros tipos de aresta (cruzamento, avanço).
Aplicação: algoritmo para determinar os componentes fortemente conexos de um grafo direcionado.
30/03
Backtracking: busca (normalmente em profundidade) em um grafo implícito. Descobrindo os vizinhos (possíveis próximos passos) à medida em que se avança na busca.
Cuidando para não propagar para o pai a sujeira feita pelo filho na estrutura que representa o estado corrente. Duas formas de se lidar com isso: (1) mexe sempre em uma cópia; ou, em geral melhor: (2) "sujou, limpa"
Exemplo: o problema das 8 (ou n) rainhas.
11/04
Árvore geradora mínima. Algoritmo de Kruskal.
Idéia geral de algoritmos gulosos, e receita geral cut & paste para prova de corretude.
13/04
Árvore geradora mínima (continuação). Algoritmo de Prim.
Prova de corretude baseada na receita geral cut & paste para algoritmos gulosos.
18/04
Outras aplicações da técnica de algoritmos gulosos.
O problema da mochila 0-1 (gulosos não funcionam) e fracionário (guloso por densidade funciona).
20/04
Implementação de dois algoritmos em tempo exponencial para o problema da mochila 0-1: um usando enumeração total (testa todos os subconjuntos, mapeados pelos primeiros naturais em base 2), e outro usando backtracking com poda. A segunda maneira prova-se muito superior à primeira.
Código feito em sala de aula no GitHub.
25/04
Caminho Mínimo. Algoritmo de Bellman-Ford.
27/04
Caminho Mínimo. Algoritmo de Dijkstra.
02/05
Revisão para a P1: determinação das articulações de um grafo e de suas componentes biconexas.
04/05
Problema da coloração de vértices (NP-difícil). Gulosos que não funcionam. Algoritmo em tempo exponencial (backtracking com podas).
Discussão: quando fazer uma busca em profundidade, quando fazer uma busca em largura, quando tanto faz...
09/05
Revisão global para a P1.
11/05
P1.
16/05
Resolução da P1 em sala de aula.
18/05
All-pairs shortest paths. Algoritmo Floyd-Warshall. Idáias básicas da técnica de Programação Dinâmica.
23/05
Exemplo completo de execução do algoritmo Floyd-Warshall.
PD bottom-up (clássica) e top-down (recursão com memoização).
Crescimento exponencial da quantidade de chamadas recursivas quando há repetição de subproblemas e não se usa PD.
25/05
Implementação de exemplos comparativos sobre dividir-e-conquistar e PD.
Fatorial, Fibonacci, Floyd.
Código feito em sala de aula no GitHub.
30/05
PD como maneira eficiente de se resolver relações de recorrência.
Ex.: sequências binárias sem dois dígitos 1 consecutivos; retas coplanares particionando o plano.
Caracterização dos problemas que admitem solução via PD: subestrutura ótima (subdivisão em problemas idênticos ao original, apenas menores); repetição de subproblemas.
01/06
Implementação de soluções para o problema dos armários. Algoritmos em tempo O(n2), O(n log n), O(n), O(sqrt(n)), O(1).
Código feito em sala de aula no GitHub.
Implementação de soluções para o problema das sequências sem dígitos 1 consecutivos. Algoritmos via enumeração exaustiva, backtracking com poda, recursão, PD top-down (memoização) e PD bottom-up.
Código feito em sala de aula no GitHub.
06/06
Programação Dinâmica aplicada a outros problemas de otimização. Exemplo: o problema da mochila 0-1 revisitado.
Como memoizar em múltiplas dimensões. Considerações sobre tempo e espaço das implementações bottom-up e top-down.
08/06
Fluxo máximo em redes. Ford-Fulkerson.
13/06
Teorema do Fluxo Máximo / Corte Mínimo. Edmonds-Karp.
20/06
Revisão para a P2.
22/06
P2.
27/06
Resolução da P2 em sala de aula.
29/06
PF.
04/06
Prova de Segunda Chamada.
