Horário: 3as e 5as, das 10h às 12h.
Início: 17 de março de 2015.
Provas:
- P1:
- P2: 25/06
- PF: 02/07
Primeira lista de exercícios.
Segunda lista de exercícios.
Repositório do código criado em sala de aula:
https://github.com/vigusmao/AlgGraf_2015_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;
- 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;
- Classes de complexidade e introdução à teoria da NP-completude.
Bibliografia sugerida
| Grafos e Algoritmos Computacionais | Introduction to Algorithms | ||
| (Jayme Luiz Szwarcfiter) | (Cormen, Leiserson, Rivest & Stein) | ||
 |  |
Conteúdo das aulas
17/03
Introdução. O problema da celebridade. Conceito de eficiência.
19/03
Representação de grafos (direcionados e não-direcionados) no computador: listas de vértices e arestas, matriz de adjacências, listas de adjacências, matriz de incidências, hashing.
Complexidades das operações básicas.
24/03
Representando pesos/custos associados a vértices e arestas. O problema das estradas entre metrópoles.
26/03
Implementação de estruturas para grafos from scratch.
Grafos aleatórios: os modelos Gn,p e Gn,m.
Tema incidental: permutando aleatória e uniformemente os elementos de uma lista em tempo linear: o algoritmo Knuth shuffle.
Código escrito em sala (linguagem Python) no github.
31/03
Implementando algoritmos para problemas em grafos. Comparação prática da performance de um algoritmo quadrático e de um algoritmo linear (o problema da celebridade revisitado).
Código escrito em sala (linguagem Python) no github.
02/04
Dois algoritmos para se criar um grafo aleatório do modelo Gn,m: o primeiro gera uma lista com todas as arestas do grafo completo e usa Knuth shuffle para selecionar m arestas; o segundo sorteia pares de vértices, verificando sempre se um mesmo par já foi sorteado antes, até m pares distintos terem sido sorteados. Discussão sobre as complexidades dos dois algoritmos. Tema incidental: o paradigma combinatório do colecionador de coupons.
Buscas em grafos: ideia geral.
Busca em largura.
07/04
Busca em largura: algoritmo básico completo. Tipos de aresta. Teorema da diferença de nível menor ou igual a 1. Possíveis customizações do algoritmo básico: visitando vértices e arestas.
09/04
Busca em largura: exemplo de execução passo-a-passo.
Aplicação: determinando a distância mínima entre vértices (sem pesos nas arestas).
14/04
Busca em profundidade: algoritmo básico completo. Implementação recursiva.
16/04
Aplicação de busca em profundidade: componentes biconexas de um grafo simples não-direcionado.
28/04
Backtracking: busca em profundidade em um grafo implícito de "configurações iterativas".
O problema das rainhas. O problema da carga da balsa.
Conceito de algoritmos pseudo-polinomiais.
30/04
Dois problemas clássicos em Teoria dos Grafos: Coloração de vértices e Conjunto Dominante Mínimo. Algoritmos gulosos que não funcionam (contra-exemplos são instâncias para as quais o algoritmo falha --- basta um contra-exemplo para mostrar que não é verdade que o algoritmo funciona sempre, o que em geral invalida completamento o algoritmo). Soluções por busca exaustiva (ok para instâncias pequenas) via backtracking.
05/05
O problema da árvore geradora mínima. Algoritmo de Kruskal. Prova de corretude baseada na receita geral cut and paste para algoritmos gulosos.
07/05
Complexidade do algoritmo de Kruskal. Implementação usando listas para conjuntos disjuntos (UNION/FIND) com UNION feita via concatenação da menor lista ao final da maior lista. (Leitura opcional: implementação mais eficiente do algoritmo de Kruskal usando árvores com union by rank e path compression.)
Algoritmo de Prim. Complexidade do algoritmo de Prim. Implementação usando heap binária. (Leitura opcional: implementação mais eficiente do algoritmo de Prim usando heap de Fibonacci.)
12/05
Resolução da primeira lista de exercícios.
19/05
Prova de corretude do algoritmo de Prim baseada, mais uma vez, na receita geral cut and paste para algoritmos gulosos.
Generalização de algoritmos gulosos e da técnica de prova: o problema da mochila (versão 0-1 e versão contínua). Algoritmo guloso, com prova de corretude, para a versão contínua.
21/05
Primeira Prova.
26/05
Resolução em sala da Primeira Prova.
28/05
O Problema do Caminho Mínimo e suas variantes mais conhecidas. Qualquer subcaminho contido em um caminho mínimo é também mínimo. Relaxamento de arestas.
Algoritmo de Bellman-Ford para a variante Single Source.
09/06
Passo-a-passo do algoritmo de Bellman-Ford. Detecção de ciclos com custo negativo.
Algoritmo de Dijkstra.
11/06
Duas provas para o algoritmo de Dijkstra: pela "receita para algotimos gulosos" (cut and paste) e por indução. Complexidade utilizando arrays, heaps e heaps de Fibonacci.
16/06
Ordenação topológica. Algoritmo eficiente para caminho mínimo em DAGs (grafos direcionados acíclicos).
18/06
All-pairs shortest paths: o algoritmo de Floyd-Warshall. Ideias básicas de programação dinâmica e memoização.