RECESSO
4 SET, SEG |
SEMANA DE ESTUDOS. NÃO HAVERÁ AULA.
|
FERIADO
7 SET, QUI |
NÃO HAVERÁ AULA.
|
AULA 5
11 SET, SEG |
- Resumo da aula anterior.
- Algoritmo de Dijkstra: invariantes, número de iterações e eficiência no
pior caso.
- Trailer dos próximos episódios.
|
AULA 6
14 SET, QUI |
- Resumo da aula anterior.
- Ciclo de custo negativo: condição de inexistência.
- Algoritmo genérico que recebe uma rede (N,A), uma função-custo
c e devolve (1) um ciclo de custo negativo ou (2) uma
função-potencial que respeita c.
- Invariantes e número de iterações do algoritmo.
- Trailer dos próximos episódios.
|
AULA 7
18 SET, SEG |
- Resumo da aula anterior.
- Teorema. Seja (N,A) uma rede e c uma função custo.
Vae uma e apenas uma das seguintes afirmações:
(1) (N,A) possui um ciclo negativo;
(2) existe uma função-potencial que respeita c.
- Algoritmo Fila-de-arcos: eficiência no pior caso.
- Trailer dos próximos episódios.
|
AULA 8
21 SET, QUI |
- Resumo da aula anterior.
- Fluxos em redes: fluxos, saldos, excessos, função-capacidade, valor de
um fluxo.
- Problema do Fluxo Máximo: Dada uma rede (N,A), uma
função-capacidade u e dois nós distintos s e t,
encontrar um fluxo viável de s a t de valor máximo.
- Condição de otimalidade: cortes de capacidade mínima.
- Capacidade residual.
- Trailer dos próximos episódios.
|
AULA 9
25 SET, SEG |
- Resumo da aula anterior.
- Lema básico. Se x é um fluxo viável de s a
t e (Y,N-Y) é um corte viável, então a capacidade do corte é
pelo menos o valor do fluxo. (Conseqüência imediata: se a capacidade de um
corte viável é igual ao valor do fluxo então o fluxo é máximo e o corte tem
capacidade mínima entre todos os cortes viáveis.)
- Algoritmo dos caminhos aumentadores (Ford e Fulkerson): invariantes e
número de iterações (o algoritom é pseudo-polinomial).
- Trailer dos próximos episódios.
|
AULA 10
28 SET, QUI |
- Resumo da aula anterior.
- Teorema do fluxo máximo e corte mínimo.
- Teorema da integralidade do fluxo.
- Rede residual.
- Decomposição de fluxos: todo fluxo pode ser expresso como a soma de
fluxos e circulações elementares.
- Trailer dos próximos episódios.
|