Algoritmos e Grafos  —  2017/2

Página principal

Informações

Local: Sala F2-018.
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.  
 

Voltar ao topo