AULA 11
2 OUT, SEG |
- Resumo da aula anterior.
- Algoritmo dos caminhos aumentadores: aumenta através do caminho de
maior capacidade residual.
- O número de passos aumentadores do algoritmo é O(m log U), logo
o algoritmo é polinomial. Eficiência no pior caso.
- Trailer dos próximos episódios.
|
AULA 12
5 OUT, QUI |
- Resumo da aula anterior.
- Algoritmo dos caminhos aumentadores: Capacity scaling .
- O número de passos aumentadores do algoritmo é O(m log U), logo
o algoritmo é polinomial. A eficiência no pior caso é O(nm log U)) .
- Trailer dos próximos episódios.
|
RECESSO
9 OUT, SEG |
SEMANA DE ESTUDOS. NÃO HAVERÁ AULA.
|
FERIADO
12 OUT, SEG |
DIA DA PADROEIRA DO BRASIL.
|
AULA 13
16 OUT, SEG |
- Resumo da aula anterior.
- Algoritmo dos caminhos aumentadores: Shortest Augmenting Path.
- Análise dos invariantes do algoritmo.
- O número de passos aumentadores do algoritmo é O(nm).
A eficiência no pior caso é O(nm2)). O algoritmo é
fortemente polinomial.
- Trailer dos próximos episódios.
|
AULA 14
19 OUT, QUI |
- Resumo da aula anterior.
- Fluxos bloqueadores.
- Algoritmo de Dinic.
- Teorema. O Algoritmo de Dinic pára depois de no máximo
n-1 passos bloqueadores.
- Current arc data structure.
- Trailer dos próximos episódios.
|
PROVA
26 OUT, QUI |
PROVA 1
|
RECESSO
30 OUT, SEG |
NÃO HAVERÁ AULA.
|