Horário: 3as e 5as, das 10h às 12h.
Início: 12 de abril de 2022.
Nos dias 24/05, 31/05, 02/06 e 07/06, a aula será remota nesta sala do Google Meet.
Provas:
- quinta-feira, 09/06
- P2: terça-feira, 19/07
- PF: quinta-feira, 28/07
Primeira lista de exercícios aqui.
Segunda lista de exercícios aqui. Gabarito aqui.
Repositório do código criado em sala de aula:
https://github.com/vigusmao/AlgGraf_2022_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: busca em um grafo implícito (se der tempo);
- Algoritmos gulosos e técnica geral para prova de corretude;
- Á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
12/04
Introdução ao curso. Apresentação da ementa. Revisão rápida dos principais conceitos em Teoria dos Grafos.
14/04
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.
26/04
Comparação tabular detalhada das principais operações segundo cada uma das possíveis representações de grafos no computador.
Problemas propostos (para pensar em casa):
(1) O Problema da Celebridade: dado um grafo simples, direcionado, com n vértices representando pessoas numa festa, e m arestas (x,y) indicando que a pessoa x conhece a pessoa y, determinar se há alguma celebridade na festa. Uma celebridade é definida como alguém que não conhece ninguém na festa e que é conhecida por todas as pessoas da festa.
(2) O Problema das Metrópoles: dado um grafo simples, não-direcionado, com n vértices representando cidades, cada qual com seu número de habitantes fornecido, e m arestas representando estradas entre cidades, determinar quantas estradas existem conectando duas metrópoles quaisquer. Uma metrópole é definida como uma cidade com mais do que um milhão de habitantes.
28/04
Discussão dos problemas da Celebridade e das Metrópoles. Comparando soluções e suas complexidades.
Implementação em Java da representação de grafos via hashing (cada vértice aponta para um HashSet com seus vizinhos).
03/05
Buscas (percursos sistemáticos) em grafos. Busca Geral. Busca em Largura. Busca em Profundidade.
Implementando Busca em Largura usando uma fila.
Aplicação de Busca em Largura: encontrando o caminho mais curto entre dois vértices num grafo onde as arestas tem pesos unitários.
05/05
Implementando Busca em Profundidade de forma recursiva (sem uma pilha explícita).
Aplicação de Busca em Profundidade: localizando as articulações de um grafo.
10/05
Exemplo completo de execução do algoritmo que determina articulações -- e agora também as próprias componentes biconexas -- de um grafo.
Ordenação Topológica. Aplicações. Algoritmos para encontrar uma Ordenação Topológica em um DAG (grafo direcionado acíclico): via busca em profundidade, e via eliminação sucessiva de fontes.
12/05
Buscas em grafos implícitos: resolvendo problemas de enumeração ou de busca exaustiva via força bruta (backtracking).
Exemplo: o Problema das Rainhas Pacíficas. Implementação (Java).
Implementação do algoritmo de Ordenação Topológica via eliminação sucessiva de fontes.
24/05
Aula remota: método geral para backtracking como uma busca em profundidade em um grafo (implícito) de estados.
O problema da Coloração de Vértices. Estratégia de backtracking para encontrar uma coloração com até k cores, caso exista.
Implementação.
Gravação da aula.
26/05
Árvore Geradora Mínima (MST). Algoritmo de Kruskal. Revisão rápida de disjoint sets (UNION/FIND).
Método geral (estratégia de "cut and paste") para prova de corretude de algoritmos gulosos.
31/05
Aula remota: reforço da técnica de "cut and paste". Algoritmo de Prim para MST.
Gravação da aula.
02/06
Aula remota: correção da lista de exercícios. Dúvidas gerais.
Gravação da aula.
07/06
Aula remota: o problema do Caminho Mínimo com origem única (single source shortest paths). Algoritmo de Bellman-Ford. Detecção de ciclos de custo negativo.
Gravação da aula.
09/06
P1.
14/06
Correção da P1 em sala de aula.
Revisão do algoritmo de Bellman-Ford.
21/06
Algoritmo de Dijkstra. Análise, complexidades de diferentes implementações.
23/06
Elementos de Programação Dinâmica: Dividir-e-conquistar possível (subestrutura ótima, em problemas de otimização). Repetição de sub-problemas.
Algoritmos pseudo-polinomiais.
O algoritmo de Floyd-Warshall para o Problema do Caminho Mínimo entre Todos os Pares.
28/06
Exemplo completo de execução do algoritmo de Floyd-Warshall. Discussão sobre PD bottom-up versus top-down. Percebendo que uma implementação recursiva do F-W teria repetições de subproblemas.
30/06
Implementação (Python) de Fibonacci (não-recursivo, recursivo ingênuo e recursivo com memoização).
Implementação (Python) do algoritmo de Floyd-Warshall.
05/07
Terminando a implementação (Python) do algoritmo de Floyd-Warshall usando recursão+memoização (PD top-down), e também acrescentando a informação de predecessores.
O Problema da Mochila. Força bruta versus PD. https://github.com/vigusmao/AlgGraf_2022_1/blob/master/mochila.py (Python) do algoritmo de PD (top-down).
07/07
Fluxo em redes. Algoritmo de Ford-Fulkerson. Teorema do Fluxo Máximo - Corte Mínimo. Pior caso pseudo-polinomial.
12/07
Algoritmo de Edmonds-Karp. Análise de complexidade.
14/07
Resolução da lista de exercícios. Dúvidas pré-P2.
19/07
P2.
21/07
Resolução da P2 em sala de aula. Divulgação das notas.
